Implementing Stacks and Queues

This note focuses on writing stack and queue code. For the ADT concepts, see Stacks and Queues.

You can read this note directly if you know Python classes, lists, methods, and raise. The key beginner habit is to track both the stored values and the control variables such as front, size, or the top position.

Caption: The stored values and control variables together determine the logical stack or queue state.

What You Are Implementing

A stack or queue is not just a list of values. It is a structure with rules about which value can be removed next.

Structure	Removal rule	Everyday idea	Common operations
stack	last in, first out	pile of trays	push, pop, peek
queue	first in, first out	waiting line	enqueue, dequeue

The code must preserve the rule after every operation. A program that stores the right values but removes the wrong value is still incorrect.

Implementation Vocabulary

Word	Meaning in code
state	the values currently stored inside the object
method	a function that belongs to the object
underflow	trying to remove from an empty structure
overflow	trying to add to a full fixed-size structure
invariant	a rule that should remain true after every operation

Three Levels of Thinking

When reading or writing stack and queue code, keep three levels separate.

Level	Question to ask	Example
ADT idea	Which value should leave next?	A stack removes the most recently pushed value.
Python representation	Which attributes store the state?	self.items, self.front, self.size
Implementation trace	Which variable changes after this operation?	after dequeue(), front moves to the next position

This matters because beginners often know the ADT rule but lose marks when they update the implementation state incorrectly.

Stack Using a Python List

A simple Python implementation can use the end of a list as the top of the stack.

class Stack:
    def __init__(self):
        self.items = []
 
    def is_empty(self):
        return len(self.items) == 0
 
    def push(self, value):
        self.items.append(value)
 
    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.items.pop()
 
    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.items[-1]

Why the List End Is Used as the Top

In this implementation:

bottom of stack                  top of stack
      ↓                              ↓
[    "A",          "B",            "C"    ]

The top item is self.items[-1]. Therefore:

• push(value) uses append(value) to add at the top;
• pop() uses pop() to remove from the top;
• peek() returns self.items[-1] without removing it.

Stack invariant:

If the stack is not empty, the top item is self.items[-1].

Code Reading

Line	Purpose
self.items = []	starts with an empty stack
self.items.append(value)	places the new value on top
if self.is_empty():	prevents underflow
return self.items.pop()	removes and returns the top item
return self.items[-1]	returns the top item without changing the stack

Stack Trace

Operation	items	Return value	Explanation
start	[]		empty stack
push("A")	["A"]		"A" is now top
push("B")	["A", "B"]		"B" is now top
peek()	["A", "B"]	"B"	top is returned but not removed
pop()	["A"]	"B"	last pushed item leaves first
pop()	[]	"A"	stack becomes empty

Stack Tests

stack = Stack()
assert stack.is_empty()
 
stack.push("A")
stack.push("B")
assert stack.peek() == "B"
assert stack.pop() == "B"
assert stack.pop() == "A"
assert stack.is_empty()

Underflow should also be tested. The following test expects an IndexError:

stack = Stack()
try:
    stack.pop()
    assert False          # this line should not run
except IndexError:
    pass                  # expected error

Linear Queue Using a Python List

A queue removes the item that has been waiting the longest.

This simple version uses:

• the front of the list as the front of the queue;
• the end of the list as the rear of the queue.

class LinearQueue:
    def __init__(self):
        self.items = []
 
    def is_empty(self):
        return len(self.items) == 0
 
    def enqueue(self, value):
        self.items.append(value)
 
    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self.items.pop(0)

This version is easy to understand but inefficient for large queues because pop(0) shifts all later items one position left.

For syllabus tracing, a fixed-size array model is often more important than this simple Python list model.

Queue invariant:

The next item to leave is at the front of the queue.

Linear Queue Trace

Operation	items	Return value	Explanation
start	[]		empty queue
enqueue("A")	["A"]		"A" is at the front and rear
enqueue("B")	["A", "B"]		"B" joins at the rear
dequeue()	["B"]	"A"	first item leaves first
dequeue()	[]	"B"	queue becomes empty

Linear Queue Tests

queue = LinearQueue()
assert queue.is_empty()
 
queue.enqueue("A")
queue.enqueue("B")
assert queue.dequeue() == "A"
assert queue.dequeue() == "B"
assert queue.is_empty()

Underflow test:

queue = LinearQueue()
try:
    queue.dequeue()
    assert False
except IndexError:
    pass

Fixed-Size Queue Thinking

Some exam-style implementations use a fixed-size array. In that model, the queue has a maximum capacity.

This adds two possible error conditions:

Situation	Meaning
underflow	trying to dequeue() from an empty queue
overflow	trying to enqueue() into a full queue

A fixed-size queue must check overflow before adding a new item. Without this check, the program may overwrite existing queue values or move control variables into an invalid state.

Circular Queue

A circular queue uses a fixed-size list and wraps around when it reaches the end of the array.

The important idea is that the physical array does not move. Only the control values change.

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("enqueue into full queue")
        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("dequeue from empty queue")
        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

Representation

Attribute	Meaning
self.items	fixed-size array storing the queue values
self.front	index of the next value to leave
self.size	number of values currently in the queue

