Debugging lab: stack and queue bugs

Why this matters

A stack is a pile. You add an item on top and you remove the item on top. A queue is a line. You add an item at the back and you remove the item at the front. Both ideas are simple, so the code looks easy to write. The bugs in it are small too. One wrong number in a full test, or one line that forgets to change a counter, can make the program print wrong answers for many lines before anyone notices.

This lab gives you seven broken pieces of code. Each one has one mistake. For each bug you do four things. You read the code and say what you think it does. You dry-run it on paper, which means following it one line at a time and writing down the value of each variable after each line. You run it and compare the output with your dry run. Then you fix it.

The linked list lab in module 17 covered pointer mistakes in general. This lab uses the same skill on stacks and queues. You do not need the circular queue or deque lessons to follow it, but the ideas match.

Tools and how to run the lab

The examples were built with g++ 15.2.0 on Linux. The options used are these.

• -std=c++20 selects the 2020 version of the C++ language.
• -Wall turns on the common warnings. Read every warning, even if the program still runs.

A second build adds AddressSanitizer. This is a checker that the compiler puts into the program. It watches every memory read and write while the program runs, and it stops at the first bad one, printing where it happened.

g++ -std=c++20 -Wall -g -o buggy buggy.cpp
g++ -std=c++20 -Wall -g -fsanitize=address,undefined -o buggy_asan buggy.cpp
./buggy 1
./buggy_asan 4

The -g option keeps line numbers in the messages, so each message points at a line of your source. Every bug has its own test. Run the program with the test number as the only argument.

Two behaviours of the output are worth knowing before you start.

The first is about bad indexes into std::vector. On the g++ build used here, a bad index stops the program at once with a message that starts with a file path and ends with Assertion ... failed. A different compiler may not check at all and may keep running with wrong data. So if you see a message like this one, the bug is a bad index.

The second is about buffered output. When the output goes to a file or to another program, the C++ library holds the printed lines in a buffer and writes them in larger blocks. If the program stops suddenly, lines still in the buffer are lost. Several of the runs below show this. The lines are missing from the captured output, not from the program.

The shared code

All seven bugs live in one file. Read it through once before you start. The comments that say bug mark the broken lines, so you can find them. In the lab you would not see these comments, but they are here so the explanations can point at them.

#include <cstdlib>
#include <iostream>
#include <vector>
 
struct Node {
    int value;
    Node* next = nullptr;
};
 
// Bugs 1 and 3 live in this array stack.
struct ArrayStack {
    static constexpr int capacity = 3;
    int data[capacity]{};
    int size = 0;
 
    bool isFull() const { return size == capacity - 1; }  // bug 1
    bool push(int x) {
        if (isFull()) return false;
        data[size++] = x;
        return true;
    }
    int pop() {
        return data[size - 1];  // bug 3: size is never reduced
    }
};
 
// Bug 2 lives in this stack, which keeps the index of the top item.
struct TopStack {
    std::vector<int> data = std::vector<int>(3);
    int top = -1;
 
    bool isEmpty() const { return top == 0; }  // bug 2
    void push(int x) { data[++top] = x; }
    int pop() { return data[top--]; }
};
 
// Bug 4: the new node is not linked to the old head.
void pushBroken(Node*& head, int x) {
    Node* n = new Node{x};
    head = n;
}
 
void push(Node*& head, int x) {
    Node* n = new Node{x};
    n->next = head;
    head = n;
}
 
bool pop(Node*& head, int& out) {
    if (head == nullptr) return false;
    out = head->value;
    Node* old = head;
    head = head->next;
    delete old;
    return true;
}
 
// Bug 5: the node is freed on one line and read on the next.
bool popBroken(Node*& head, int& out) {
    if (head == nullptr) return false;
    Node* old = head;
    head = head->next;
    delete old;
    out = old->value;
    return true;
}
 
