Stack and Queue in C++ STL

The C++ Standard Library provides implementations of both stack and queue data structures. These are fundamental containers that follow specific access orders—LIFO (Last In, First Out) for stacks and FIFO (First In, First Out) for queues.

Stack Interface

• push(element): Inserts an element at the top
• pop(): Removes the top element
• top(): Returns a reference to the top element
• empty(): Checks whether the container is empty
• size(): Returns the number of elements

Queue Interface

• empty(): Checks whether the container is empty
• size(): Returns the number of elements
• front(): Returns reference to the first element
• back(): Returns reference to the last element
• push(element): Inserts element at the back
• pop(): Removes the first element

232. Implement Queue using Stacks

This problem requires simulating queue behavior using two stacks. The key insight is that one stack handles input while the other handles output, transferring elements only when the output stack is empty.

class QueueUsingStacks {
public:
    stack<int> input;
    stack<int> output;
    
    void enqueue(int val) {
        input.push(val);
    }
    
    int dequeue() {
        if (output.empty()) {
            while (!input.empty()) {
                output.push(input.top());
                input.pop();
            }
        }
        int result = output.top();
        output.pop();
        return result;
    }
    
    int front() {
        if (output.empty()) {
            while (!input.empty()) {
                output.push(input.top());
                input.pop();
            }
        }
        return output.top();
    }
    
    bool isEmpty() {
        return input.empty() && output.empty();
    }
};

225. Implement Stack using Queues

To implement stack operations using a single queue, rotate elements during each push operation so the most recently added element always reaches the front.

class StackUsingQueue {
public:
    queue<int> data;
    
    void push(int val) {
        data.push(val);
        // Rotate the queue to bring the new element to front
        for (int i = 0; i < data.size() - 1; i++) {
            data.push(data.front());
            data.pop();
        }
    }
    
    int pop() {
        int topVal = data.front();
        data.pop();
        return topVal;
    }
    
    int peek() {
        return data.front();
    }
    
    bool empty() {
        return data.empty();
    }
};

20. Valid Parentheses

This classic problem uses a stack to verify bracket matching. Each opening bracket is pushed onto the stack, and when a closing bracket is encountered, it must match the top element.

class BracketValidator {
public:
    bool isValid(string expr) {
        if (expr.length() % 2 != 0) return false;
        
        stack<char> store;
        for (char c : expr) {
            if (c == '(' || c == '[' || c == '{') {
                store.push(c);
            } else {
                if (store.empty()) return false;
                
                char top = store.top();
                bool matches = (c == ')' && top == '(') ||
                               (c == ']' && top == '[') ||
                               (c == '}' && top == '{');
                
                if (matches) {
                    store.pop();
                } else {
                    return false;
                }
            }
        }
        return store.empty();
    }
};

Alternative approach: Push the expected closing bracket instead of the opening bracket, then simply check for equality.

class BracketValidatorOptimized {
public:
    bool isValid(string expr) {
        if (expr.length() % 2 != 0) return false;
        
        stack<char> store;
        for (char c : expr) {
            if (c == '(') store.push(')');
            else if (c == '{') store.push('}');
            else if (c == '[') store.push(']');
            else if (store.empty() || store.top() != c) return false;
            else store.pop();
        }
        return store.empty();
    }
};

1047. Remove All Adjacent Duplicates

Given a string, repeatedly remove pairs of adjacent identical characters. This can be efficiently solved using a stack—the top of the stack holds the most recent non-removed character.

class DuplicateRemover {
public:
    string removeDuplicates(string str) {
        stack<char> buffer;
        
        for (char ch : str) {
            if (buffer.empty() || buffer.top() != ch) {
                buffer.push(ch);
            } else {
                buffer.pop();
            }
        }
        
        string result;
        while (!buffer.empty()) {
            result.push_back(buffer.top());
            buffer.pop();
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

Optimized solution using the string itself as a stack:

class DuplicateRemoverOptimized {
public:
    string removeDuplicates(string str) {
        string buffer;
        
        for (char ch : str) {
            if (buffer.empty() || buffer.back() != ch) {
                buffer.push_back(ch);
            } else {
                buffer.pop_back();
            }
        }
        return buffer;
    }
};