Debugging lab: Python stack and queue bugs

Why this matters

Almost every program that stores work to do later uses a stack or a queue. A stack holds the most recent item on top and gives it back first. A queue holds items in arrival order and gives back the oldest first. Your code will rarely be perfect the first time you write one of these, and most of the bugs are small: a check that is one step off, a pointer that is not updated, a line that is missing.

This lab gives you four broken pieces of code and one error to find. For each one you will see what the code should do, what it actually does, the exact message or wrong result that shows the problem, and the fix. The lab uses only the ideas from the earlier lessons in this module: the stack rule, the queue rule, and how a list or a linked list stores items. It does not teach new algorithms. Each bug is one that beginners really make.

You will get the most from this lesson if you type each program yourself, run it, and try to find the bug before you read the explanation. Running broken code and reading its error is a skill, and it is faster to build by doing.

The method

Before you look at any code, write down three things. This is the same method used by working engineers when they debug a stack or a queue.

1. The rule. For example: "pop removes the top item and returns it. Pop on an empty stack must fail."
2. The state. Which variables hold the data, and what does each one mean? For a stack built on a list with fixed slots, top is the index of the top item, or -1 when the stack is empty.
3. The edge cases. Try the empty case, the one-item case, the full case, and the case after you emptied it. Most stack and queue bugs show up in one of these four cases, not in the middle of normal use.

Then run the code with a small input and compare the real result with the rule. The first place where they differ is the bug.

Python gives you two kinds of clue. An exception is a report that the program hit a problem it could not handle. When nothing catches it, Python stops the program and prints a traceback. A traceback is the list of function calls that were running when the problem happened, with file names and line numbers. Python prints the oldest call first and the newest call last, so read a traceback from the bottom. The last line names the exception and gives a short message. The lines above it show where the problem happened. A wrong result is the other kind of clue. It comes with no error, only an answer that does not match the rule.

If you learned Java first, Python's IndexError plays the part of Java's array index exception, and the traceback plays the part of the stack trace.

The outputs in this lesson come from Python 3.14. Error wording can change between versions, so your messages may differ a little. Programs marked python run need no input. Save one in a file and run it with python3 file.py.

Bug 1: a stack that never reports full

A stack built on a fixed-size list has a capacity, which is the number of slots it has. A stack of capacity 3 can hold three items, in slots with the index 0, 1 and 2. An index is the position number of a slot, counting from 0. The last valid index is always the capacity minus one. A stack that is full must refuse the next push.

A plain Python list grows by itself when you add items, so a list-based stack never reports full. This lesson builds a fixed-size stack on purpose, using [None] * capacity. That expression makes a list with capacity slots, and each slot holds None. None is Python's word for "no value".

The program below wraps each push in try and except. try runs the code inside it. If that code raises an exception, Python jumps to the except block and the program keeps going. Python does not make you catch exceptions the way some languages do, so try is optional. The test uses it so that one failure does not stop the rest of the test.

Here is the code. Read it once and try to find the problem before going on.

The program prints:

pushed 10
pushed 20
pushed 30
push 40: IndexError: list assignment index out of range

The message says the program tried to write to an index that the list does not have. The list has 3 slots, so the valid indexes are 0, 1 and 2. The is_full check never returns True before this point. When top is 2, the test asks whether top equals 3. It does not, so push moves top to 3 and writes to self.data[3]. That slot does not exist, so Python raises the error.

The check should compare with the last index, not with the length. Here is the fix. Only this one line changes:

def is_full(self):
    return self.top == len(self.data) - 1

With that line changed, the same program prints:

pushed 10
pushed 20
pushed 30
push 40: RuntimeError: stack is full

This is the behaviour the rule asks for. The stack refuses the fourth item with a clear message, instead of failing deep inside the list code. Python has no exception type made only for "stack is full", so RuntimeError is used here as a general type for a problem that happens while the program runs.