// Bug 6: a ring of three slots where full and empty look the same.
struct RingQueue {
    static constexpr int capacity = 3;
    int data[capacity]{};
    int front = 0;
    int rear = 0;
 
    bool isEmpty() const { return front == rear; }
    bool isFull() const { return front == rear; }  // bug 6
    bool enqueue(int x) {
        if (isFull()) return false;
        data[rear] = x;
        rear = (rear + 1) % capacity;
        return true;
    }
    bool dequeue(int& out) {
        if (isEmpty()) return false;
        out = data[front];
        front = (front + 1) % capacity;
        return true;
    }
};
 
// Bug 7: tail is not reset when the last node is removed.
struct LinkedQueue {
    Node* head = nullptr;
    Node* tail = nullptr;
 
    void enqueue(int x) {
        Node* n = new Node{x};
        if (tail == nullptr) {
            head = n;
            tail = n;
        } else {
            tail->next = n;
            tail = n;
        }
    }
    bool dequeue(int& out) {
        if (head == nullptr) return false;
        Node* old = head;
        out = old->value;
        head = head->next;
        delete old;
        return true;  // bug 7: tail still points at the deleted node when head is null
    }
};
 
void test1() {
    ArrayStack s;
    for (int x : {1, 2, 3}) {
        std::cout << "push " << x << ": " << (s.push(x) ? "ok" : "refused") << '\n';
    }
    std::cout << "size " << s.size << '\n';
}
 
void test2() {
    TopStack s;
    s.push(7);
    std::cout << "pop " << s.pop() << '\n';
    while (!s.isEmpty()) {
        std::cout << "pop " << s.pop() << '\n';
    }
    std::cout << "done\n";
}
 
void test3() {
    ArrayStack s;
    s.push(1);
    s.push(2);
    std::cout << "pop " << s.pop() << '\n';
    std::cout << "pop " << s.pop() << '\n';
    std::cout << "size " << s.size << '\n';
}
 
void test4() {
    Node* head = nullptr;
    pushBroken(head, 1);
    pushBroken(head, 2);
    pushBroken(head, 3);
    int v = 0;
    while (pop(head, v)) {
        std::cout << "pop " << v << '\n';
    }
    std::cout << "stack is empty\n";
}
 
void test5() {
    Node* head = nullptr;
    push(head, 1);
    int v = 0;
    popBroken(head, v);
    std::cout << "popped " << v << '\n';
}
 
void test6() {
    RingQueue q;
    std::cout << "empty " << q.isEmpty() << " full " << q.isFull() << '\n';
    std::cout << "enqueue 1: " << (q.enqueue(1) ? "ok" : "refused") << '\n';
}
 
void test7() {
    LinkedQueue q;
    q.enqueue(1);
    int v = 0;
    q.dequeue(v);
    std::cout << "dequeued " << v << '\n';
    q.enqueue(2);
    std::cout << "dequeue: " << (q.dequeue(v) ? "ok" : "empty") << '\n';
}
 
int main(int argc, char** argv) {
    int test = argc > 1 ? std::atoi(argv[1]) : 0;
    switch (test) {
        case 1: test1(); break;
        case 2: test2(); break;
        case 3: test3(); break;
        case 4: test4(); break;
        case 5: test5(); break;
        case 6: test6(); break;
        case 7: test7(); break;
        default: std::cout << "usage: buggy 1..7\n"; break;
    }
}

Two parts of this file need a word before the bugs. The struct keyword makes a new type that groups data and functions. A method is a function inside a struct, and you call it with a dot, as in s.push(1). The -> arrow reads a field through a pointer, so head->value means "the value of the node that head points at".

Bug 1: the full test stops one item early

The first test is ./buggy 1. It pushes three numbers onto an array stack. The array has three slots, data[0], data[1] and data[2], so all three numbers should fit.

Here is the full check from the code.

bool isFull() const { return size == capacity - 1; }  // bug 1

