Source: CS 225 Midterm 1 Solutions, UIUC
Tags: stack, queue, LIFO, FIFO, enqueue, dequeue, push, pop, isEmpty, singly linked list queue, tail pointer, running time, stack-queue problems, reverse between delimiters, CS 225, UIUC, C++
Difficulty: Intermediate Prerequisites: Pointers and linked lists (see Part 1 and Part 2 notes), basic understanding of abstract data types.
Stacks and queues are the two fundamental linear abstract data types. A stack is last-in, first-out (LIFO); a queue is first-in, first-out (FIFO). CS 225 tests these both as concepts (which operations are O(1) for a given implementation?) and as tools (write an algorithm that uses a stack and a queue together to solve a problem). The exam problem here, reversing elements between delimiter zeroes, is a classic pattern: use a stack to reverse a subsequence, then feed the reversed elements back into a queue. Understanding the interfaces (push/pop vs. enqueue/dequeue) and knowing when each data structure is the right tool is essential for the rest of the course.
Stacks support push and pop (both O(1)); queues support enqueue and dequeue (O(1) depends on implementation). When a queue is backed by a singly linked list with a tail pointer, whether enqueue and dequeue are O(1) depends on which end is the front and which is the rear. Stacks naturally reverse sequences, which makes them useful whenever you need to flip the order of a subsequence within a larger structure.
Stack
A LIFO (last-in, first-out) data structure. The most recently added element is the first one removed. Core operations: push(e) adds an element, pop() removes and returns the top element, isEmpty() checks if the stack is empty. In simple terms, it is a pile of plates: you can only add or remove from the top.
Queue
A FIFO (first-in, first-out) data structure. The first element added is the first one removed. Core operations: enqueue(e) adds to the rear, dequeue() removes and returns from the front, isEmpty() checks if the queue is empty. In simple terms, it is a queue at a shop: first person in line is served first.
LIFO
Last-in, first-out. The access pattern of a stack.
FIFO
First-in, first-out. The access pattern of a queue.
Tail pointer
A pointer maintained alongside the head pointer in a linked list, pointing to the last node. Allows O(1) insertion at the tail without traversing the entire list.
Enqueue
Adding an element to the rear of a queue.
Dequeue
Removing and returning the element at the front of a queue.
When you implement a queue using a singly linked list with both a head and a tail pointer, the running times of enqueue and dequeue depend on which end of the list represents the front (dequeue end) and which represents the rear (enqueue end).
If the rear of the queue is at the head of the linked list:
Enqueue (insert at the head): O(1). You create a new node, point its next to the current head, and update the head pointer.
Dequeue (remove from the tail): O(n). In a singly linked list, reaching the node before the tail requires traversing from the head, because there is no prev pointer.
This is the less efficient arrangement. The better design places the rear at the tail (enqueue at tail in O(1) using the tail pointer, dequeue from head in O(1)).
A stack reverses the order of any sequence you push onto it. If you push elements 1, 2, 3, then pop them, you get 3, 2, 1. This property is central to problems that require selective reversal within a larger structure.
The problem: given a queue of integers, reverse the elements between each consecutive pair of zeroes. Pairs do not overlap (first zero pairs with second, third with fourth, etc.). If there is an odd number of zeroes, elements after the last zero are also reversed.
Example:
Input: 1 0 5 3 0 3 1 0 2 6 5
Output: 1 0 3 5 0 3 1 0 5 6 2
The 5 and 3 between the first pair of zeroes are reversed. The 3 and 1 between the second and third zeroes are left alone (unpaired). The 2, 6, 5 after the third (unpaired) zero are reversed.
Algorithm using a flag, a stack, and an output queue:
Initialise a flag temp2 = 0 to track whether you are currently in a "reversing" section.
Dequeue elements one at a time from the input queue.
Four cases per element:
Element is 0 and flag is 0 (not currently reversing): Start reversing. Set flag to 1. Enqueue the 0 onto the output queue.
Element is 0 and flag is 1 (currently reversing): Stop reversing. Set flag to 0. Pop everything from the stack onto the output queue (this reverses them). Then enqueue the 0.
Element is non-zero and flag is 0: Not in a reversing section. Enqueue directly onto the output queue.
Element is non-zero and flag is 1: In a reversing section. Push onto the stack.
After the main loop, if the stack still has elements (odd number of zeroes), pop them all onto the output queue.
Copy the output queue back to the original queue.
void Rev0(Queue & queue) {
int temp1, temp2;
Stack s;
Queue q;
temp2 = 0;
while (!queue.isEmpty()) {
temp1 = queue.dequeue();
if ((temp1 == 0) && (temp2 == 0)) {
temp2 = 1;
q.enqueue(temp1);
}
else if ((temp1 == 0) && (temp2 == 1)) {
temp2 = 0;
while (!s.isEmpty()) {
q.enqueue(s.pop());
}
q.enqueue(temp1);
}
else if ((temp1 != 0) && (temp2 == 0)) {
q.enqueue(temp1);
}
else if ((temp1 != 0) && (temp2 == 1)) {
s.push(temp1);
}
}
while (!s.isEmpty()) {
q.enqueue(s.pop());
}
queue = q;
}
Key details graders look for:
The zero delimiters themselves are enqueued, not pushed onto the stack.
After the closing zero, the stack is emptied before the zero is enqueued (reversed elements appear before the closing zero).
The final cleanup loop handles the case where the input ends mid-reversal.
The result is written back to the original queue reference.
Queue backed by singly linked list (rear at head):
Enqueue (insert at head):
new_node -> [old head] -> ... -> [tail]
O(1)
Dequeue (remove from tail):
[head] -> ... -> [node before tail] -> [tail] (must traverse to find node before tail)
O(n)
Rev0 trace on input 1 0 5 3 0 3 1 0 2 6 5:
Dequeue 1: flag=0, not zero -> enqueue 1. q: [1]
Dequeue 0: flag=0, zero -> flag=1, enqueue 0. q: [1, 0]
Dequeue 5: flag=1, not zero -> push 5. s: [5]
Dequeue 3: flag=1, not zero -> push 3. s: [5, 3]
Dequeue 0: flag=1, zero -> flag=0, pop all (3 then 5), enqueue 0.
q: [1, 0, 3, 5, 0]
Dequeue 3: flag=0, not zero -> enqueue 3. q: [1, 0, 3, 5, 0, 3]
Dequeue 1: flag=0, not zero -> enqueue 1. q: [1, 0, 3, 5, 0, 3, 1]
Dequeue 0: flag=0, zero -> flag=1, enqueue 0. q: [1, 0, 3, 5, 0, 3, 1, 0]
Dequeue 2: flag=1, not zero -> push 2. s: [2]
Dequeue 6: flag=1, not zero -> push 6. s: [2, 6]
Dequeue 5: flag=1, not zero -> push 5. s: [2, 6, 5]
Queue empty. Pop remaining: 5, 6, 2.
q: [1, 0, 3, 5, 0, 3, 1, 0, 5, 6, 2]
Stacks are used in function call management (the call stack), expression evaluation (converting infix to postfix), undo/redo systems, and backtracking algorithms (depth-first search). Queues are used in breadth-first search, print job scheduling, request handling in web servers, and buffering (e.g. streaming video). The pattern of selectively reversing segments appears in text processing (reversing words within a sentence) and network packet reordering.
Students often assume that a queue backed by a singly linked list with a tail pointer has O(1) for both enqueue and dequeue in all configurations. The tail pointer helps insertion at the tail, but removal from the tail still requires traversal because you need the second-to-last node's pointer. Which end is front and which is rear matters.
Students sometimes push the zero delimiters onto the stack along with the data elements. The zeros are structural markers and should be enqueued directly, not reversed.
Forgetting the final cleanup loop (emptying the stack after the main loop ends) is a common error. Without it, elements after an unpaired zero are lost.
Students occasionally call dequeue() on a potentially empty queue without checking isEmpty() first, which is undefined behaviour.
The queue-implementation running-time question (which end is front, which is rear) is a classic 2.5-point multiple-choice. Think carefully about which operations need traversal.
The Rev0-style problem is a 20-point coding question. Graders award points for the main loop, correct use of the flag, correct push/pop/enqueue/dequeue calls, handling the closing zero, handling the odd-zero case, and writing the result back.
Comments are worth 6 points. Explain your flag, your cases, and your cleanup step.
Deducting points for calling dequeue on a possibly empty queue is explicitly mentioned in the grading rubric.
True or false: A stack is a FIFO data structure.
Fill in the blank: In a singly linked list with a tail pointer, removing the last element requires traversing the list because you need a pointer to the ______ node.
True or false: Pushing elements 4, 7, 2 onto a stack and then popping all three gives you 4, 7, 2 in that order.
Fill in the blank: dequeue() removes from the ______ of the queue, while enqueue() adds to the ______.
True or false: In the Rev0 problem, the zero delimiters should be pushed onto the stack.
Answers: 1. False (LIFO). 2. Second-to-last (or penultimate). 3. False (you get 2, 7, 4). 4. Front, rear. 5. False (they are enqueued directly).
Q: A queue is implemented as a singly linked list with a tail pointer. The front of the queue is at the head and the rear is at the tail. What are the running times of enqueue and dequeue?
A: Both are O(1). Enqueue inserts at the tail using the tail pointer, and dequeue removes from the head, which is a direct pointer update.
Q: Same setup, but the front of the queue is at the tail and the rear is at the head. What changes?
A: Enqueue is O(1) (insert at head), but dequeue is O(n) (remove from tail requires traversal to find the second-to-last node).
Q: In the Rev0 problem, what happens if the input queue contains no zeroes at all?
A: Every element is dequeued with the flag at 0, so every element is enqueued directly to the output queue. The output is identical to the input. Nothing is reversed.
Q: In the Rev0 problem, what happens if the input is 0 1 2 3?
A: The first 0 sets the flag to 1. Then 1, 2, 3 are pushed onto the stack. The main loop ends with items still on the stack. The cleanup loop pops 3, 2, 1 onto the output queue. Result: 0 3 2 1.
Q: Why is a stack the right tool for reversing a subsequence, rather than a second queue?
A: A stack reverses the order of elements naturally through its LIFO property. If you enqueue elements into a second queue, they come out in the same order (FIFO), which does not reverse anything.
The stack's role as a reversing tool reappears in expression parsing (converting infix to postfix notation) and in depth-first search (DFS uses a stack, while BFS uses a queue). Queue implementations connect back to linked list design from Part 2 of these notes. Later in CS 225, you will use stacks and queues as building blocks for tree traversals: level-order traversal uses a queue, while iterative pre-order/in-order traversals use a stack.
stack, queue, LIFO, FIFO, push, pop, enqueue, dequeue, isEmpty, abstract data type, ADT, singly linked list, tail pointer, head pointer, O(1), O(n), running time, reverse between delimiters, selective reversal, boolean flag, stack as reversal tool, CS 225, UIUC, data structures, midterm, C++