C++ Stacks and Queues (from scratch)

A stack is a data structure where the last value added is the first value removed. A queue is a data structure where the first value added is the first value removed.

C++ provides std::stack and std::queue, but building small versions yourself shows what these rules mean internally.

Stack and Queue Rules

A stack follows LIFO: last in, first out. Think of a stack as values placed on top of one another. You can add to the top, look at the top, and remove from the top.

A queue follows FIFO: first in, first out. Think of a queue as a waiting line. New values join at the back, and values leave from the front.

Structure	Add operation	Remove operation	Order
Stack	push at the top	pop from the top	Newest value first
Queue	enqueue at the back	dequeue from the front	Oldest value first

Array-Based Implementations

The example below uses fixed-size arrays. This keeps the code focused on the data-structure rules instead of dynamic memory. Each operation returns true when it succeeds and false when the structure is full or empty.

#include <iostream>

class IntStack {
private:
    static const int CAPACITY = 5;
    int data[CAPACITY];
    int count;

public:
    IntStack(void) {
        count = 0;
    }

    bool push(int value) {
        if (count == CAPACITY) {
            return false;
        }

        data[count] = value;
        count++;
        return true;
    }

    bool pop(int& value) {
        if (isEmpty()) {
            return false;
        }

        count--;
        value = data[count];
        return true;
    }

    bool peek(int& value) const {
        if (isEmpty()) {
            return false;
        }

        value = data[count - 1];
        return true;
    }

    bool isEmpty(void) const {
        return count == 0;
    }
};

class IntQueue {
private:
    static const int CAPACITY = 5;
    int data[CAPACITY];
    int frontIndex;
    int backIndex;
    int count;

public:
    IntQueue(void) {
        frontIndex = 0;
        backIndex = 0;
        count = 0;
    }

    bool enqueue(int value) {
        if (count == CAPACITY) {
            return false;
        }

        data[backIndex] = value;
        backIndex = (backIndex + 1) % CAPACITY;
        count++;
        return true;
    }

    bool dequeue(int& value) {
        if (isEmpty()) {
            return false;
        }

        value = data[frontIndex];
        frontIndex = (frontIndex + 1) % CAPACITY;
        count--;
        return true;
    }

    bool front(int& value) const {
        if (isEmpty()) {
            return false;
        }

        value = data[frontIndex];
        return true;
    }

    bool back(int& value) const {
        if (isEmpty()) {
            return false;
        }

        int lastIndex = backIndex - 1;
        if (lastIndex < 0) {
            lastIndex = CAPACITY - 1;
        }

        value = data[lastIndex];
        return true;
    }

    bool isEmpty(void) const {
        return count == 0;
    }
};

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

    int value = 0;
    stack.peek(value);
    std::cout << "Stack top: " << value << std::endl;

    while (stack.pop(value)) {
        std::cout << "Stack pop: " << value << std::endl;
    }

    IntQueue queue;
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);

    queue.front(value);
    std::cout << "Queue front: " << value << std::endl;

    queue.back(value);
    std::cout << "Queue back: " << value << std::endl;

    while (queue.dequeue(value)) {
        std::cout << "Queue remove: " << value << std::endl;
    }

    return 0;
}

Output:

Stack top: 30
Stack pop: 30
Stack pop: 20
Stack pop: 10
Queue front: 10
Queue back: 30
Queue remove: 10
Queue remove: 20
Queue remove: 30

How the Stack Works

The stack stores its values in data and uses count to track how many values are currently stored. When push() adds a value, it writes to data[count], then increases count.

When pop() removes a value, it decreases count first. The value at the new top position is copied into the reference parameter named value. This lets pop() return both a success flag and the removed number.

How the Queue Works

The queue uses a circular array. frontIndex points to the next value that should leave. backIndex points to the next empty slot where a new value should be stored.

The expression (backIndex + 1) % CAPACITY wraps the index back to 0 after it reaches the end of the array. The same idea is used when removing values from the front. This avoids shifting all the remaining elements after each removal.

Checking Full and Empty States

Both classes check their state before reading or writing. A stack or queue is empty when count == 0. It is full when count == CAPACITY.

These checks matter because reading from an empty stack or queue would produce an invalid result, and writing past the end of the array would be a serious bug.

Takeaway: a stack controls access from one end for LIFO behavior, while a queue controls access from two ends for FIFO behavior.