4 STACKS AND QUEUES Flashcards
What are the two data structures introduced in this chapter?
Stacks and queues
What is the primary difference between stacks and queues?
Stacks return the most recently inserted data first (LIFO), while queues return the oldest data (FIFO)
What is the core algorithm that stacks form the basis for?
Depth-first search
What type of search do queues enable?
Breadth-first search
Define a stack.
A last-in, first-out (LIFO) data structure
What operations does a stack support?
- Push
- Pop
What happens when elements are pushed onto a stack in the order 1, 2, 3, 4, 5?
They are retrieved in the order 5, 4, 3, 2, 1
How can stacks be implemented?
- Arrays
- Linked lists
What is the initial value of the top index in a stack implemented as an array?
-1
What does the Push operation do in a stack?
Adds a new element to the top of the stack
What is the code structure for pushing an element onto a stack implemented as an array?
IF s.top == s.array_size – 1:
Expand the size of the array
s.top = s.top + 1
s.array[s.top] = value
What does the Pop operation do in a stack?
Removes the element from the top of the stack and returns it
What is the code for popping an element from a stack implemented as an array?
IF s.top > -1:
value = s.array[s.top]
s.top = s.top – 1
return value
What is the primary advantage of using a linked list to implement a stack?
Increased flexibility; no need to worry about array size
Define a queue.
A first-in, first-out (FIFO) data structure
What operations does a queue support?
- Enqueue
- Dequeue
What happens when five elements are enqueued in the order 1, 2, 3, 4, 5?
They are retrieved in the same order: 1, 2, 3, 4, 5
How can queues be implemented?
- Arrays
- Linked lists
What problem can occur when dequeuing from a fixed array?
A block of empty space will accumulate at the front of the array
What is a better solution to avoid shifting elements in a queue implemented as an array?
Wrapping the queue around the end of the array
What pointers are maintained in a queue implemented as a linked list?
- Front
- Back
What does the Enqueue operation do in a queue?
Adds a new element to the back of the queue
What is the code for enqueuing an element in a queue?
LinkedListNode: node = LinkedListNode(value)
IF q.back == null:
q.front = node
q.back = node
ELSE:
q.back.next = node
q.back = node
What does the Dequeue operation do in a queue?
Removes the element from the front of the queue and returns it
