Stacks and Queues

Stacks and queues are linear data structures. The difference is not the shape of the data, but the rule for which item can leave next.

You can read this note directly without first reading the hub. The only Python ideas assumed are lists, indexes, simple classes, and methods. If those are unfamiliar, read Data Types and Collections first.

The Big Idea

A stack or queue is not just “a list of values”. It is a list of values plus a rule about access.

Structure	Access rule	Everyday model	Next item removed
stack	last in, first out	undo history	newest item
queue	first in, first out	service line	oldest item

This access rule is the reason the structure exists. If any item can be removed freely from the middle, the structure is no longer being used as a pure stack or queue.

A good way to study both structures is to ask four questions:

1. Where is a new item added?
2. Where is the next item removed?
3. Which pointer or index identifies that position?
4. What happens if the structure is empty or full?

These questions are often more useful than memorising a definition alone.

Abstract Operation Versus Implementation

A stack or queue is an abstract data type, or ADT. The ADT tells us what operations are allowed and what behaviour they must have.

For example, a stack ADT supports push() and pop(). This does not force the stack to be stored in one particular way. The same stack behaviour can be implemented using:

• a Python list;
• a fixed-size array;
• linked nodes.

Similarly, a queue ADT can be implemented using an array, a circular array, or linked nodes.

In exam questions, always check whether the question is asking about the ADT behaviour or the implementation details.

In pseudocode, <- means assignment: store the value on the right into the variable or field on the left.

Question focus	What to think about
ADT behaviour	Which item is allowed to leave next?
Python list implementation	Which list method is being used?
fixed-size array implementation	Where are top, front, and rear?
circular queue implementation	Does a pointer wrap around using modulo?

Stack: Last In, First Out

A stack follows LIFO order: last in, first out.

Caption: A stack only exposes the top item: after pushing A, B, then C, pop() removes C first.

Example trace:

Operation	Stack after operation	Return value
start	[]
push("A")	["A"]
push("B")	["A", "B"]
push("C")	["A", "B", "C"]
pop()	["A", "B"]	"C"

The invariant is that the top item is always the next item to be removed.

An invariant is a rule that remains true after every valid operation. For a stack, the invariant is simple:

Only the top item is directly removed by pop().

Simple Python Stack

stack = []
 
stack.append("A")
stack.append("B")
stack.append("C")
 
top = stack[-1]
removed = stack.pop()

In this simple Python version:

• append() acts as push;
• pop() removes from the top;
• stack[-1] peeks at the top.

Exam questions may use abstract operations such as push() and pop() even if Python code uses list methods.

Stack Using a Fixed-Size Array

A stack may also be implemented using a fixed-size array. In that case, the array has a fixed capacity, and a top index records where the current top item is.

One common convention is:

• top = -1 means the stack is empty;
• top = 0 means the first array slot is the top;
• top = capacity - 1 means the stack is full.

Caption: In a fixed-size array stack, top identifies the next item returned by pop(); after the pop, top moves to the previous occupied index.

Example with capacity 3:

Step	Operation	Array state	top	Return value	Comment
0	start	[_, _, _]	-1		empty
1	push("A")	[A, _, _]	0		A is top
2	push("B")	[A, B, _]	1		B is top
3	push("C")	[A, B, C]	2		full
4	push("D")	[A, B, C]	2		overflow
5	pop()	[A, B, _]	1	"C"	C removed
6	pop()	[A, _, _]	0	"B"	B removed
7	pop()	[_, _, _]	-1	"A"	A removed
8	pop()	[_, _, _]	-1		underflow

A trace table should show the array after each operation, not only the final answer.

Fixed-Size Stack Pseudocode

Push operation:

Push(item):
    IF top = capacity - 1 THEN
        OUTPUT "Stack overflow"
    ELSE
        top <- top + 1
        stack[top] <- item
    ENDIF

Pop operation:

Pop():
    IF top = -1 THEN
        OUTPUT "Stack underflow"
    ELSE
        item <- stack[top]
        stack[top] <- empty
        top <- top - 1
        RETURN item
    ENDIF

The check must happen before the structure is changed.

Stack Trace Checklist

When tracing a stack, record:

• the current stack contents;
• which side is the top;
• the value of top if an array implementation is used;
• the value returned by pop() or peek();
• whether an operation would cause underflow or overflow.

Example with the top shown on the right:

Step	Operation	Stack state	Explanation
0	start	[]	empty stack
1	push(4)	[4]	4 is now top
2	push(9)	[4, 9]	9 is now top
3	peek()	[4, 9]	returns 9 but does not remove it
4	pop()	[4]	returns and removes 9