Here is the dry run. The variable size counts the items. The test isFull is true when size equals 2.

The dry run says the third push is refused, even though data[2] is empty. Run the program.

./buggy 1

The output is:

push 1: ok
push 2: ok
push 3: refused
size 2

The output matches the dry run. The program holds two items, but the array has room for three. The fix is to make the full test match the array size.

bool isFull() const { return size == capacity; }

With this change, the output for test 1 is push 3: ok and size 3.

The rule to take from this bug is simple. When you write a full test, ask "how many items fit?" and make the test answer with that number. A test that uses capacity - 1 is only correct for a design where one slot is kept empty on purpose. That design is common in circular queues, but this stack does not use it.

Bug 2: the empty test checks the wrong number

The second test is ./buggy 2. The stack in this test keeps top, the index of the top item. An empty stack has no top item, so top is -1. The test should check for -1. The broken code checks for 0, which is the index of the first slot.

bool isEmpty() const { return top == 0; }  // bug 2

The dry run goes like this. Start with top equal to -1. Push 7, so top becomes 0. Pop returns data[0], which is 7, and top becomes -1 again. Now the loop asks isEmpty(). The stack is empty, but the test says top == 0 is false, so the loop body runs and calls pop() again. The pop function reads data[-1], which is not a slot of the array.

Run the program.

./buggy 2

On the g++ build used here, the output is one line from the library check.

/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The message says that an index was not smaller than the size. The index was -1, which becomes a very large number when treated as an unsigned value, so the check fails. The pop 7 line from the first pop is not in the output, because the program stopped before the buffer was written. This is the buffering note from the start of the lab.

The fix is to compare with -1.

bool isEmpty() const { return top == -1; }

With this change the output is pop 7 and then done.

The rule to take from this bug is to write down the value that means "empty" for your own design. Then use exactly that value in every empty test. If a comment says "top is the index of the top item", the empty value is not the index of any slot.

Bug 3: the pop that forgets to remove the item

The third test is ./buggy 3. It pushes two numbers and pops twice. Each pop should remove an item, so the second pop should return the first number.

int pop() {
    return data[size - 1];  // bug 3: size is never reduced
}

The function reads the top item correctly. It never changes size. So the top item stays in the stack after every pop.

The dry run starts with size equal to 2, because two items were pushed. The first pop returns data[1], which is 2. size is still 2. The second pop returns data[1] again, which is 2. Then size is still 2.

Run the program.

./buggy 3

The output is:

pop 2
pop 2
size 2

The second pop 2 is wrong, and the final size 2 shows why. The stack never shrinks. A missed pop is one of the most common stack bugs, and it can hide for a long time, because the top value still looks right on the first pop.

The fix is one line. Reduce the size first, and then read the item that the new size points at.

int pop() {
    return data[--size];
}

The --size part lowers size by one before the read. For a stack of size 2, the top item is at index 1. After the change, size becomes 1 and the function returns data[1]. The index of the top item is always size - 1 after the change, so the read uses the new size. With this fix the output is pop 2, pop 1, and size 0.

Bug 4: a push that loses the rest of the stack

The fourth test is ./buggy 4. It uses a stack made of linked nodes. A linked stack keeps the nodes in a chain. The head pointer points at the top node. Each node has a next pointer that points at the node below it.

When you push a new node, the new node must point at the old head before it becomes the head. The broken push forgets that step.

void pushBroken(Node*& head, int x) {
    Node* n = new Node{x};
    head = n;
}

The Node*& in the function header means that head is a reference to the caller's pointer. So head = n changes the head in test4. The new Node{x} line creates a node on the heap, which is memory that lasts until the program deletes it. The next field of the new node starts as nullptr, which means "nothing below me". The broken code never changes that.

Here is the dry run for three pushes. Each row shows where the head points and what is reachable from it.

Run the program.

./buggy 4

The output is:

pop 3
stack is empty

