Stacks & Queues
Stacks and queues are two of the most fundamental linear data structures in computer science. A stack enforces Last-In, First-Out (LIFO) access; a queue enforces First-In, First-Out (FIFO) access. Together, they provide structured, predictable patterns for managing data.
This guide covers stack and queue ADTs, array and linked list implementations, circular queues, priority queues, deques, code walkthroughs, and a 10-question practice quiz.
Stack Operations: Push & Pop
Stack (top → bottom)
State
Operation
None
Type
—
Top Element
Empty
Size
0 / 6
1Introduction
In the world of computer science, data structures serve as the bedrock upon which efficient algorithms and robust software systems are built. Among the most fundamental linear data structures are Stacks and Queues. These simple yet powerful structures provide specific rules for adding and removing elements, imposing order and predictability on data management.
Understanding their principles, implementations, and applications is crucial for any aspiring computer scientist or software engineer, as they underpin everything from operating system process scheduling to web browser navigation history, compiler expression parsing, and graph traversal algorithms like BFS and DFS.
Every function call in a running program uses the call stack to manage return addresses and local variables. Every time you click the “Back” button in your browser, a stack pops the previous URL. Every print job waits in a queue. These data structures are not just academic — they are woven into the fabric of every computing system.
2Key Definitions
Essential terms for understanding stacks and queues at the university level.
Stack
Ordered list where insertions and deletions occur at one end (the top); LIFO access
Queue
Ordered list where insertions occur at rear and deletions at front; FIFO access
LIFO
Last-In, First-Out — the most recently added element is removed first
FIFO
First-In, First-Out — the earliest added element is removed first
Push
Add an element to the top of a stack
Pop
Remove and return the top element from a stack
Enqueue
Add an element to the rear of a queue
Dequeue
Remove and return the front element from a queue
Peek (Top / Front)
Return the top/front element without removing it
Overflow
Attempting to add to a full fixed-size structure
Underflow
Attempting to remove from an empty structure
Abstract Data Type (ADT)
Defines operations and behavior without specifying implementation
Circular Queue
Array-based queue that wraps indices using modulo to reuse space
Priority Queue
Elements dequeued by priority, not arrival order; often backed by a heap
Deque
Double-ended queue — insert and delete from both front and rear
Amortized O(1)
Average O(1) per operation over a sequence, even if individual ops vary
3The Stack Abstract Data Type
A stack is an ordered collection where all insertions and deletions happen at one end, called the top. It enforces LIFO (Last-In, First-Out) ordering: the most recently added element is the first to be removed. Think of a stack of plates — you always take the top one.
Core Operations
push(item)
Add item to the top of the stack. O(1) time.
Raises Overflow if fixed-size and full.
pop()
Remove and return the top element. O(1) time.
Raises Underflow if empty.
peek() / top()
Return the top element without removing it. O(1) time.
Does not modify the stack.
isEmpty()
Return true if the stack contains no elements. O(1) time.
Always check before pop/peek.
Common Stack Applications
- Function call stack: managing return addresses, local variables, and stack frames
- Expression evaluation: infix-to-postfix conversion, postfix evaluation
- Parentheses matching: checking balanced brackets in code or math expressions
- Undo/Redo: text editors push edits onto a stack for reversal
- Browser history: the “Back” button pops from the history stack
- DFS (Depth-First Search): uses a stack (or recursion, which is implicit stack usage)
4The Queue Abstract Data Type
A queue is an ordered collection where insertions happen at the rear and deletions happen at the front. It enforces FIFO (First-In, First-Out) ordering: the earliest added element is removed first. Think of a waiting line at a store — the first person in line is served first.
Core Operations
enqueue(item)
Add item to the rear of the queue. O(1) time.
Raises Overflow if fixed-size and full.
dequeue()
Remove and return the front element. O(1) time.
Raises Underflow if empty.
peek() / front()
Return the front element without removing it. O(1) time.
Does not modify the queue.
isEmpty()
Return true if the queue contains no elements. O(1) time.
Always check before dequeue/peek.
Common Queue Applications
- OS task scheduling: CPU scheduling, process queues, thread pools
- Print spooling: documents wait in FIFO order to be printed
- BFS (Breadth-First Search): explores graph nodes level by level using a queue
- Network packet buffering: routers queue packets for orderly transmission
- Load balancing: distributing incoming requests among servers in order
- Simulation: modeling waiting lines in banks, hospitals, call centers
5Implementation Strategies
Both stacks and queues can be implemented using arrays or linked lists. Each approach offers different trade-offs in cache performance, memory overhead, and resize behavior.
Array-Based vs. Linked List
Array-Based
- Excellent cache locality (contiguous memory)
- No pointer overhead per element
- Fixed capacity or amortized O(1) resize
- Queue needs circular indexing to avoid O(N) shifts
- Risk of overflow with fixed-size arrays
Linked List-Based
- Dynamic size — grows/shrinks as needed
- True O(1) push/pop without resizing
- Extra memory per node for pointers
- Poor cache locality (scattered nodes)
- Queue needs both head and tail pointers
Complexity Summary
| Operation | Array Stack | LL Stack | Circular Queue | LL Queue |
|---|---|---|---|---|
| Push / Enqueue | O(1)* | O(1) | O(1) | O(1) |
| Pop / Dequeue | O(1) | O(1) | O(1) | O(1) |
| Peek | O(1) | O(1) | O(1) | O(1) |
| Space | O(N) | O(N) | O(N) | O(N) |
* Amortized O(1) for dynamic arrays that resize.
6Queue Variations
While the basic FIFO queue is widely used, several specialized variations address specific requirements in systems and algorithms.
Circular Queue
Treats the underlying array as circular using modulo arithmetic (rear = (rear + 1) % capacity). This reuses freed slots at the front, eliminating the need for costly element shifts.
Applications: OS buffers, network packet handling, CPU scheduling with equal-priority tasks.
Priority Queue
Elements are dequeued by priority, not arrival order. The highest-priority element is always served first. Typically backed by a min-heap or max-heap for O(log N) enqueue/dequeue and O(1) peek.
Applications: Dijkstra's shortest path, Prim's MST, OS task scheduling, event-driven simulations.
Deque (Double-Ended Queue)
Supports insertion and deletion at both ends. Can function as either a stack or a queue. Python's collections.deque is a highly optimized deque implementation.
Applications: Work stealing in parallel computing, sliding window algorithms, browser forward/back navigation.
7Code Walkthroughs
Stack Push & Pop (Python List)
stack = [] stack.append(1) # push 1 stack.append(2) # push 2 stack.append(3) # push 3 print(stack) # [1, 2, 3] val = stack.pop() # pop → 3 print(val) # 3 print(stack) # [1, 2]
Line 2: append() adds to the end (top of stack). O(1) amortized.
Line 7: pop() removes and returns the last element (top). O(1).
Key: Python lists naturally support stack operations with append/pop at the end.
Key insight: Stack follows LIFO — last in (3), first out (3).
Queue with collections.deque
from collections import deque q = deque() q.append(1) # enqueue 1 q.append(2) # enqueue 2 q.append(3) # enqueue 3 print(q) # deque([1, 2, 3]) val = q.popleft() # dequeue → 1 print(val) # 1 print(q) # deque([2, 3])
Line 4: append() adds to the rear. O(1).
Line 9: popleft() removes from the front. O(1) — unlike list.pop(0) which is O(N).
Key: Always use deque for queues in Python, not plain lists.
Key insight: Queue follows FIFO — first in (1), first out (1).
Valid Parentheses (Stack Application)
def is_valid(s: str) -> bool:
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
if not stack or stack.pop() != mapping[char]:
return False
else:
stack.append(char)
return not stack
# Tests
print(is_valid("({[]})")) # True
print(is_valid("([)]")) # FalseLine 3: Maps each closing bracket to its expected opening bracket.
Line 6: When we see a closing bracket, pop and check if it matches. If stack is empty or mismatch, invalid.
Line 9: Opening brackets are pushed onto the stack to wait for their match.
Line 10: At the end, the stack must be empty for all brackets to be matched.
Key insight: The stack naturally tracks nested opening brackets, ensuring they match in LIFO order.
Circular Queue Implementation
class CircularQueue:
def __init__(self, k):
self.k = k
self.q = [None] * k
self.front = self.rear = -1
def enqueue(self, x):
if (self.rear + 1) % self.k == self.front:
return False # Full
elif self.front == -1:
self.front = self.rear = 0
else:
self.rear = (self.rear + 1) % self.k
self.q[self.rear] = x
return True
def dequeue(self):
if self.front == -1:
return None # Empty
val = self.q[self.front]
if self.front == self.rear:
self.front = self.rear = -1
else:
self.front = (self.front + 1) % self.k
return valLine 8: Full check — if the next rear position equals front, the queue is full.
Line 13: (rear + 1) % k wraps the index around to reuse space.
Lines 21–22: When front equals rear, the last element is being removed — reset both to −1.
Line 24: Front advances with modulo to wrap around the array.
Key insight: Modulo arithmetic creates the illusion of an infinite array by wrapping indices around.
8Memory Aids
“A stack of plates in a cafeteria — you always take the top plate (last placed), and add new plates on top.”
“A line at the grocery store — the first person in line is the first to be served. No cutting!”
“LIFO = Last In, First Out (stack). FIFO = First In, First Out (queue). One letter difference, opposite behavior.”
“A roundabout road — when you reach the end of the array, loop back to the beginning with modulo (%).”
“DFS goes deep (stack). BFS goes broad (queue). Deep starts with D like 'down' a stack. Broad starts with B like 'buffer' in a queue.”
“Underflow = taking from an empty well (nothing there). Overflow = pouring into a full glass (no room left).”
9Common Mistakes
Attempting to pop from an empty stack or dequeue from an empty queue causes an Underflow error or crash.
Always call isEmpty() before pop() or dequeue(). Handle the empty case explicitly.
list.pop(0) is O(N) because it shifts all remaining elements left.
Use collections.deque and popleft() for O(1) queue dequeue operations in Python.
Using a stack when a queue is needed (or vice versa) produces incorrect program logic.
Remember: Stack = LIFO (last in, first out). Queue = FIFO (first in, first out). BFS uses a queue; DFS uses a stack.
Mismanaging top, front, or rear indices leads to data corruption or skipped elements.
Be consistent: decide whether top points to the last element or the next available slot, and stick with that convention throughout.
When a linked list queue goes from one element to empty, setting only front = None leaves rear dangling.
When front becomes None after dequeue, always also set rear = None to correctly reflect an empty queue.
Forgetting modulo arithmetic or applying it inconsistently breaks the circular wrapping.
Always use (index + 1) % capacity for both front and rear updates. Use a separate count variable to distinguish full from empty.
peek() inspects without removing; pop()/dequeue() removes the element.
Using peek when removal is intended (or vice versa) is a subtle but common bug. Be deliberate about whether you want to consume the element or just inspect it.
Relying on a fixed-size array without overflow checks causes crashes when capacity is exceeded.
Always check isFull() before insertion, or use a dynamic backing structure that resizes automatically.
Frequently Asked Questions
- Why not just use a dynamic array (like Python's list) for everything?
- While dynamic arrays can mimic stack and queue behavior (append() for push, pop() for stack pop, pop(0) for queue dequeue), list.pop(0) in Python is O(N) because it shifts all subsequent elements. Dedicated implementations or collections.deque are more efficient for queues. Using a specific data structure also clearly communicates intent.
- Which implementation (Array or Linked List) is better for stacks and queues?
- It depends on the use case. Array-based implementations (especially circular for queues) offer better cache locality and less memory overhead per element, ideal for fixed-size requirements. Linked list implementations handle dynamic sizes gracefully with no overflow risk and simpler O(1) operations, but use more memory per element due to pointers.
- Can a Stack be used as a Queue, or vice versa?
- Not directly. However, you can implement queue behavior using two stacks (or stack behavior using two queues). The two-stack queue approach uses one stack for enqueue and another for dequeue, achieving amortized O(1) per operation. This is a classic interview problem.
- What is a Deque, and how does it relate to Stacks and Queues?
- A Deque (Double-Ended Queue) is a generalization of both stacks and queues. It allows insertions and deletions from both the front and the rear. It can function as a stack (using one end for both push/pop) or a queue (using one end for enqueue, the other for dequeue), or both simultaneously.
- Are Stacks and Queues Abstract Data Types (ADTs)?
- Yes. An ADT defines a set of operations and their behavior without specifying how they are implemented. Stacks define push, pop, peek, and isEmpty; queues define enqueue, dequeue, peek, and isEmpty. Array-based and linked-list-based versions are concrete implementations of these ADTs.
- What are real-world applications of Stacks and Queues?
- Stacks are used in compilers (expression parsing), web browsers (back button history), text editors (undo/redo), and recursion (the call stack). Queues are used in OS task scheduling, print spooling, network packet buffering, BFS graph traversal, and load balancing across servers.
Practice Quiz
Test your understanding of stacks and queues — select the correct answer for each question.
1.Which principle does a Stack follow for data access?
2.What is the operation called when an element is added to a Queue?
3.What is the typical time complexity for push and pop operations on a stack implemented with a linked list?
4.Which of the following scenarios is best suited for a Queue?
5.What is the primary advantage of a circular array implementation over a naive array implementation for a Queue?
6.What happens if you try to pop an element from an empty stack?
7.Which data structure is typically used to implement a Priority Queue efficiently?
8.In a linked list based Queue, what pointers are typically maintained to ensure O(1) enqueue and dequeue?
9.A Deque (Double-Ended Queue) allows which of the following operations?
10.Which of the following is a common application of a Stack?
Study Tips
- Trace operations by hand: Draw a stack or queue and step through push/pop or enqueue/dequeue operations on paper. Visualizing the data flow builds deep intuition.
- Implement both ways: Build a stack and queue using both an array and a linked list. Understanding both implementations highlights the trade-offs between cache locality and dynamic sizing.
- Solve classic problems: Practice parentheses matching, reverse a string with a stack, implement BFS with a queue, and build a queue using two stacks.
- Compare DFS vs BFS: Run both on a graph side by side — notice how swapping a stack for a queue changes traversal order from depth-first to breadth-first.