C++ Stacks and Queues (from scratch)

A stack and a queue are two of the most fundamental data structures in computer science. A stack follows LIFO (Last In, First Out) order — think of a stack of plates, where you can only add or remove from the top. A queue follows FIFO (First In, First Out) order — think of a checkout line, where the first person to arrive is the first to be served. Both can be built from scratch using either a plain array or a linked list, and understanding how to build them yourself is essential before you ever reach for std::stack or std::queue from the C++ Standard Library.

Overview: How Stacks and Queues Work

Both stacks and queues are linear data structures — their elements form a sequence — but they restrict where you’re allowed to insert and remove elements. A stack only allows access at one end, called the top. A queue allows insertion at one end (the back, or rear) and removal at the other end (the front).

There are two classic ways to implement either structure under the hood:

• Array-based: elements live in a contiguous block of memory. For a stack, you keep a single integer index (often called top) that tracks the position of the last inserted element; pushing increments the index and writes into the array, popping reads the value and decrements the index. This is extremely fast because it only touches one memory location and needs no pointer chasing, but the array has a fixed capacity unless you write resizing logic.
• Linked-list-based: elements live in separately allocated nodes, each holding a value and a pointer to the next node. A stack keeps a pointer to the head node (push/pop happen there). A queue keeps two pointers — one to the front node and one to the back node — so both ends can be reached in constant time without scanning the whole list. This approach grows and shrinks dynamically with no fixed capacity, at the cost of a small amount of extra memory per element (for the pointer) and a heap allocation (new/delete) on every insert/remove.

Because both operations only ever touch one end (or, for a linked queue, one end each), a correctly implemented stack and queue perform push/pop or enqueue/dequeue in O(1) constant time — no matter how many elements are stored. That constant-time guarantee is the entire point of restricting access to the ends: if you allowed insertion or removal from the middle, you’d need to shift or search through elements, which costs O(n).

In the C++ Standard Library, std::stack and std::queue are not data structures themselves — they are container adapters that wrap an underlying container (by default std::deque) and expose only the restricted stack/queue interface. Building your own version from scratch, as this lesson does, is how you learn what those adapters are doing internally.

Syntax: Building Your Own Stack and Queue

There’s no special C++ keyword for a stack or queue — you define a class with private storage and public methods that enforce the LIFO or FIFO discipline. The general shape looks like this:

class MyStack {
private:
    // storage: array + index, OR linked list head pointer
public:
    void push(int value);   // insert at the top
    int  pop();              // remove and return the top
    int  peek() const;       // look at the top without removing
    bool isEmpty() const;
};

class MyQueue {
private:
    // storage: array + two indices, OR linked list with front/back pointers
public:
    void enqueue(int value); // insert at the back
    int  dequeue();           // remove and return the front
    int  front() const;       // look at the front without removing
    bool isEmpty() const;
};

Operation	Stack	Queue	Complexity
Insert	push(value)	enqueue(value)	O(1)
Remove	pop()	dequeue()	O(1)
Inspect	peek() / top()	front()	O(1)
Check empty	isEmpty()	isEmpty()	O(1)

Examples

Example 1: An Array-Based Stack of Integers

#include <iostream>
using namespace std;

class ArrayStack {
private:
    int data[100];
    int topIndex;

public:
    ArrayStack() : topIndex(-1) {}

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

    bool isFull() const {
        return topIndex == 99;
    }

    void push(int value) {
        if (isFull()) {
            cout << "Stack overflow: cannot push " << value << endl;
            return;
        }
        data[++topIndex] = value;
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack underflow: cannot pop" << endl;
            return -1;
        }
        return data[topIndex--];
    }

    int peek() const {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return -1;
        }
        return data[topIndex];
    }

    int size() const {
        return topIndex + 1;
    }
};

int main() {
    ArrayStack stack;
    stack.push(10);
    stack.push(20);
    stack.push(30);

    cout << "Top element: " << stack.peek() << endl;
    cout << "Stack size: " << stack.size() << endl;

    cout << "Popping elements: ";
    while (!stack.isEmpty()) {
        cout << stack.pop() << " ";
    }
    cout << endl;

    cout << "Is stack empty now? " << (stack.isEmpty() ? "Yes" : "No") << endl;

    return 0;
}

Output:

Top element: 30
Stack size: 3
Popping elements: 30 20 10 
Is stack empty now? Yes

