Stacks and Queues

Stack Push/Pop

Push values onto a stack and pop them back in last-in, first-out order.

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> stack;
    for (int value : {10, 20, 30}) stack.push_back(value);
    vector<int> popped;
    while (!stack.empty()) {
        popped.push_back(stack.back());
        stack.pop_back();
    }
    cout << render(popped) << endl;
}

The same three values from the trace are shown as stack states. The top cell is the next value a pop removes.

Step 1 - Start empty

There is no top value yet.

Empty stack before any push.top of stack(empty)

Step 2 - Push 10, then 20, then 30

Each push places the new value above the previous top.

After push 10, push 20, push 30: 30 is on top.top -> bottom302010

Step 3 - Pop removes 30 first

The top cell leaves first, so the remaining stack starts with 20.

After one pop: popped is 30; 20 is now on top.top -> bottompopped203010

Complexity

  • Time: O(1) per push/pop
  • Space: O(n)

Implementation notes

  • In C++, the checked source uses std::vector<int> stack as the stack backing store; it does not use the std::stack adapter.
  • Push uses stack.push_back(value) over {10, 20, 30}. The logical top is the vector back, so pop reads stack.back() before stack.pop_back().
  • The pop loop is guarded by while (!stack.empty()), so back() and pop_back() are only called on a non-empty vector in the checked path.
  • Popped integers are copied into std::vector<int> popped; there is no ownership transfer or reference aliasing between the vectors.
  • The trace records stack [], then [10, 20, 30], then popped [30] with stack [10, 20], ending with popped [30, 20, 10] and stack [].
  • render(const std::vector<int>&) uses std::ostringstream and a size_t loop to produce 30 -> 20 -> 10, which is printed with std::cout.
  • Visible allocation is the stack vector, popped vector, and output string buffer; mutation happens through vector push_back and pop_back.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.