Stacks and Queues

Queue from Two Stacks

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

Algorithm

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;
}

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.

After enqueues: input top is 30; output is empty.input stack top -> bottomoutput stack top -> bottomremoved30(empty)(empty)2010

Step 2 - Transfer reverses into output order

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

After transfer: output top is 10, so dequeue returns the oldest value.input stackoutput stack top -> bottomremoved(empty)10(empty)2030

Step 3 - Dequeue pops from output

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

After one dequeue: removed is 10; output top is now 20.input stackoutput stack top -> bottomremoved(empty)201030

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.
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.