Unit 3: Stacks and Queues
CC4 – Data structures and algorithms
Instructor: Don Harl C. Malabanan
Importance of Stacks and Queues
• Both stacks and queues are an example of data structures
• Used to collect, arrange, and manipulate data
• Most common way to arrange data in different algorithms of the same data type
• Expressions (infix, prefix, postfix)
• Binary search trees
• AVL trees
• Graphs
• Searching algorithms
• Sorting algorithms
Applying Stacks and Queues
• Usually implemented in a one-dimensional array
• Can use other variations: list, linked list, etc.
• Possible to use for any programming language
• Can also be used in multidimensional arrays
• Not recommended
• Increases the time complexity of the space required
Stacks and Queues
Stack:
• Last-in first-out policy
• First element is at the bottom
• Last element is at the topmost part
• Examples: Pancakes, Pringles can, Stack of books, etc.
Queue:
• First-in first-out policy
• First element is at the beginning/front
• Last element is at the end of the queue
• Examples: lines at the supermarket or jeep.
Stack
• Container based on the last-in-first-out (LIFO) policy
• New data is inserted at the last index (push)
• Data to be deleted starts off with the last index (pop)
• Uses only one(1) pointer
• Starts off at array[-1]: empty
• Maximum number of elements is the limit of the array
Inserting Elements in Stacks (Push)
• Create a one- dimensional array
• Pointer is at -1
• Place value to be inserted in another variable
• Locate the pointer
• Iterate the value of the pointer
• Place value to the array where the index pointer is located (array[pointer])
Deleting Elements in Stacks (Pop)
• Locate the pointer
• Assign the value of the pointer to the index of the array
• Remove the value at array [pointer]
• Decrement the value of the pointer by 1
Queues
• Container based on the first-in-first-out (FIFO) Policy
• New data is inserted at the last index
• Data to be deleted starts off with the first index
• Uses two(2) pointers
• One pointer is for the first element in the array
• Another pointer is for the space after the last element in the array
• Maximum number of elements is array.length-1
• Queue is considered empty if both pointers are on the same position
• Array can be considered circular
Inserting Elements in Queues
• Called ENQUEUE
• Create a one-dimensional array
• Place the value to be inserted into a variable
• Locate the value of the second pointer (position of the index number after the
last element that was placed)
• Place value to the array where the index is the seconds pointer (array[pointer2])
• Iterate the second pointer
Deleting Elements in Queues
• Called Dequeue
• Locate where the first pointer is (pointer that shows the earliest element
inserted)
• Remove the value at array[pointer1]
• Iterate first pointer
Activity 3: 10pts
1. Illustrate the final stack with the following commands and show the pointer:
• N=4, Pop(), Pop(), Push(4), Push(4), Push(“Array”), Pop(), Push(3)
• N=2, Push(3), Push(-3), Push(-4), Push(5), Pop()
• N=1, Push(5), Pop(), Push(“abra”), Push(“alakazam”), Pop()
• N=9, Pop(), Pop(), Push(125), Push(44), Push(“yes”)
• N=7, Push(3), Push(5), Push(“CC4”), Pop(), Pop(), Push(6), Pop(), Push(4),
Push(19), Push(-7), Pop(), Push(“almost_there”), Push(“end”)
• 1pt each
Activity 3: 10pts cont.
1. Illustrate the queue with its pointers(p1, p2) given the FF commands:
• N=3, Enqueue(4), Dequeue(), Enqueue(“yes”), Enqueue(“woof”),
Enqueue(5), Enqueue(6), Enqueue(5), Dequeue()
• N=7, Dequeue(), Enqueue(5), Enqueue(41), Enqueue(66), Enqueue(‘G’),
Deqeue(), Dequeue()
• N=1, Enqueue(5), Enqueue(522), Enqueue(66), Dequeue()
• N=10, Enqueue(‘s’), Enqueue(3), Enqueue(1), Enqueue(6), Dequeue(),
Dequeue(), Dequeue(), Enqueue(3)
• N=5, Enqueue(“ ”), Enqueue(3), Enqueue(“ ”), Enqueue(4), Dequeue()
• 1pt each