The array stores elements contiguously, and topIndex is the only piece of state that changes on push/pop. Pushing 10, 20, then 30 leaves topIndex at 2, pointing at the 30. Popping always removes the most recently pushed value first — 30, then 20, then 10 — which is exactly the LIFO order the stack guarantees.

Example 2: A Linked-List-Based Queue of Integers

#include <iostream>
using namespace std;

class LinkedQueue {
private:
    struct Node {
        int value;
        Node* next;
    };

    Node* frontNode;
    Node* backNode;
    int count;

public:
    LinkedQueue() : frontNode(nullptr), backNode(nullptr), count(0) {}

    ~LinkedQueue() {
        while (!isEmpty()) {
            dequeue();
        }
    }

    bool isEmpty() const {
        return frontNode == nullptr;
    }

    void enqueue(int value) {
        Node* newNode = new Node{value, nullptr};
        if (isEmpty()) {
            frontNode = newNode;
            backNode = newNode;
        } else {
            backNode->next = newNode;
            backNode = newNode;
        }
        count++;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue underflow: cannot dequeue" << endl;
            return -1;
        }
        Node* temp = frontNode;
        int value = temp->value;
        frontNode = frontNode->next;
        if (frontNode == nullptr) {
            backNode = nullptr;
        }
        delete temp;
        count--;
        return value;
    }

    int front() const {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return -1;
        }
        return frontNode->value;
    }

    int size() const {
        return count;
    }
};

int main() {
    LinkedQueue queue;
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);

    cout << "Front element: " << queue.front() << endl;
    cout << "Queue size: " << queue.size() << endl;

    cout << "Dequeuing elements: ";
    while (!queue.isEmpty()) {
        cout << queue.dequeue() << " ";
    }
    cout << endl;

    return 0;
}

Output:

Front element: 1
Queue size: 3
Dequeuing elements: 1 2 3 

Here, frontNode and backNode let both ends of the queue be reached in O(1) time. enqueue always attaches a new node after backNode and moves backNode forward; dequeue always removes frontNode and moves frontNode forward. Elements come out in the exact order they went in — 1, 2, 3 — which is the FIFO guarantee.

Example 3: A Realistic Use Case — Balanced Parentheses Checker

Stacks are the natural tool for matching nested, paired symbols such as brackets in code, HTML tags, or arithmetic expressions.

#include <iostream>
#include <string>
using namespace std;

class CharStack {
private:
    char data[100];
    int topIndex;

public:
    CharStack() : topIndex(-1) {}

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

    void push(char value) {
        data[++topIndex] = value;
    }

    char pop() {
        return data[topIndex--];
    }
};