Here is what the error looks like when nothing catches it. This program is the buggy stack with the try and except removed. The folder part of each File line depends on where you save the file, so it is shortened here to ...:

Traceback (most recent call last):
  File ".../p1_uncaught.py", line 28, in <module>
    stack.push(number)
    ~~~~~~~~~~^^^^^^^^
  File ".../p1_uncaught.py", line 16, in push
    self.data[self.top] = value
    ~~~~~~~~~^^^^^^^^^^
IndexError: list assignment index out of range

Read it from the bottom. The last line is the exception. The line above it, self.data[self.top] = value, is where it happened. The ^ marks show which part of that line failed. Python 3.14 draws them under the failing part of each line.

Notice the pattern. An off-by-one error is a mistake of one, and it is common with indexes. When a test compares with a length, ask yourself whether the value you have is an index or a count. An index runs from 0 to the length minus 1. A count runs from 0 to the length.

Bug 2: a circular queue where full and empty look the same

A circular queue is a queue built on a fixed list. When the rear pointer reaches the end of the list, it wraps back to index 0. A pointer here is just an index variable that marks a position. The queue keeps two of them. front is the index of the oldest item, and rear is the index where the next item will go.

The wrap uses the % operator, which gives the remainder after a division. For a list of 3 slots, (rear + 1) % len(self.data) turns 3 into 0. The index goes 0, 1, 2, 0, 1, and so on.

The problem is that both "empty" and "full" can look the same when you only compare the two pointers. Here is a version that does exactly that:

The first thing to try is the simplest case: one enqueue into an empty queue. The queue is empty, so front and rear are both 0. The is_full test is also true, so the enqueue is refused. The output is:

enqueue 1 into empty queue: RuntimeError: queue is full

A queue that is empty should accept an item. The message says full, which is wrong.

The problem is that two different states give the same pair of numbers. When the queue is empty, front equals rear. When the queue is full, after the rear pointer has wrapped round and caught up with the front, front also equals rear. The two pointers cannot tell the states apart.

There are two common fixes. The one used here keeps a third variable, count, that holds how many items are in the queue. Every enqueue adds one, and every dequeue takes one away. Then the two tests become plain. Here are the changed parts of the class:

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

A program that enqueues 10, 20 and 30, checks that the queue is full, then dequeues one item prints:

fixed queue full after 3: True
dequeue: 10

The other common fix leaves one slot empty, so that the queue is full when (rear + 1) % len(data) equals front. That works too, but it wastes a slot. The counter is easier to read, so it is the version to learn first.

Bug 3: a linked-list queue with a stale tail

A queue can also be built from linked nodes. A node is a small object that holds one value and a next attribute. The next attribute points to the node after it, or to None at the end of the chain. An attribute is a named value stored inside an object, and you reach it with a dot, as in node.value.

The queue keeps two pointers: head for the oldest node, and tail for the newest. A queue with no items has both pointers set to None.

The code below has an enqueue that is correct and a dequeue with a missing step. Read it once, then run it.

The output is:

dequeue: 1
is empty after enqueue 2: True
buggy dequeue: IndexError: queue is empty

The bug is a stale pointer. A stale pointer is a variable that still points at something that no longer belongs to the structure. When the last node is removed, head becomes None, but tail still points at that old node. The next enqueue then checks tail, sees that it is not None, and takes the else branch. It links the new node onto the old one and never sets head. The queue now holds a node that head cannot reach, so is_empty reports True.

The value 2 was added, but the queue reports itself as empty. This kind of bug is hard to spot, because the enqueue looks correct when you read it alone. It only fails after a dequeue has emptied the queue.

The fix is to clear tail in the same step that clears head. The dequeue method changes to this:

def dequeue(self):
    if self.is_empty():
        raise IndexError("queue is empty")
    value = self.head.value
    self.head = self.head.next
    if self.head is None:
        self.tail = None
    return value

Notice that the check says is None, not == None. The word is asks whether two names point at the same object. None is a single object in Python, so is None is the usual test for it.