The program pops only the last value pushed. The values 1 and 2 are still in memory, but no pointer leads to them. This is a memory leak. A leak is memory that the program has allocated and can no longer reach, so it cannot free it.

The fix is to link the new node before the head moves.

void pushBroken(Node*& head, int x) {
    Node* n = new Node{x};
    n->next = head;
    head = n;
}

Now the output is pop 3, pop 2, pop 1, and stack is empty.

The leak is easier to see under AddressSanitizer. The leak check runs when the program ends, and it lists every block of memory that is still allocated but not reachable. Here is the report from the buggy program, with the paths and the memory addresses shortened.

=================================================================
==199603==ERROR: LeakSanitizer: detected memory leaks
 
Direct leak of 16 byte(s) in 1 object(s) allocated from:
    #0 ... in operator new(unsigned long) ...
    #1 ... in pushBroken(Node*&, int) buggy.cpp:39
    #2 ... in test4() buggy.cpp:146
    ...
 
Direct leak of 16 byte(s) in 1 object(s) allocated from:
    #0 ... in operator new(unsigned long) ...
    #1 ... in pushBroken(Node*&, int) buggy.cpp:39
    #2 ... in test4() buggy.cpp:145
    ...
 
SUMMARY: AddressSanitizer: 32 byte(s) leaked in 2 allocation(s).

The report names line 39 of buggy.cpp as the place where each leaked node was created. The pop 3 and stack is empty lines are missing from this captured run, because the leak check ends the program before the buffer is written. The plain run in the previous step shows those lines.

Bug 5: reading a node after it is freed

The fifth test is ./buggy 5. It pushes one number and pops it with a broken function. The function frees the node, which means it gives the memory back to the system, and then it reads the value from the freed node.

bool popBroken(Node*& head, int& out) {
    if (head == nullptr) return false;
    Node* old = head;
    head = head->next;
    delete old;
    out = old->value;  // reads memory that was just freed
    return true;
}

The delete line gives the node back to the allocator. After that the pointer old still holds the address, but the memory there no longer belongs to the node. Reading it is a bug called use after free. The value you get back can be the old number, a number written by something else, or any other value.

Run the program without the sanitizer first.

./buggy 5

The output is:

popped 2006081140

The value 1 was pushed, but the program prints a random-looking number. This is the freed memory being reused. The number changes between machines and between runs, so you cannot rely on it being right.

Now run the sanitizer build.

./buggy_asan 5

The first lines of the report say what happened. The paths and addresses are shortened.

==199611==ERROR: AddressSanitizer: heap-use-after-free on address 0x7322f61e0010
READ of size 4 at 0x7322f61e0010 thread T0
    #0 ... in popBroken(Node*&, int&) buggy.cpp:64
    #1 ... in test5() buggy.cpp:159
    ...
freed by thread T0 here:
    #0 ... in operator delete(void*, unsigned long) ...
    #1 ... in popBroken(Node*&, int&) buggy.cpp:63
    ...
previously allocated by thread T0 here:
    #0 ... in operator new(unsigned long) ...
    #1 ... in push(Node*&, int) buggy.cpp:44
    ...
SUMMARY: AddressSanitizer: heap-use-after-free buggy.cpp:64 in popBroken(Node*&, int&)

The report gives three places. The read is on line 64. The free is on line 63. The allocation is on line 44 in push. Use the three places together to find the bug. The fix is to copy the value out before the node is freed.

bool popBroken(Node*& head, int& out) {
    if (head == nullptr) return false;
    out = head->value;
    Node* old = head;
    head = head->next;
    delete old;
    return true;
}

With this change the output is popped 1, both in the plain run and under the sanitizer.

The rule is to read everything you need from a node before you free it. Once delete runs, treat the node as gone.

Bug 6: full and empty look the same

