Stack Data Structures using std::stack

A stack is another fundamental data structure frequently used to solve programming problems. Similar to a queue, they are used when we need a container that constrains the order in which its objects are accessed. The key difference is that a stack uses the opposite principle.

• a queue uses the first in, first out (FIFO) principle
• a stack uses the last in, first out (LIFO) principle

That is, objects in a stack are accessed in the opposite order to which they were added. In other words, the most recently added object is accessed first.

Stacks are often visualized as a vertical tower of objects, where the most recently added items are at the top. As such, only the topmost object is accessible:

Objects deeper in the stack only become accessible when the objects above them are removed. Removing an object from the top of the stack is sometimes referred to as “popping” it. Once we pop an object from the stack, the object that was immediately below it will then become the stack’s top object.

When we add objects to a stack, this is often referred to as “pushing” them. Objects are always pushed to the top of the stack:

Stacks are a ubiquitous technique for solving problems we’re likely to encounter when programming complex software. Some common examples include:

1. Code Compilation

The most obvious use of stacks is one we’ve already been using this whole time. We saw how the execution of our program is a function call stack.

Code compilers are themselves written in code and, as we might expect, function call stacks are examples of stacks in action.

It’s not the only example - stacks are also ubiquitous in the evaluation of expressions that appear in our source code.

2. Backtracking Algorithms

Almost any form of backtracking involves a stack under the hood. Examples of this include “undo” functionality in programs, where actions need to be reverted in the opposite order in which they were performed. That is, last in, first out.

The back button within browsers is another example of this principle that we use every day.

3. Graph Algorithms

Stacks are also fundamental building blocks that power a lot of useful algorithms, particularly graph algorithms. Graphs are more complex data structures than what we’ve seen so far. Within a graph, our objects can be connected to any other object in the collection. The main use case for these data structures is to model real-world networks, such as road systems and the Internet.

Stacks underpin the most common graph algorithm - depth-first search. This is used to navigate through the graph, powering capabilities such as navigation within a GPS system, and enabling AI characters to move through virtual worlds within games.

std::stack

The standard library’s implementation of a stack is std::stack, and is available within the <stack> header.

std::stack objects can be constructed in the normal way - we just need to pass a template parameter denoting the type of objects our stack will contain. In this case, we create a stack to hold int objects:

1#include <stack>
2
3int main(){
4  std::stack<int> Numbers;
5}
6

We can populate our stack with initial values by passing an iterator pair to the constructor. We cover iterators in more detail later in the course.

In the following code, we give a simple example of creating a stack using all the objects from a std::vector

In this case, our stack will contain the numbers 1, 2, and 3, with 3 being at the “top” of the stack:

1#include <stack>
2#include <vector>
3
4int main(){
5  std::vector Source{1, 2, 3};
6  std::stack<int> Numbers{
7    Source.begin(), Source.end()
8  };
9}
10

We can also create stacks by copying and moving other stacks:

1#include <stack>
2#include <vector>
3
4int main(){
5  std::stack<int> Numbers;
6  std::stack<int> NumbersCopy{Numbers};
7  std::stack<int> NumbersMove{
8    std::move(Numbers)
9  };
10}
11

As always, we can use Class Template Argument Deduction (CTAD) to remove template arguments in many cases. The compiler correctly deduces that all of the containers we’re constructing in this example will be holding int objects:

1#include <stack>
2#include <vector>
3
4int main(){
5  std::vector Source{1, 2, 3};
6  std::stack Numbers{
7    Source.begin(), Source.end()
8  };
9  std::stack NumbersCopy{Numbers};
10}
11

We can also construct a queue directly from a specific type of container, which we cover later in this lesson.

Accessing the Top Element

We can get a reference to the top element of our stack using the top() method:

1#include <stack>
2#include <vector>
3#include <iostream>
4
5int main(){
6  std::vector Numbers{1, 2, 3};
7  std::stack Stack{
8    Numbers.begin(), Numbers.end()
9  };
10
11  std::cout << "Top: " << Stack.top();
12}
13

1Top: 3
2

Removing the Top Element

The pop() method allows us to remove the top element from the stack. This reduces the size (height) of our stack, and the element that was previously second from the top will now be the top element:

1#include <stack>
2#include <vector>
3#include <iostream>
4
5int main(){
6  std::vector Numbers{1, 2, 3};
7  std::stack Stack{
8    Numbers.begin(), Numbers.end()
9  };
10
11  std::cout << "Top: " << Stack.top();
12  Stack.pop();
13  std::cout << "\nTop: " << Stack.top();
14}
15

1Top: 3
2Top: 2
3

Adding Objects to the Stack

There are three main methods we use to add items to the stack. Those are emplace(), push() and, since C++23, push_range()

emplace()

Similar to other containers, the most performant way of adding objects to a stack is to construct them directly in the stack. This is sometimes referred to as constructing the object in place.

To do this, we use the emplace() method. Any arguments we provide to emplace() will be forwarded to the constructor of the type our stack contains.

1#include <stack>
2#include <iostream>
3
Character Class|Show 20 Lines
4class Character {/*...*/};
25
26int main(){
27  std::stack<Character> Stack;
28  Stack.emplace("Roderick");
29  std::cout << "\nTop: " << Stack.top().Name;
30}
31

1Constructing Roderick
2Top: Roderick
3

push()