The rear position is calculated when needed:

$$rear=(front+size)\mathrm{mod}capacity$$

In Python, this is written as:

rear = (self.front + self.size) % len(self.items)

The modulo operator % wraps the index back to 0 when it reaches the end of the array.

Circular Queue Invariant

The logical queue contains size items, starting at front and moving right with wrap-around.

This is the most important sentence in the circular queue implementation.

The array display may not match the logical queue order after wrap-around.

Circular Queue Trace

Operation	items	front	size	Logical queue
start	[None, None, None]	0	0	empty
enqueue A	["A", None, None]	0	1	A
enqueue B	["A", "B", None]	0	2	A, B
dequeue	[None, "B", None]	1	1	B
enqueue C	[None, "B", "C"]	1	2	B, C
enqueue D	["D", "B", "C"]	1	3	B, C, D

The final enqueue wraps to index 0. The physical array is:

["D", "B", "C"]

but the logical queue order is:

B, C, D

because front = 1.

Code Reading for enqueue()

Line	Purpose
if self.is_full():	prevents overflow
rear = (self.front + self.size) % len(self.items)	finds the next free rear position
self.items[rear] = value	stores the new value
self.size = self.size + 1	records that one more item is in the queue

Code Reading for dequeue()

Line	Purpose
if self.is_empty():	prevents underflow
value = self.items[self.front]	saves the value before clearing the slot
self.items[self.front] = None	clears the old front position
self.front = (self.front + 1) % len(self.items)	moves the front with wrap-around
self.size = self.size - 1	records that one item has left
return value	gives back the dequeued item

Why size Is Useful

Some circular queue designs use both front and rear. In those designs, it can be tricky to tell whether the queue is empty or full.

This implementation uses size, so the checks are direct:

self.size == 0                 # empty
self.size == len(self.items)   # full

The same size value also helps calculate the next rear position.

Exam questions may instead give three control variables: front, rear, and count. In that convention, count is used for the empty and full checks, while rear usually stores the index of the most recently enqueued item. The next insertion position is then:

rear = (rear + 1) % capacity

Both designs use the same idea: modulo arithmetic keeps the array circular, and the control variables define the logical queue order.

Circular Queue Tests

queue = CircularQueue(3)
assert queue.is_empty()
 
queue.enqueue("A")
queue.enqueue("B")
assert queue.dequeue() == "A"
 
queue.enqueue("C")
queue.enqueue("D")
assert queue.is_full()
 
assert queue.dequeue() == "B"
assert queue.dequeue() == "C"
assert queue.dequeue() == "D"
assert queue.is_empty()

Overflow test:

queue = CircularQueue(2)
queue.enqueue("A")
queue.enqueue("B")
try:
    queue.enqueue("C")
    assert False
except IndexError:
    pass

Underflow test:

queue = CircularQueue(2)
try:
    queue.dequeue()
    assert False
except IndexError:
    pass

How to Explain This in an Exam

For stack code, explain:

The top of the stack is stored at the end of the Python list, so push appends and pop removes the last item.

For queue code, explain:

A queue removes the item at the front, so enqueue adds at the rear and dequeue removes from the front.

For circular queue code, explain:

The array does not rotate. The front index and size describe the logical queue order. Modulo arithmetic wraps indexes back to the start.

Mini Debugging Table

Symptom	Likely cause	Fix
pop() crashes on an empty stack	missing underflow check	check is_empty() before removing
peek() removes the top item	used pop() instead of indexing	return self.items[-1]
queue removes the newest item first	implemented stack behaviour by mistake	remove from the front, not the rear
queue overwrites old values	forgot overflow check	check is_full() before enqueue
dequeue() returns the wrong item after wrap-around	confused array position with logical queue order	trace from front for size items
queue never becomes empty	forgot to decrease size	subtract 1 after successful dequeue()
enqueue skips slots	wrong rear formula	use (front + size) % capacity
dequeued value is lost	cleared slot before saving value	save value before setting slot to None

Common Mistakes

• Forgetting underflow checks.
• Forgetting overflow checks in a fixed-size queue.
• Updating front before saving the dequeued value.
• Calculating rear without modulo.
• Confusing list position with logical queue order after wrap-around.
• Thinking that a circular queue physically rotates the array.
• Forgetting to update size after enqueue or dequeue.
• Testing only the normal case and not the empty or full case.

Check Your Understanding

1. What does peek() do that pop() does not?
2. Why does dequeue() save value before clearing the front slot?
3. In the circular queue implementation, what does size help distinguish?
4. If front = 1, size = 3, and the array is ["D", "B", "C"], which value leaves next?
5. Why does the circular queue use % len(self.items) when moving an index?
6. Why is the array display not always the same as the logical queue order?

Answers:

1. It returns the top item without removing it.
2. The value would be lost after the slot is cleared.
3. Empty and full states, and the position of the next rear slot.
4. "B".
5. It wraps the index from the end of the array back to the start.
6. After wrap-around, the logical queue starts at front, not necessarily at array index 0.

Related Notes

• Implementing Algorithms and Data Structures
• Stacks and Queues