The sixth test is ./buggy 6. The queue is a ring of three slots. The variable front is the index of the next item to remove. The variable rear is the index of the next free slot. When items are added, rear moves forward. When items are removed, front moves forward. Both wrap around to 0 after the last slot, which is why it is called a ring. The % operator, called modulo, does the wrapping. (rear + 1) % capacity is 0 when rear is 2.

The problem is that the two tests use the same comparison.

bool isEmpty() const { return front == rear; }
bool isFull() const { return front == rear; }  // bug 6

When the queue is empty, front equals rear. When the queue is full, front also equals rear after the last slot is used. The two states give the same numbers. The program cannot tell them apart.

Run the program.

./buggy 6

The output is:

empty 1 full 1
enqueue 1: refused

The output says the queue is both empty and full at the start. The program refuses to add a number to an empty queue, which is wrong.

The clean fix is to keep a count of the items. Then the two tests have separate numbers to look at.

struct RingQueue {
    static constexpr int capacity = 3;
    int data[capacity]{};
    int front = 0;
    int rear = 0;
    int count = 0;
 
    bool isEmpty() const { return count == 0; }
    bool isFull() const { return count == capacity; }
    bool enqueue(int x) {
        if (isFull()) return false;
        data[rear] = x;
        rear = (rear + 1) % capacity;
        ++count;
        return true;
    }
    bool dequeue(int& out) {
        if (isEmpty()) return false;
        out = data[front];
        front = (front + 1) % capacity;
        --count;
        return true;
    }
};

The enqueue and dequeue functions change count on every successful call. With this fix the output is empty 1 full 0 and enqueue 1: ok.

Another design keeps one slot empty on purpose, so that front and rear never meet when the queue is full. That design works, but the count is easier to read. Pick one design and write the full and empty tests to match it.

Bug 7: the tail pointer is left behind

The seventh test is ./buggy 7. It uses a queue made of linked nodes. The queue has two pointers. The head points at the oldest node, which is the next one to remove. The tail points at the newest node, where new items go. Adding an item links it after tail. Removing an item moves head forward.

The broken dequeue frees the node and does not update tail when the last node is removed.

bool dequeue(int& out) {
    if (head == nullptr) return false;
    Node* old = head;
    out = old->value;
    head = head->next;
    delete old;
    return true;  // tail still points at the deleted node when head is null
}

The dry run follows the two pointers.

Run the program.

./buggy 7

The output is:

dequeued 1
dequeue: empty

The program just added the number 2, but dequeue says the queue is empty. The link to the new node was written into freed memory, so head never reaches it.

Run the sanitizer build to see the exact line.

./buggy_asan 7

The report names the write and the place where the node was freed.

==199615==ERROR: AddressSanitizer: heap-use-after-free on address 0x7713083e0018
WRITE of size 8 at 0x7713083e0018 thread T0
    #0 ... in LinkedQueue::enqueue(int) buggy.cpp:102
    #1 ... in test7() buggy.cpp:175
    ...
freed by thread T0 here:
    #0 ... in operator delete(void*, unsigned long) ...
    #1 ... in LinkedQueue::dequeue(int&) buggy.cpp:111
    ...
previously allocated by thread T0 here:
    #0 ... in operator new(unsigned long) ...
    #1 ... in LinkedQueue::enqueue(int) buggy.cpp:97
    ...
SUMMARY: AddressSanitizer: heap-use-after-free buggy.cpp:102 in LinkedQueue::enqueue(int)

Line 102 is tail->next = n;. The write goes to the freed node. The fix is to set tail to nullptr when the last node goes away.

bool dequeue(int& out) {
    if (head == nullptr) return false;
    Node* old = head;
    out = old->value;
    head = head->next;
    delete old;
    if (head == nullptr) tail = nullptr;
    return true;
}

Now enqueue sees tail == nullptr and sets both head and tail to the new node. With this change the output is dequeued 1 and dequeue: ok.

The rule is that the two pointers must agree. When head becomes nullptr, tail must also become nullptr. Check every function that removes a node for this.

