A stack is a data structure where the last item added is the first item removed (LIFO — Last In, First Out); a queue is one where the first item added is the first removed (FIFO — First In, First Out). Both are abstract data types that impose a strict access rule on a collection of items.
What is an abstract data type?
Before defining stacks and queues, it helps to understand what makes them abstract. An abstract data type (ADT) defines a collection of data and a set of permitted operations on it — but hides the internal implementation. You can implement a stack using an array or a linked list; the programmer using it just calls push and pop and does not care which. The abstraction lets you swap implementations without breaking the rest of the program.
What is a stack?
A stack works exactly like a pile of plates. You can only add a plate to the top (push) or remove the top plate (pop). You cannot reach into the middle. This LIFO behaviour is not a limitation — it is a deliberate design that makes stacks ideal for problems that need reversal or "remembering where you came from".
Operations:
| Operation | Effect | Analogy |
|---|---|---|
push(item) |
Add item to the top | Place a plate on the pile |
pop() |
Remove and return the top item | Take the top plate off |
peek() |
Return top item without removing | Look at the top plate |
isEmpty() |
True if the stack has no items | Pile is empty? |
Pseudocode trace — pushing then popping:
stack = []
push(stack, 10) → stack = [10]
push(stack, 20) → stack = [10, 20]
push(stack, 30) → stack = [10, 20, 30]
x = pop(stack) → x = 30, stack = [10, 20]
y = pop(stack) → y = 20, stack = [10]
What is a queue?
A queue works like a line of people waiting for a bus. The first person in the line boards first; new arrivals join the back. FIFO order means items are processed in the sequence they arrived — fair and predictable.
Operations:
| Operation | Effect | Analogy |
|---|---|---|
enqueue(item) |
Add item to the back | Join the back of the queue |
dequeue() |
Remove and return the front item | First person boards the bus |
peek() |
Return front item without removing | Check who is at the front |
isEmpty() |
True if the queue has no items | Is the bus stop empty? |
Pseudocode trace — enqueueing and dequeueing:
queue = []
enqueue(queue, "Alice") → queue = ["Alice"]
enqueue(queue, "Bob") → queue = ["Alice", "Bob"]
enqueue(queue, "Carol") → queue = ["Alice", "Bob", "Carol"]
x = dequeue(queue) → x = "Alice", queue = ["Bob", "Carol"]
y = dequeue(queue) → y = "Bob", queue = ["Carol"]
Where are stacks and queues used in real systems?
| Data structure | Real-world uses |
|---|---|
| Stack | Browser back button (visited pages), undo in a text editor, call stack during function calls, checking brackets are balanced in code |
| Queue | Print spooler (jobs printed in order), CPU task scheduling, network packets waiting to be sent, customers in an online checkout |
The browser back button is a classic stack: each page you visit is pushed. Clicking "back" pops the current page and returns to the previous one. The forward button is a second stack of "popped" pages.
What is a call stack and why does it matter?
When a function calls another function, the CPU uses a stack to remember where to return. Each function call pushes a stack frame (containing local variables and the return address) onto the call stack. When the function finishes, the frame is popped and execution resumes at the saved return address.
main() calls functionA()
→ push main's return address
functionA() calls functionB()
→ push functionA's return address
functionB() finishes → pop → return to functionA
functionA() finishes → pop → return to main
If functions keep calling each other without returning (infinite recursion), the stack fills up and causes a stack overflow — a term you may recognise from the famous programmer Q&A site of the same name.
How can a stack be implemented using an array?
You keep an integer pointer called top that records the index of the current top element. Initially top = −1 (empty stack).
Array: [ _ , _ , _ , _ ] top = -1
push(5): Array = [ 5 , _ , _ , _ ] top = 0
push(9): Array = [ 5 , 9 , _ , _ ] top = 1
push(3): Array = [ 5 , 9 , 3 , _ ] top = 2
pop(): return 3, top = 1
pop(): return 9, top = 0
The array itself does not shrink — only top moves. This is efficient: both push and pop are O(1) operations (constant time, regardless of how many items are in the stack).
Frequently asked questions
What is stack overflow in a program?
Stack overflow occurs when so many items are pushed onto the call stack that it exceeds its allocated memory space. The most common cause is runaway recursion — a function that calls itself indefinitely without a valid base case. The operating system detects the overflow and terminates the program with an error rather than letting it corrupt adjacent memory.
Can a queue be implemented using two stacks?
Yes — and this is a classic computer science problem. To enqueue, push onto stack 1. To dequeue, if stack 2 is empty, pop all items from stack 1 and push them onto stack 2 (reversing order); then pop from stack 2. Each item is moved at most twice, so the amortised cost per operation is still O(1). This is sometimes asked at GCSE extension level or A-level.
What is a circular queue?
A circular queue wraps the end of the array back to the beginning, so the space freed by dequeuing items at the front can be reused for new enqueues at the back. Without this, a standard array-based queue would need to shift every remaining element forward after each dequeue — an expensive O(n) operation. Circular queues are used in buffering scenarios such as audio streaming and keyboard input buffers.
What is the difference between a stack and a queue when sorting?
Stacks reverse order (LIFO makes the most recently added item come out first, useful for reversing sequences). Queues preserve order (FIFO processes items in arrival sequence, useful for fair scheduling). Neither structure sorts data — sorting requires additional logic (e.g. a priority queue, which extends a queue by dequeuing the highest-priority item rather than the earliest arrival).
Professor Turing can walk you through stacks and queues with Socratic questions and live pseudocode traces at aitutors.me.