bool isBalanced(const string& expression) {
    CharStack stack;

    for (char ch : expression) {
        if (ch == '(' || ch == '[' || ch == '{') {
            stack.push(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.pop();
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{')) {
                return false;
            }
        }
    }

    return stack.isEmpty();
}

int main() {
    string test1 = "{[(a+b)*c]-d}";
    string test2 = "([)]";
    string test3 = "((a+b)";

    cout << test1 << " -> " << (isBalanced(test1) ? "Balanced" : "Not balanced") << endl;
    cout << test2 << " -> " << (isBalanced(test2) ? "Balanced" : "Not balanced") << endl;
    cout << test3 << " -> " << (isBalanced(test3) ? "Balanced" : "Not balanced") << endl;

    return 0;
}

Output:

{[(a+b)*c]-d} -> Balanced
([)] -> Not balanced
((a+b) -> Not balanced

Every opening symbol is pushed. Every closing symbol pops the stack and checks it matches the expected opener. ([)] fails because the ) arrives while a [ is on top, meaning the brackets crossed instead of nesting properly. ((a+b) fails because one ( is left unmatched on the stack when the string ends — exactly the kind of bug a compiler’s parser uses this same technique to catch.

Under the Hood: Step by Step

For the array-based stack, push(30) when topIndex is 1 does two things in order: it increments topIndex to 2, then writes 30 into data[2]. pop() reverses this: it reads data[2] to get the return value, then decrements topIndex back to 1. The old value is never actually erased from the array — it’s simply considered “outside” the valid range once topIndex moves past it, and the next push will silently overwrite it.

For the linked-list queue, enqueue allocates a brand-new Node on the heap via new, links the current backNode‘s next pointer to it, then reassigns backNode to point at the new node. dequeue saves a pointer to the current frontNode, extracts its value, moves frontNode to frontNode->next, and then calls delete on the old node to free its memory — skipping the delete here would leak memory on every dequeue.

It’s worth noting that your CPU and language runtime already use a real stack for something you rely on constantly: the call stack. Every function call pushes a new stack frame (local variables, return address); every return pops it off. That’s precisely why deep, unbounded recursion causes a “stack overflow” — it’s the same LIFO overflow condition you handled explicitly with isFull() above, just happening automatically in hardware.

Common Mistakes

Mistake 1: Popping or Reading the Front Without Checking for Empty

// DANGEROUS: no isEmpty() check before pop()
int topValue = stack.pop();  // if the stack is empty, topIndex is -1,
                              // and this reads data[-1] -- undefined behavior

Reading data[-1] is memory outside the array’s bounds. It may return garbage, corrupt an unrelated variable, or crash — and the failure is often silent until much later, making it hard to trace. Always guard the operation:

if (!stack.isEmpty()) {
    int topValue = stack.pop();
    cout << topValue << endl;
} else {
    cout << "Cannot pop: stack is empty" << endl;
}

Mistake 2: Forgetting to Reset the Back Pointer When a Linked Queue Empties

// BUGGY dequeue(): frontNode is advanced, but backNode is never reset
int dequeue() {
    Node* temp = frontNode;
    int value = temp->value;
    frontNode = frontNode->next;
    delete temp;
    // BUG: if the queue is now empty, backNode still points at
    // the just-deleted node -- a dangling pointer
    return value;
}

If the last node is removed and backNode isn’t reset to nullptr, the next call to enqueue will write through backNode->next, dereferencing a pointer to freed memory. This is a classic dangling-pointer bug. The fix, shown in Example 2, is to check whether the queue became empty and reset backNode too:

int dequeue() {
    Node* temp = frontNode;
    int value = temp->value;
    frontNode = frontNode->next;
    if (frontNode == nullptr) {
        backNode = nullptr;  // queue is now empty -- reset both ends
    }
    delete temp;
    return value;
}

Best Practices

• Always check isEmpty() before pop()/dequeue()/peek()/front() — never assume the structure has elements.
• For array-based implementations, check isFull() before pushing, or use a dynamically resizable array (like std::vector) to avoid a fixed capacity entirely.
• For linked-list implementations, always pair every new with a corresponding delete — implement a destructor that drains the structure to avoid memory leaks.
• Keep the internal representation (array, indices, or pointers) private, and only expose the restricted push/pop or enqueue/dequeue interface — this is what makes the structure a stack or queue rather than just an array or list.
• In real production code, prefer the Standard Library’s std::stack and std::queue (or std::deque/std::vector directly) — write your own from scratch primarily to learn how they work internally.
• Use a stack for problems involving nesting, backtracking, or “undo” history; use a queue for problems involving fair ordering, scheduling, or breadth-first traversal.

Practice Exercises

• Exercise 1: Extend ArrayStack from Example 1 into a StringStack that can push and pop C++ string values, then use it to reverse a sentence word by word.
• Exercise 2: Implement a circular array-based queue (rather than a linked list) that reuses freed array slots by wrapping the front and back indices with the modulo operator, so it doesn’t need to shift elements or grow unbounded.
• Exercise 3: Using two instances of your own stack, implement a queue where enqueue pushes onto stack A, and dequeue pops from stack B (refilling B from A only when B is empty). Verify it produces correct FIFO order for the sequence enqueue(1), enqueue(2), dequeue(), enqueue(3), dequeue(), dequeue().

Summary

• A stack is LIFO (Last In, First Out); a queue is FIFO (First In, First Out).
• Both can be built with a fixed-size array plus index tracking, or with a linked list plus pointer tracking.
• Array-based structures are fast and simple but have a fixed capacity unless you add resizing logic.
• Linked-list-based structures grow dynamically but require careful new/delete management to avoid leaks and dangling pointers.
• All core operations — push/pop, enqueue/dequeue, peek/front — run in O(1) constant time because they only ever touch one end of the structure.
• Always guard against operating on an empty structure; undefined behavior from an unchecked pop/dequeue is one of the most common bugs in hand-rolled implementations.
• The C++ Standard Library’s std::stack and std::queue are container adapters that implement these same ideas — build your own first to understand what they’re doing.