Stack Boundary Cases

Underflow happens when a program tries to remove an item from an empty stack.

Overflow happens when a program tries to insert an item into a full fixed-size stack.

Safe stack code checks these cases before changing the structure.

Case	Meaning	Safe response
empty stack and pop()	no item can be removed	report underflow or return an error value
empty stack and peek()	no top item exists	report underflow or return an error value
full fixed-size stack and push()	no empty slot exists	report overflow

A Python list can grow dynamically, so ordinary Python append() does not normally cause fixed-capacity overflow. However, syllabus questions may still ask about fixed-size array implementations.

Queue: First In, First Out

A queue follows FIFO order: first in, first out.

Caption: dequeue() removes from the front and enqueue() adds at the rear; a circular queue reuses earlier array slots by wrapping the rear index.

Example trace:

Operation	Queue after operation	Return value
start	[]
enqueue("A")	["A"]
enqueue("B")	["A", "B"]
enqueue("C")	["A", "B", "C"]
dequeue()	["B", "C"]	"A"

The invariant is that the front item is always the next item to be removed.

For a queue:

• enqueue() adds at the rear;
• dequeue() removes from the front;
• peek() returns the front item without removing it.

Simple Python Queue and Its Limitation

A simple Python list can model a queue like this:

queue = []
 
queue.append("A")      # enqueue
queue.append("B")      # enqueue
removed = queue.pop(0) # dequeue

This is easy to understand, but pop(0) is inefficient for long lists because all later items have to shift left. For syllabus tracing, it is more important to understand front and rear pointers than to rely on pop(0).

Linear Queue

In an array-based linear queue, two positions are tracked:

• front: index of the item to remove next;
• rear: index where the most recent item was added, or where the next item will be added depending on the convention.

This note uses the convention that rear is the index of the most recently added item.

The key trace idea is to record the array, front, and rear after every operation.

Problem with a simple linear queue:

• after several dequeues, earlier array slots become unused;
• if rear has reached the end of the array, the queue may appear full even though there are empty slots at the front.

Trace example:

Step	Operation	Array state	front	rear	Return value
0	start	[_, _, _]	-	-
1	enqueue A	[A, _, _]	0	0
2	enqueue B	[A, B, _]	0	1
3	dequeue	[_, B, _]	1	1	A
4	enqueue C	[_, B, C]	1	2

At step 4, index 0 is empty but a simple linear queue cannot use it unless items are shifted or a circular queue is used.

Linear Queue Pseudocode

One possible fixed-size linear queue convention is:

• an empty queue has front = -1 and rear = -1;
• the first enqueue sets both front and rear to 0;
• rear = capacity - 1 means no more insertion is possible in a simple linear queue.

Enqueue operation:

Enqueue(item):
    IF rear = capacity - 1 THEN
        OUTPUT "Queue overflow"
    ELSE IF front = -1 THEN
        front <- 0
        rear <- 0
        queue[rear] <- item
    ELSE
        rear <- rear + 1
        queue[rear] <- item
    ENDIF

Dequeue operation:

Dequeue():
    IF front = -1 THEN
        OUTPUT "Queue underflow"
    ELSE
        item <- queue[front]
        queue[front] <- empty
        IF front = rear THEN
            front <- -1
            rear <- -1
        ELSE
            front <- front + 1
        ENDIF
        RETURN item
    ENDIF

Different textbooks may use slightly different conventions. Always follow the convention stated in the question.

Circular Queue

A circular queue treats the array as if the end connects back to the start. When a pointer moves past the last index, it wraps to index 0.

For an array of length capacity, a pointer can move using:

next_index = (current_index + 1) % capacity

In mathematical notation:

$$\text{next index}=(\text{current index}+1)\mathrm{mod}\text{capacity}$$

The modulo operation gives the remainder after division by capacity. This is why index 2 wraps to index 0 when the capacity is 3:

$$(2+1)\mathrm{mod}3=0$$

Caption: After wraparound, the physical array order may differ from the logical queue order; front, rear, and modulo arithmetic determine which item is removed next.

Beginner trace with capacity 3:

Step	Operation	Array state	front	rear	Stored items in queue order	Return value
0	start	[_, _, _]	-	-	empty
1	enqueue A	[A, _, _]	0	0	A
2	enqueue B	[A, B, _]	0	1	A, B
3	dequeue	[_, B, _]	1	1	B	A
4	enqueue C	[_, B, C]	1	2	B, C
5	enqueue D	[D, B, C]	1	0	B, C, D

