• Stack: Last-In-First-Out (LIFO) structure.
• Queue: First-In-First-Out (FIFO) structure.

Both are container adaptors in C++ STL, not containers themselves. They rely on underlying containers (like deque, vector, or list) to store data, exposing only a restricted interface—no iterators or traversal methods.

Standard Library Implementations

The C++ STL has multiple historical implementations:

• HP STL: The original open-source version.
• P.J. Plauger STL: Proprietary, used in Visual C++.
• SGI STL: Open-source, adopted by GCC; known for high readability and performance.

By default, both std::stack and std::queue use std::deque as they underlying container. A deque is a double-ended queue; by restricting access to one end, it naturally models a stack.

Customizing Underlying Containers

You can explicitly specify the underlying container:

// Stack using vector as base
std::stack<int, std::vector<int>> stackWithVector;

// Queue using list as base
std::queue<int, std::list<int>> queueWithList;

Implementing Queue with Two Stacks

To simulate a queue using two stacks, maintain one for input and one for output. When popping, tarnsfer all elements from input to output if the output is empty.

class MyQueue {
private:
    std::stack<int> input;
    std::stack<int> output;

public:
    void push(int x) {
        input.push(x);
    }

    int pop() {
        if (output.empty()) {
            while (!input.empty()) {
                output.push(input.top());
                input.pop();
            }
        }
        int val = output.top();
        output.pop();
        return val;
    }

    int peek() {
        int val = pop();
        output.push(val);
        return val;
    }

    bool empty() {
        return input.empty() && output.empty();
    }
};

Implementing Stack with Two Queues

To emulate a stack using two queues, move all but the last element from the primary queue to a secondary one, then pop the last element.

class MyStack {
private:
    std::queue<int> q1;
    std::queue<int> q2;

public:
    void push(int x) {
        q1.push(x);
    }

    int pop() {
        while (q1.size() > 1) {
            q2.push(q1.front());
            q1.pop();
        }
        int val = q1.front();
        q1.pop();
        std::swap(q1, q2); // Efficiently transfer remaining elements back
        return val;
    }

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

    bool empty() {
        return q1.empty();
    }
};

Optimized Stack with One Queue

Rotate elements so the newest becomes the front:

class MyStack {
private:
    std::queue<int> q;

public:
    void push(int x) {
        q.push(x);
        // Rotate: move (n-1) elements to the back
        for (int i = 0; i < q.size() - 1; ++i) {
            q.push(q.front());
            q.pop();
        }
    }

    int pop() {
        int val = q.front();
        q.pop();
        return val;
    }

    int top() {
        return q.front();
    }

    bool empty() {
        return q.empty();
    }
};

Valid Parenthsees

Use a stack to match opening and closing brackets. Push the expected closing bracket, and verify on encounter.

bool isValid(std::string s) {
    if (s.length() % 2 != 0) return false;

    std::stack<char> stk;
    for (char c : s) {
        if (c == '(') stk.push(')');
        else if (c == '{') stk.push('}');
        else if (c == '[') stk.push(']');
        else if (stk.empty() || stk.top() != c) return false;
        else stk.pop();
    }
    return stk.empty();
}

Remove Adjacent Duplicates

Use a stack to detect and eliminate consecutive identical characters.

string removeDuplicates(string s) {
    std::string result;
    for (char c : s) {
        if (!result.empty() && result.back() == c) {
            result.pop_back();
        } else {
            result.push_back(c);
        }
    }
    return result;
}

Reverse Polish Notation (Postfix Evaluation)

Process tokens: push numbers, pop two operands when encountering an operator.

int evalRPN(vector<string>& tokens) {
    std::stack<long long> stk;
    for (const string& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            long long b = stk.top(); stk.pop();
            long long a = stk.top(); stk.pop();
            if (token == "+") stk.push(a + b);
            else if (token == "-") stk.push(a - b);
            else if (token == "*") stk.push(a * b);
            else stk.push(a / b);
        } else {
            stk.push(stoll(token));
        }
    }
    return stk.top();
}

Sliding Window Maximum

Use a monotonic deque to maintain indices of elements in descending order. The front always holds the maximum.

class MonotonicQueue {
private:
    std::deque<int> dq;

public:
    void push(int val) {
        while (!dq.empty() && dq.back() < val) {
            dq.pop_back();
        }
        dq.push_back(val);
    }

    void pop(int val) {
        if (!dq.empty() && dq.front() == val) {
            dq.pop_front();
        }
    }

    int front() {
        return dq.front();
    }
};

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    MonotonicQueue mq;
    vector<int> result;

    for (int i = 0; i < k; ++i) {
        mq.push(nums[i]);
    }
    result.push_back(mq.front());

    for (int i = k; i < nums.size(); ++i) {
        mq.pop(nums[i - k]);
        mq.push(nums[i]);
        result.push_back(mq.front());
    }
    return result;
}

Top K Frequent Elements

Use a min-heap of size k to retain the most frequent elements.

struct Compare {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second; // Min-heap by frequency
    }
};

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int n : nums) freq[n]++;

    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;

    for (auto& p : freq) {
        pq.push(p);
        if (pq.size() > k) pq.pop();
    }

    vector<int> result(k);
    for (int i = k - 1; i >= 0; --i) {
        result[i] = pq.top().first;
        pq.pop();
    }
    return result;
}

Memory Layout Notes

Since stacks and queues are adaptors, their underlying containers dictate memory behavior. For example, deque uses segmented storage—non-contiguous blocks—so elements in a stack built on deque are not guaranteed to be contiguous in memory.