Stack and Queue Fundamentals

A queue follows the First-In-First-Out (FIFO) principle, while a stack follows the Last-In-First-Out (LIFO) principle.

Understanding Stack Implementation in C++

1. Is the C++ stack considered a container?
2. Which STL version does our stack implementation belong to?
3. How is the STL stack implemented?
4. Does the stack provide iterators for traversal?

Stacks and queues in the Standard Template Library (STL) are both data structures. The stack interface includes operations like push and pop, with all elements adhering to the LIFO principle. Consequently, stacks don't support traversal or provide iterators, unlike containers such as set or map.

The stack relies on an underlying container to perform all operations, presenting a uniform interface. The underlying container is pluggable, meaning we can specify which container to use for stack functionality.

In STL, stacks are not classified as containers but rather as container adapters. The internal structure of a stack can be implemented using vector, deque, or list—essentially array or linked list structures.

In the SGI STL implementation, if no underlying container is specified, deque serves as the default for stack implementation. A deque (double-ended queue) can function as a stack by restricting access to one end.

Similarly, queues in SGI STL use deque as the default underlying structure. However, we can also specify list as the underlying container for a queue:

std::queue> customQueue; // Queue with list as underlying container

Therefore, STL queues are also classified as container adapters, not containers.

Implementing a Queue Using Two Stacks

Problem: Implement a queue using two stacks. The queue should support standard operations: push, pop, peek, and empty.

Approach: We need two stacks: one for input and one for output. When pushing elements, we simply add them to the input stack. For popping elements, if the output stack is empty, we transfer all elements from the input stack to the output stack before popping. If the output stack isn't empty, we directly pop from it.

The queue is empty only when both input and output stacks are empty.

Notice that pop() and peek() have similar functionality, allowing for code abstraction.

Implementation

 inputStack;
    stack outputStack;

public:
    CustomQueue() {}

    void push(int value) {
        inputStack.push(value);
    }

    int pop() {
        if (outputStack.empty()) {
            while (!inputStack.empty()) {
                outputStack.push(inputStack.top());
                inputStack.pop();
            }
        }
        
        int result = outputStack.top();
        outputStack.pop();
        return result;
    }

    int peek() {
        if (outputStack.empty()) {
            while (!inputStack.empty()) {
                outputStack.push(inputStack.top());
                inputStack.pop();
            }
        }
        
        return outputStack.top();
    }

    bool isEmpty() {
        return inputStack.empty() && outputStack.empty();
    }
};

Implementing a Stack Using Queues

Problem: Implement a stack using two queues that supports standard stack operations: push, pop, top, and empty.

Approach: While one queue is technically sufficient, we'll first explore the two-queue approach. Since queues maintain FIFO order, transferring elements between queues doesn't change their order. To simulate stack behavior, we use one queue as the primary and another as a backup.

When popping, we move all elements except the last one from the primary queue to the backup queue. The last element in the primary queue is the one we pop. Then we move all elements back from the backup queue to the primary queue.

Two-Queue Implementation

 primaryQueue;
    queue backupQueue;

public:
    CustomStack() {}

    void push(int value) {
        primaryQueue.push(value);
    }

    int pop() {
        int size = primaryQueue.size();
        size--;
        
        while (size--) {
            backupQueue.push(primaryQueue.front());
            primaryQueue.pop();
        }
        
        int result = primaryQueue.front();
        primaryQueue.pop();
        
        // Swap queues
        primaryQueue = backupQueue;
        
        // Clear backup queue
        while (!backupQueue.empty()) {
            backupQueue.pop();
        }
        
        return result;
    }

    int top() {
        return primaryQueue.back();
    }

    bool isEmpty() {
        return primaryQueue.empty();
    }
};

Optimized Single-Queue Implementation

We can optimize the stack implementation using only one queue. When popping, we move all elements except the last one from the front to the back of the queue. The last element will then be at the front, ready to be popped.

 dataQueue;

public:
    OptimizedStack() {}

    void push(int value) {
        dataQueue.push(value);
    }

    int pop() {
        int size = dataQueue.size();
        size--;
        
        while (size--) {
            dataQueue.push(dataQueue.front());
            dataQueue.pop();
        }
        
        int result = dataQueue.front();
        dataQueue.pop();
        return result;
    }

    int top() {
        return dataQueue.back();
    }

    bool isEmpty() {
        return dataQueue.empty();
    }
};