With the fix in place, the same sequence prints:

dequeue: 1
is empty after enqueue 2: False
dequeue: 2

Think about the rule that each pointer must match the state of the list. After the change, tail is None exactly when head is None. Whenever you write code that changes head or tail, check that the other pointer still matches.

Bug 4: a missed pop in bracket checking

A classic stack exercise is to check whether brackets are balanced. Every opening bracket must be closed by the matching bracket, in the right order. The stack holds the open brackets that are waiting for their partners. When a closing bracket arrives, the top of the stack must be its match, and then that open bracket is finished. It must be removed.

A Python list has no peek method. In this lesson, peek means reading the top item without removing it. The code does that with stack[-1], because a negative index counts from the end of the list, so -1 is the last item. To remove the top item, use stack.pop(), which removes the last item and returns it.

The program below has two functions. The first one, balanced_no_pop, reads the top item with stack[-1] and never removes it. The second one, balanced, uses stack.pop(). The loop at the bottom runs both on five inputs.

Take the simplest balanced input, (). The open bracket is pushed. The closing bracket finds the open bracket on top, and the check passes. But the open bracket is still on the stack, so the last line sees a non-empty stack and returns False. The output for the five inputs is:

buggy balanced("()") = False
fixed balanced("()") = True
buggy balanced("([])") = False
fixed balanced("([])") = True
buggy balanced("(]") = False
fixed balanced("(]") = False
buggy balanced("((") = False
fixed balanced("((") = False
buggy balanced("[()]") = False
fixed balanced("[()]") = True

The fixed function changes one line: stack[-1] becomes stack.pop(). A matched bracket must not be waiting any more, so it has to leave the stack.

