Queue from Two Stacks

Implement queue behavior with an input stack and an output stack.

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.

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

Keep the explicit stack/queue operations. Library shortcuts that only produce the final list hide the data-structure behavior this lesson is meant to replay.
The final output uses a deterministic a -> b -> c format for cross-language comparison.

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.