When the object we want to add to the stack already exists, we can use the push() method to copy or move it into our stack. Below, we push two objects onto our stack - one by copying an existing object, and one by moving that same object:

1#include <stack>
2#include <iostream>
3
Character Class|Show 20 Lines
4class Character {/*...*/};
25
26int main(){
27  std::stack<Character> Stack;
28
29  Character Roderick{"Roderick"};
30  Stack.push(Roderick);
31  Stack.push(std::move(Roderick));
32}
33

1Constructing Roderick
2Copying Roderick
3Moving Roderick
4

We cover copy semantics, move semantics, and std::move in more detail here:

Copy Semantics, Elision, and RVO

Learn how to implement copy semantics in C++, and take advantage of copy elision and return value optimization (RVO)

Move Semantics, std::move and rvalues

Learn how to implement move semantics in C++, the difference between lvalues and rvalues, and what std::move really does.

push_range()

As of C++23, std::stack has gained the push_range() method, which allows us to add multiple objects to the stack at once.

We cover ranges in more detail later in the course, but for now, we can note that most of the sequential containers we’ve seen so far are examples of a range.

Below, we push all the contents of a std::vector to our stack:

1#include <stack>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Numbers{3, 4, 5};
7  std::stack<int> Stack;
8
9  Stack.emplace(1);
10  Stack.emplace(2);
11  Stack.push_range(Numbers);
12
13  std::cout << "Top: " << Stack.top();
14}
15

1Top: 5
2

Getting the Stack Size

There are two main ways we can check how many objects are in our std::stack - the size() method and the empty() method.

size()

The size() method returns a size_t - an integer that tells us how many objects are in our std::stack:

1#include <stack>
2#include <iostream>
3
4int main(){
5  std::stack<int> Stack;
6
7  Stack.emplace(0);
8  Stack.emplace(0);
9  Stack.emplace(0);
10
11  std::cout << "Stack Size: " << Stack.size();
12  Stack.pop();
13  std::cout << "\nStack Size: " << Stack.size();
14}
15

1Stack Size: 3
2Stack Size: 2
3

empty()

In many cases, our motivation for calling the size() method is to check if there are any objects in the stack at all. That is, if size() == 0.

The empty() method gives us a more descriptive way to implement that check:

1#include <stack>
2#include <iostream>
3
4int main(){
5  std::stack<int> Stack;
6
7  Stack.emplace(0);
8
9  if (!Stack.empty()) {
10    std::cout << "The stack is not empty";
11  }
12
13  Stack.pop();
14
15  if (Stack.empty()) {
16    std::cout << "\nNow it is empty";
17  }
18}
19

1The stack is not empty
2Now it is empty
3

Typical Stack Usage

The following example shows a basic, typical recipe for how stacks are used. which combines the top(), pop() and empty() methods.

We have a loop that continues as long as the stack has objects - ie, it is not empty().

The top element is then accessed using the top() method, and handled in whatever way our use case requires. Once processing is complete, it is removed from the stack using the top() method, and the next iteration of our loop continues.

1#include <stack>
2#include <iostream>
3#include <vector>
4
5void Process(int Number){
6  std::cout << "Processing " << Number << '\n';
7}
8
9int main(){
10  std::vector Nums{1, 2, 3};
11  std::stack Stack{Nums.begin(), Nums.end()};
12
13  while (!Stack.empty()) {
14    Process(Stack.top());
15    Stack.pop();
16  }
17
18  std::cout << "Done!";
19}
20

1Processing 3
2Processing 2
3Processing 1
4Done!
5

Using a different container with std::stack (Container Adaptors)

Similar to std::queue, the std::stack template is an example of a container adaptor.

Container adaptors do not directly manage the storage of the objects they contain. They defer that to some other container, and then simply provide an interface that makes that container behave in the desired way.

By default, std::stack uses a std::deque - a double-ended queue - as the underlying container. We cover std::deque in detail later in this chapter.

The underlying container can be changed by passing a second template argument when creating our std::stack.

In this example, we use a std::list instead:

1#include <stack>
2#include <list>
3
4int main(){
5  std::stack<int, std::list<int>> Stack;
6}
7

A std::stack can use any sequential container, as long as it supports the following methods:

• push_back() - adds an object to the top of the stack
• back() - returns a reference to the object at the top of the stack (i.e., the object that was most recently pushed)
• pop_back() - returns a reference to the object at the top of the stack (i.e., the object that was most recently pushed)

In other words, the std::stack template simply uses another sequential container and treats the “back” of that container as the “top” of the stack.

If we want our stack to have good performance, ideally the underlying container should also have favorable performance (ideally constant time) in all three of these operations. The default std::deque does meet these criteria so unless there’s a compelling reason to use something else, the default option is generally good.

Initializing a Stack from an Underlying Container

When our objects are already in a container that is a viable candidate to underly a std::stack, we can create it directly from that container. The “back” of that container will become the “top” of the stack:

1#include <stack>
2#include <list>
3#include <iostream>
4
5int main(){
6  std::list Numbers{1, 2, 3};
7  std::stack<int, std::list<int>> A{Numbers};
8  std::cout << "Top Object: " << A.top();
9}
10

1Top Object: 3
2

When doing this, we can eliminate the second template parameter, and let the compiler infer it using class template argument deduction (CTAD):

1#include <stack>
2#include <list>
3#include <iostream>
4
5int main(){
6  std::list Numbers{1, 2, 3};
7  std::stack A{Numbers};
8}
9