Queue from Two Stacks

Algorithm

The replay uses the same three values in every language, so this C++ DSA implementation can be compared directly with the rest of the DSA track.

input stack Enqueue pushes new values onto the input stack.

output stack When the output stack is empty, transferring all input values reverses them into dequeue order.

Visual walkthrough

The two-stack queue keeps cheap enqueues in the input stack, then reverses that stack only when dequeue needs the output stack.

Step 1 - Enqueue pushes onto the input stack

After enqueueing 10, 20, 30, the newest input value is on top of the input stack.

Step 2 - Transfer reverses into output order

Moving every input value to the output stack turns 10 into the next pop.

Step 3 - Dequeue pops from output

The output stack pops 10 first while 20 becomes the next front.

Basic Implementation

                            basic.cpp
                        

                            #include <deque>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

string render(const vector<int>& values) {
    ostringstream out;
    for (size_t i = 0; i < values.size(); ++i) {
        if (i > 0) out << " -> ";
        out << values[i];
    }
    return out.str();
}

int main() {
    vector<int> inStack;
    vector<int> outStack;
    for (int value : {10, 20, 30}) inStack.push_back(value);
    while (!inStack.empty()) {
        outStack.push_back(inStack.back());
        inStack.pop_back();
    }
    vector<int> removed;
    while (!outStack.empty()) {
        removed.push_back(outStack.back());
        outStack.pop_back();
    }
    cout << render(removed) << endl;
}

                        

Complexity

Time: O(1) amortized per operation
Space: O(n)

Implementation notes

In C++, the checked source uses two std::vector<int> instances, inStack and outStack, as stack backs; it does not use the std::stack adapter.
Enqueue is inStack.push_back(value) over {10, 20, 30}. Stack top is the vector back, so reads use back() and removals use pop_back().
Transfer runs while !inStack.empty(), copying inStack.back() into outStack.push_back(...) before popping from inStack. This reverses [10, 20, 30] into out stack [30, 20, 10].
Dequeue drains outStack under while (!outStack.empty()), copying outStack.back() into removed before pop_back(). The values are int copies, not moved-owned objects.
The trace records empty stacks, input [10, 20, 30], transfer to output [30, 20, 10], then removed [10, 20, 30] with output empty.
render(const std::vector<int>&) uses std::ostringstream and a size_t loop to produce 10 -> 20 -> 30, which is printed with std::cout.
Visible allocation is the three vectors and output string buffer; mutation happens through vector push_back and pop_back.