Home | Projects | Notes > C++ Programming > Container Adaptor - std::stack

Container Adaptor - std::stack

std::stack

• Declared in the <stack> header file.

• Last-In, First-Out (LIFO) data structure.

• Implemented as an adaptor over other STL containers.

  • Can use vector, list, or deque as the underlying container.

  • Stack methods work through delegation—they internally call the back(), push_back(), and pop_back() functions of the underlying container.

• All operations occur at one end of the stack (i.e., the top).

• Iterators are not supported.

  • This makes sense, as stacks only allow insertions and deletions at one end.

• Use cases:

  • Function call stack

  • Expression evaluation & parsing in compilers, calculators and so on

  • Backtracking algorithms (e.g., Maze solvers, Sudoku solvers, Depth-First Search (DFS) in graphs)

  • Syntax checking (e.g., Code parsers, interpreters, linters, balanced parentheses)

Initialization

Because std::stack is a container adaptor, you have the flexibility to specify the underlying container—such as deque, vector, or list—at the time of stack creation.

4
1
std::stack<int> s1;                     // deque (by default)
2
std::stack<int, std::vector<int>> s2;   // vector
3
std::stack<int, std::list<int>> s3;     // list
4
std::stack<int, std::deque<int>> s4;    // deque

Stack Operations

For more information, see cppreference.com.

Project: Usage of std::stack

It's best to adhere to the fundamental operations of a stack. Introducing additional methods like insert() compromises the integrity of the stack's intended behavior.

64
1
#include <iostream>
2
#include <stack>
3
#include <vector>
4
#include <list>
5

6
// Prints the stack by repeatedly topping and popping the elements.
7
// Note that this function is passed a stack 'by value' so whatever happens
8
// inside this function will not affect the original stack.
9
template <typename T>
10
void print(std::stack<T> s)
11
{
12
    std::cout << "[ ";
13
    while (!s.empty())
14
    {
15
        T elem = s.top();
16
        s.pop();
17
        std::cout << elem << " ";
18
    }
19
    std::cout << "]" << std::endl;
20
}
21

22
// push(), pop(), empty(), size()
23
void test(void)
24
{
25
    std::cout << "\nTEST" << std::endl;
26

27
    std::stack<int> s;
28
    std::stack<int, std::vector<int>> s1;
29
    std::stack<int, std::list<int>> s2;
30
    std::stack<int, std::deque<int>> s3;
31

32
    for (int i : {1, 2, 3, 4, 5})
33
    {
34
        s.push(i);
35
    }
36
    print(s);
37

38
    s.push(100);
39
    print(s);
40

41
    s.pop();
42
    s.pop();
43
    print(s);
44

45
    while (!s.empty())
46
    {
47
        s.pop();
48
    }
49
    print(s);
50

51
    std::cout << "Size: " << s.size() << std::endl;
52

53
    s.push(10);
54
    print(s);
55

56
    s.top() = 100;
57
    print(s);
58
}
59

60
int main(int argc, char *argv[])
61
{
62
    test();
63
    return 0;
64
}

9
1

2
TEST
3
[ 5 4 3 2 1 ]
4
[ 100 5 4 3 2 1 ]
5
[ 4 3 2 1 ]
6
[ ]
7
Size: 0
8
[ 10 ]
9
[ 100 ]