At step 5, rear wraps from index 2 to index 0. The physical array order is [D, B, C], but the queue order is still B, C, D because front = 1.

This is a common beginner trap: array order is not always the same as queue order.

Distinguishing Full and Empty in a Circular Queue

In a circular queue, front == rear can be ambiguous if no extra information is stored.

For example, depending on the implementation, front == rear could mean:

• the queue has one item;
• the queue is empty;
• the queue is full.

To avoid ambiguity, many circular queue implementations use one of these designs:

Design	How it distinguishes full and empty
store size	empty when size = 0; full when size = capacity
leave one slot unused	empty when front catches rear; full when the next rear position would catch front

This note uses the size design in the Python model below because it is easier for beginners to trace.

Circular Queue Python Model

class CircularQueue:
    def __init__(self, capacity):
        self.items = [None] * capacity
        self.front = 0
        self.size = 0
 
    def is_empty(self):
        return self.size == 0
 
    def is_full(self):
        return self.size == len(self.items)
 
    def enqueue(self, value):
        if self.is_full():
            raise IndexError("queue is full")
        rear = (self.front + self.size) % len(self.items)
        self.items[rear] = value
        self.size = self.size + 1
 
    def dequeue(self):
        if self.is_empty():
            raise IndexError("queue is empty")
        value = self.items[self.front]
        self.items[self.front] = None
        self.front = (self.front + 1) % len(self.items)
        self.size = self.size - 1
        return value

This model stores front and size. It calculates the rear position only when adding a new item. Other correct implementations may store both front and rear.

Circular Queue Pseudocode Using front and size

This version matches the Python model above.

IsEmpty():
    RETURN size = 0
 
IsFull():
    RETURN size = capacity

Enqueue operation:

Enqueue(item):
    IF size = capacity THEN
        OUTPUT "Queue overflow"
    ELSE
        rear <- (front + size) MOD capacity
        queue[rear] <- item
        size <- size + 1
    ENDIF

Dequeue operation:

Dequeue():
    IF size = 0 THEN
        OUTPUT "Queue underflow"
    ELSE
        item <- queue[front]
        queue[front] <- empty
        front <- (front + 1) MOD capacity
        size <- size - 1
        RETURN item
    ENDIF

The formula for calculating rear works because front + size points to the next empty position after the current queue contents, and modulo wraps that position back into the array.

Exam Trace Method for Queues

For any queue trace, especially a circular queue, record these after every operation:

• the array contents;
• the value of front;
• the value of rear, if the implementation stores it;
• the value of size, if the implementation stores it;
• the item returned by dequeue() or peek();
• whether the operation causes underflow or overflow.

A useful exam habit is to separate physical array order from logical queue order.

Example:

Array: [D, B, C]
front = 1
Queue order: B, C, D

The next item removed is B, not D.

Comparing Stack, Linear Queue, and Circular Queue

Feature	Stack	Linear queue	Circular queue
Removal rule	newest item first	oldest item first	oldest item first
Main operation pair	push, pop	enqueue, dequeue	enqueue, dequeue
Important pointer/index	top	front, rear	front, rear or size
Empty risk	underflow	underflow	underflow
Full risk in fixed array	overflow	overflow when rear reaches end	overflow only when all usable slots are filled
Special idea	top controls access	unused front slots may appear	modulo wraparound reuses slots

Common Mistakes

• Saying a stack removes the first item added.
• Saying a queue removes the most recent item.
• Calling queue removal pop() without explaining that the front item is removed.
• Forgetting underflow checks.
• Forgetting overflow checks in fixed-size implementations.
• Updating top, front, or rear before checking whether the operation is valid.
• Moving rear in a circular queue without using modulo.
• Treating the physical array order as the queue order after wraparound.
• Assuming front == rear is enough to distinguish full and empty in every circular queue design.
• Not clearing a dequeued array slot when tracing state.

Check Your Understanding

1. After pushing A, B, C, what does pop() return?
2. After enqueueing A, B, C, what does dequeue() return?
3. Why can a circular queue reuse an earlier array slot?
4. What is underflow?
5. In a fixed-size stack of capacity 4, what does top = -1 usually mean?
6. In a circular queue with capacity 5, what is (4 + 1) MOD 5?
7. If a circular queue has array [D, B, C] and front = 1, which item is removed next?

Answers:

1. C.
2. A.
3. The pointer wraps around using modulo once it passes the last index.
4. Trying to remove an item from an empty structure.
5. The stack is empty.
6. 0.
7. B, because the queue order starts at front, not at array index 0.

Related Notes

• Data Structures
• Data Types and Collections