The last two inputs in the first group are wrong in a way that happens to match. (] should fail because the brackets do not match, and it does. (( should fail because it has two open brackets and no closing brackets. The buggy version only gives the right answer on those inputs by accident. Always test an input that should pass, not just inputs that should fail. A bug that always returns False would pass every failing test.

Bug 5: popping an empty deque

The last case is an error you will see many times. A deque (short for double-ended queue) is a list-like type from the collections module. It is fast to add or remove items at either end. Here is a short program that calls pop on an empty deque, and also on an empty list for comparison:

The output is:

pop on empty deque: IndexError: pop from an empty deque
pop on empty list: IndexError: pop from empty list
nothing to pop
popped 8

Both messages are short. The name of the exception is clear: there was no item to remove. The fix is to check before the call. A deque or a list is False when it is empty and True when it has at least one item, so if d: is the check. The last part of the program shows that check working: the first if d: finds the deque empty and prints nothing to pop, and after d.append(8) the same test passes and the item is popped.

The same idea shows up in the array stack from bug 1. The pop there has a check before it. If that check were removed, the code would read the slot at index -1, and Python would not raise an error at all. Exercise 1 shows that case.

Common mistakes

Beginners often fix one bug and create another. These checks help you avoid that.

Test the empty case first. Most stack and queue methods have a special case when there is nothing in the structure. Pop, dequeue, peek and the tests that read the front or the top all need it.

Test the full case for fixed-size structures. An array can hold only so much, and an off-by-one error in the full check is the most common mistake in the first bug.

Do not rely on Python to stop at the start of a list. A negative index counts from the end, so data[-1] is the last slot, not an error. In an empty stack, top is -1, and data[top] reads the last slot without any message. Always check for the empty case before you read a slot.

Test the sequence that empties and refills a structure. Bug 3 only appears after a queue has been emptied and then used again. A single enqueue followed by a print will not show it.

Change one thing at a time and run the same test again. If you change three lines and the program still fails, you will not know which change mattered.

Read the traceback from the bottom. The last line says what went wrong. The lines above it say where, and the ^ marks show the failing part of the line.

Do not treat a pointer as correct because it looks right on its own line. Check every place that changes it, as the tail bug shows.

Practice

Try each exercise before you read the answer. You can run the code in this lesson to check your answers.

Exercise 1

The stack below has no check before pop. What does pop return when it is called on an empty stack of capacity 4? Does Python raise an error?

class NoCheck:
    def __init__(self):
        self.data = [None] * 4
        self.top = -1
 
    def push(self, value):
        self.top += 1
        self.data[self.top] = value
 
    def pop(self):
        value = self.data[self.top]
        self.top -= 1
        return value

Show the answer

Python does not raise an error here. pop returns None, and top becomes -2. Running the exercise code with a call to pop, then a push of 7, prints:

pop on empty stack returns: None
top is now: -2
data after push 7: [None, None, None, 7]

Here top starts at -1, so self.data[self.top] reads index -1. Python counts a negative index from the end of the list, so index -1 is the last slot, which is slot 3. The stack has no error message, but its state is wrong. After the push, top goes from -2 to -1, and the value 7 lands in slot 3. The fix is to add if self.top == -1: before the read and raise IndexError("stack is empty"), the same way the bug 1 stack does.

Exercise 2

A circular queue has capacity 3 and uses the fixed version with a count variable. Enqueue 1, 2 and 3. Dequeue once. Enqueue 4. Is the queue full now?

Show the answer

Yes. After three enqueues, count is 3. The dequeue lowers it to 2. The enqueue of 4 raises it back to 3, which equals the capacity. Running this sequence prints:

full after 1,2,3: True
dequeue: 1
full after 2,3,4: True

The front and rear pointers alone could not have answered this question, because they would be equal in both the full and the empty case. The counter answers it directly.

Exercise 3

Explain why balanced("[()]") returns False in the buggy version and True in the fixed version. Use the words pop and peek in your answer.

Show the answer

The buggy version pushes [ and then (. It reads ) and peeks at the top with stack[-1], which finds ( and leaves it on the stack. Then it reads ], and the top is still (, not [. The check open_bracket != "[" is True, so the function returns False. The fixed version calls pop at each closing bracket. The ) removes (, and the ] then sees [ on top and removes it. The stack is empty at the end, so the function returns True. The program prints buggy balanced("[()]") = False and fixed balanced("[()]") = True.

Exercise 4

Trace the buggy ListQueue for this sequence: enqueue 5, enqueue 6, dequeue, dequeue. After the second dequeue, what is the value of tail? What goes wrong with the next enqueue?

Show the answer

After the second dequeue, head is None, but tail still points at the node that holds 6. The next enqueue sees that tail is not None, so it links the new node onto the old node holding 6, and it does not set head. The new item is then invisible to is_empty and dequeue, the same symptom as in bug 3. The fix in the lesson sets tail to None when head becomes None. Running the buggy class on this sequence prints:

tail value after two dequeues: 6
is empty after enqueue 7: True

Exercise 5

A teammate says that is_empty for the linked-list queue could check tail is None instead of head is None. Is this safe with the buggy dequeue? Explain what would happen.

Show the answer

No, not with the buggy dequeue. After one item is enqueued and dequeued, head is None and tail still points at the old node. A check on tail would say the queue is not empty, so the teammate's version would go ahead and read head.value. head is None, and None has no attribute called value, so Python raises an AttributeError. The program for this exercise prints:

tail is None after emptying: False
head is None after emptying: True
tail check, dequeue on empty: AttributeError: 'NoneType' object has no attribute 'value'

With the fix in place, tail is None whenever head is None, so either check would work. Keeping the check on head is still the clearer choice, because head is the pointer that dequeue reads.

Summary

• Compare an index with the last valid index, which is the length minus one, and not with the length.
• An empty test and a full test must be different. A counter is the simplest way to keep them apart.
• When a pointer changes in one method, check the other pointer that depends on it, such as head and tail.
• Use pop to remove a matched item, and stack[-1] only to look at it.
• Python does not stop on a negative index, so check for the empty case before you read a slot.
• Test the empty case, the full case, and a sequence that empties and refills the structure, not only the normal case.