# Stacks and Queues

Computer Science I · Data Structures · https://tryals.app/learn/computer-science-i/stacks-and-queues

## Core Order Structures

Some of the most useful data structures are deliberately restricted, allowing additions and removals only at specific ends. This exact restriction is what makes them powerful.

A **stack** is a **last-in, first-out (LIFO)** structure. You **push** elements onto the top, **pop** the top element off, and **peek** to view it without removal. The last item added is always the first one popped, acting just like a physical stack of plates.

A **queue** is a **first-in, first-out (FIFO)** structure. You **enqueue** at the back and **dequeue** from the front. The first element added is the first one removed, modeling any standard service line.

| Structure | Order | Add Operation | Remove Operation |
| --- | --- | --- | --- |
| Stack | LIFO | push (top) | pop (top) |
| Queue | FIFO | enqueue (back) | dequeue (front) |

Both are Abstract Data Types implemented via arrays or linked lists. When well-implemented, all core operations run in $O(1)$ time.

## Variants and Pitfalls

A common variant is the **deque** (double-ended queue), which allows adding and removing elements at **both** ends. This effectively generalizes both stacks and queues into a single flexible structure.

Applications are distinct and widespread:
- **Stack uses:** **call stack** for function tracking, undo/redo histories, bracket matching, and expression evaluation.
- **Queue uses:** print jobs, task scheduling, and **breadth-first** graph traversal.

> **Common pitfall:** Mixing up LIFO and FIFO. A stack always returns the most recently added element, while a queue always returns the oldest. Never expect a queue to act like a stack.

## Practice questions

4 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. A stack starts empty and these operations run in order: push 1, push 2, pop, push 3, push 4, pop, pop, pop. Order the four popped values by when they came out.

**Answer:**

1. 2
2. 4
3. 3
4. 1

**Why:** The pops give 2, then 4, then 3, then 1. Notice that 1 was pushed first and popped last, while 3 was pushed after 2 yet came out after 4, a stack's output order depends on the interleaving of pushes and pops, not simply on the reverse of the push order.

Page: https://tryals.app/practice/computer-science-i/stacks-and-queues/a-stack-starts-empty-and-these-operations-run-in-order-push-1-push

### 2. Both a stack and a queue store items and hand them back one at a time. Why does reversing which end you remove from make one of them right for undo history and the other right for a print spooler?

A. Because a stack can hold more items than a queue, and undo histories are longer than print queues.
B. Because a stack is faster than a queue, and undo needs to be immediate while printing does not.
C. Because the removal order encodes a different relationship to time.
D. Because a queue preserves the items' original values while a stack modifies them.

**Answer:** C. Because the removal order encodes a different relationship to time.

**Why:** The two differ in one decision, which end you remove from, and that decision encodes a policy about time. Last-in-first-out returns the most recent, which is precisely what undo means. Using a stack for a spooler would serve the newest job first, leaving a nine a.m. document unprinted all day. The choice is never about speed; both are constant time.

Page: https://tryals.app/practice/computer-science-i/stacks-and-queues/both-a-stack-and-a-queue-store-items-and-hand-them-back-one-at-a

### 3. Depth-first search can be written recursively with no visible stack, or iteratively with an explicit one. What is the recursive version actually using?

A. The call stack, borrowed to remember where to resume
B. The heap, since recursive calls allocate dynamically
C. A queue maintained by the runtime, which differs from an explicit stack
D. No stack at all, which is why recursion can exhaust memory

**Answer:** A. The call stack, borrowed to remember where to resume

**Why:** Each frame holds the node you must come back to, which is exactly what the explicit stack holds, same LIFO discipline, different owner. Recursion is more readable and bounded by stack depth; the explicit version can be given a heap-allocated stack, which is how graph traversal survives a million-node input.

Page: https://tryals.app/practice/computer-science-i/stacks-and-queues/depth-first-search-can-be-written-recursively-with-no-visible-stack

### 4. Select every statement the lesson supports about stacks and queues.

A. When well implemented, push, pop, enqueue and dequeue are all O(1)
B. A deque generalises both a stack and a queue
C. A queue returns whichever element has the highest priority
D. peek returns the top of a stack without removing it
E. Both are ADTs and can be built on an array or on a linked list

**Answer:** A. When well implemented, push, pop, enqueue and dequeue are all O(1); B. A deque generalises both a stack and a queue; D. peek returns the top of a stack without removing it; E. Both are ADTs and can be built on an array or on a linked list

**Why:** Stacks and queues are interfaces with constant-time operations under either implementation, peek looks without removing, and a deque relaxes both restrictions. Serving by priority is the priority queue, a different ADT, expecting a queue to know about importance is a common and expensive mix-up.

Page: https://tryals.app/practice/computer-science-i/stacks-and-queues/select-every-statement-the-lesson-supports-about-stacks-and-queues