The fixed program

Every fix above is a change to one or two lines. Here is the list of changes, one per bug.

Each change is local. You can apply them one at a time and run the matching test after each one. That habit is faster than fixing all seven at once and then searching for the new bug that you added.

Common mistakes

The seven bugs above are not the only ways to go wrong with stacks and queues. These two mistakes often show up when you use the standard library.

Using the return value of std::stack::pop

In std::stack, top() returns the top item and pop() removes it. pop() returns nothing. Code that expects a value from pop() does not compile.

#include <iostream>
#include <stack>
 
int main() {
    std::stack<int> s;
    s.push(4);
    int top = s.pop();
    std::cout << top << '\n';
}

The compiler reports this error.

voidpop.cpp: In function ‘int main()’:
voidpop.cpp:7:20: error: void value not ignored as it ought to be
    7 |     int top = s.pop();
      |               ~~~~~^~

The fix is two lines: read top() first, then call pop(). The compiler error is a good error, because it stops the program before it runs with a wrong value.

Popping from an empty std::vector

A std::vector can be used as a stack with push_back and pop_back. Calling pop_back on an empty vector is a bug. The library checks for it on this build and stops the program.

/usr/include/c++/15/bits/stl_vector.h:1459: constexpr void std::vector<_Tp, _Alloc>::pop_back() [with _Tp = int; _Alloc = std::allocator<int>]: Assertion '!this->empty()' failed.

The fix is the same as the empty test in bug 2. Check empty() before every pop_back.

Practice

Exercise 1

Bug 1 has a full test that stops at capacity - 1. Suppose the array has four slots instead of three, and the test is still size == capacity - 1. How many pushes succeed before the first refusal?

Show the answer.

Answer: three. The full test is true when size is 3, so the fourth push is refused. Three items are stored, and one slot is left empty.

Exercise 2

Bug 4 pushes three values with the broken push. How many nodes are leaked? Use the leak report from that section to check your answer.

Show the answer.

Answer: two. Only the last node pushed (value 3) is reachable from head. Nodes 1 and 2 are not reachable, so they leak. The report says 32 byte(s) leaked in 2 allocation(s), which is two nodes of 16 bytes each.

Exercise 3

In LinkedQueue::dequeue, the fix sets tail = nullptr only when head == nullptr. Why is it not right to set tail to nullptr on every dequeue?

Show the answer.

Answer: when head is not null, the queue still has at least one node, and the last of those nodes is still the tail. Setting tail to nullptr would make the next enqueue start a new list and lose the nodes that are still waiting. The if statement changes tail only when the queue becomes empty.

Exercise 4

Write a peek method for ArrayStack from bug 3. It should return the top value without removing it. It should return false and leave out alone when the stack is empty.

Show the answer.

Answer:

bool peek(int& out) const {
    if (size == 0) return false;
    out = data[size - 1];
    return true;
}

The method does not change size, which is why it is marked const. The check for size == 0 comes first, so the read never uses index -1.

Exercise 5

Use the fixed ArrayStack from the section on bug 1, with the full test corrected but the pop fix from bug 3 not applied. Push 1, 2 and 3, then pop twice and print the size. Predict the three output lines before you run the program.

Show the answer.

Answer:

pop 3
pop 3
size 3

The three pushes all succeed, because the full test is now size == capacity. Without the --size change, pop reads data[size - 1], which is data[2] for each call, so both pops return 3. size stays 3.

Summary

• Check each full test and empty test against the number of slots or the value that means empty in your design.
• A pop must reduce the size or move the top pointer, or the item stays in the stack.
• Link a new node to the old head before the head moves, or the rest of the stack is lost.
• Read everything you need from a node before you free it.
• In a linked queue, set the tail to nullptr when the last node is removed.
• Use AddressSanitizer and read the report from top to bottom, because its three sections show the bad access, the free and the allocation.