C++

std::stack Overview

std::stack is a container adapter from the C++ Standard Library. It does not reimplement a stack from scratch. Instead, it wraps an existing container and exposes only the operations that make sense for a stack: push, pop, top, empty, and size.

Because it hides the underlying container's other methods, std::stack guarantees that LIFO order cannot be violated. You cannot accidentally insert in the middle or iterate over the contents, which keeps the interface honest and safe.

#include <stack>
#include <iostream>

int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);

    std::cout << s.top();   // 3
    s.pop();
    std::cout << s.top();   // 2
    std::cout << s.size();  // 2
}

The stack operations in detail

Underlying Containers

You choose the underlying container by passing it as the second template parameter. The default is std::deque, but std::vector and std::list are also valid.

#include <stack>
#include <vector>
#include <deque>
#include <list>

std::stack<int, std::deque<int>>  a;  // default
std::stack<int, std::vector<int>> b;  // cache friendly
std::stack<int, std::list<int>>   c;  // pointer based

Each container offers a different tradeoff. deque balances growth and random access. vector gives the best cache locality and is preferred when you control the maximum size. list avoids reallocation entirely but pays for pointer chasing and extra memory per element.

Array-backed stack design | Linked list stack design

Push, Pop, Top, and Empty

The operations are straightforward. push adds to the top, top reads the top without removing it, pop removes the top, and empty tells you whether the stack is empty.

std::stack<int> s;

s.push(10);
s.push(20);

int value = s.top();       // 20, not removed
s.pop();                   // removes 20
bool empty = s.empty();    // false

Note that pop() returns void in C++. Unlike Python's list.pop(), you must read top() first and then call pop(). This avoids the cost and exception-safety issues of returning a value by copy.

Why all these operations are O(1)

Custom Stack with std::vector

If you want a stack with a slightly larger API, such as a clear() method or direct size control, you can build a small wrapper around std::vector.

#include <vector>

template <typename T>
class VectorStack {
    std::vector<T> data;
public:
    void push(const T& value) { data.push_back(value); }
    void pop() { if (!data.empty()) data.pop_back(); }
    T& top() { return data.back(); }
    bool empty() const { return data.empty(); }
    size_t size() const { return data.size(); }
    void clear() { data.clear(); }
};

This is essentially std::stack<T, std::vector<T>> plus a few convenience methods. The vector grows automatically with O(1) amortized pushes. A fully manual C stack implementation

Performance Comparison

All three give O(1) push and pop. The differences are constant factors: vector wins on raw speed thanks to contiguous memory, deque is a strong general default, and list trades memory and locality for guaranteed no-reallocation behavior.

Move Semantics and Stack

C++ move semantics let you push objects without unnecessary copying. std::stack forwards to the underlying container, so you can move a temporary object in.

#include <string>
#include <stack>

std::stack<std::string> s;

std::string word = "hello";
s.push(word);                 // copies
s.push(std::move(word));      // moves, word is now empty
s.push(std::string("world")); // moves the temporary

Move semantics matter when stack elements are expensive to copy, such as large strings, containers, or file handles. Passing an rvalue, or calling std::move, avoids a full copy of the element.

How stack elements are stored in memory

Complete C++ Stack Examples

Reversing a string

#include <stack>
#include <string>

std::string reverse(const std::string& in) {
    std::stack<char> s;
    for (char c : in) s.push(c);
    std::string out;
    while (!s.empty()) {
        out.push_back(s.top());
        s.pop();
    }
    return out;
}

Matching parentheses

#include <stack>
#include <unordered_map>

bool isValid(const std::string& str) {
    std::unordered_map<char, char> close = {
        {')', '('}, {']', '['}, {'}', '{'}};
    std::stack<char> s;
    for (char c : str) {
        if (close.count(c)) {
            if (s.empty() || s.top() != close[c]) return false;
            s.pop();
        } else {
            s.push(c);
        }
    }
    return s.empty();
}

More stack problems with solutions

Key Takeaway

std::stack is a thin adapter over a container you choose. Use deque by default, reach for vector when cache locality and raw speed matter, and reserve list for cases that absolutely cannot reallocate. Remember top-then-pop, and use move semantics to avoid needless copies.

Explore all EasyStack guides

Frequently Asked Questions

Which underlying container should I use for std::stack?

deque is the default and a great choice for general use. vector is usually fastest for cache locality and is ideal when you know the stack stays small or bounded. list avoids resizing but has poor cache locality and higher memory overhead, so it is rarely the best pick for a stack.

What is a container adapter in C++?

A container adapter is a class that provides a restricted interface on top of another container. std::stack is an adapter: it wraps a container like deque or vector and exposes only push, pop, top, empty, and size, hiding the container's other operations so LIFO semantics cannot be violated.

Why do push and pop not return values in std::stack?

std::stack follows C++ design rules: functions that can fail throw exceptions, top() returns a reference (allowing modification), and pop() returns void. To get a value and remove it, read top() first, then call pop(). This avoids copy and exception-safety problems.