Introduction to Stacks 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. Whilst a queue constrains access based on a first in, first out (FIFO) principle, a stack is last in, first out (LIFO)

That is, objects in a stack are accessed in the opposite order they were added. 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.

The Call Stack and Debugging Functions

An introduction to how our function calls create a call stack, and how we can navigate it in a debugger.

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.

Creating a 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}

Prepopulating a Stack using Iterators

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

Iterators

This lesson provides an in-depth look at iterators in C++, covering different types like forward, bidirectional, and random access iterators, and their practical uses.

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}

Copying and Moving Stacks

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}

Class Template Argument Deduction

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}

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}

1Top: 3

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}

1Top: 3
2Top: 2

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
4class Character {/*...*/};
25
26int main(){
27  std::stack<Character> Stack;
28  Stack.emplace("Roderick");
29  std::cout << "\nTop: " << Stack.top().Name;
30}

1Constructing Roderick
2Top: Roderick

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

1Constructing Roderick
2Copying Roderick
3Moving Roderick

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

Copy Semantics and Return Value Optimization

Learn how to control exactly how our objects get copied, and take advantage of copy elision and return value optimization (RVO)

Move Semantics

Learn how we can improve the performance of our types using move constructors, move assignment operators and std::move()

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}

1Top: 5

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}

1Stack Size: 3
2Stack Size: 2

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}

1The stack is not empty
2Now it is empty

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}

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

std::stack is a Container Adaptor

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}

A std::stack can use any sequential container - it treats the "back" of that container as the "top" of the stack. Specifically, the container needs to provide the following methods:

• push_back() - adds an object to the top of the stack. Used by the push() method of std::stack
• emplace_back() - constructs an object at the top of the stack. Used by the emplace() method of std::stack
• back() - returns a reference to the object at the top of the stack. Used by the top() method of std::stack
• pop_back() - removes the object at the top of the stack. Used by the pop() method of std::stack

If we want our stack to have high performance, the underlying container should also have favorable performance (ideally constant time) in all three of these operations. The default std::deque meets this 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.

Below, we use a doubly linked list, std::list, as the basis for our stack, and we prepopulate it by copying an existing std::list:

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}

1Top Object: 3

If preferred, we can alternatively move the list rather than copying it. We can also omit the template arguments and use CTAD if we wish:

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

1Top Object: 3

Summary

This lesson provides an in-depth overview of the stack data structure and how to use it in C++ with the std::stack container adaptor. Key takeaways include:

• Stacks are a last-in, first-out (LIFO) data structure, where elements are accessed in the reverse order they were added
• Stacks have many applications, including code compilation, backtracking algorithms, and graph algorithms like depth-first search
• std::stack is the standard library implementation of a stack, available in the <stack> header
• Stacks can be constructed by passing iterators, copying/moving other stacks, or using class template argument deduction (CTAD)
• The top element can be accessed with top() and removed with pop()
• Elements can be added to the stack with emplace(), push(), and in C++23, push_range()
• The size of a stack can be checked with size() or empty()
• std::stack is a container adaptor that uses std::deque by default, but can use other sequential containers
• Stacks can be initialized directly from an underlying container

Next Lesson

Double-Ended Queues using std::deque

A guide to double-ended queues - a structure that behaves like a vector, specialised for manipulating objects at the edges of the collection

ContinueView Course