Traverse a stack in C++

This post will discuss how to traverse a stack in C++.

The std::stack container does not have any std::begin or std::end member function, and there isn’t any overload of std::begin which accepts a std::stack. We cannot use it with a range-based for-loop. In other words, std::stack is not meant to be iterated over.

Although it is not possible to directly traverse a std::stack, you can create a copy of the original stack and process its items, one at a time, and then remove it with the standard pop function until the stack gets empty. This way the original stack remains untouched, but its copy becomes empty.

#include <iostream>

#include <stack>

int main()

{

std::stack<int> stk;

stk.push(1);

stk.push(2);

stk.push(3);

stk.push(4);

std::stack<int> stk_copy(stk);

while(!stk_copy.empty()) {

std::cout << stk_copy.top() << std::endl;

stk_copy.pop();

}

return 0;

}

Download Run Code

Output:

4
3
2
1

We can also recursively print the contents of the stack and avoid creating a temporary copy of it. This, however, uses an implicit stack (call stack) for recursion and may exhaust heap memory for a very large stack.

#include <iostream>

#include <stack>

template <typename T>

void traverseStack(std::stack<T> &stk) {

if (stk.empty()) {

return;

}

T x = stk.top();

std::cout << x << " ";

stk.pop();

traverseStack(stk);

stk.push(x);

}

int main()

{

std::stack<int> stk;

stk.push(1);

stk.push(2);

stk.push(3);

stk.push(4);

traverseStack(stk);

return 0;

}

Download Run Code

Output:

4
3
2
1

A better alternative is to use std::deque instead, which can be iterated over using the range-based for-loop. A std::deque supports all standard operations of a std::stack. For example, we can insert and remove items from one end of a deque (say front) using the push_front and pop_front functions.

#include <iostream>

#include <deque>

int main()

{

std::deque<int> s;

s.push_front(1);

s.push_front(2);

s.push_front(3);

s.push_front(4);

for(auto &i: s) {

std::cout << i << std::endl;

}

return 0;

}

Download Run Code

Output:

4
3
2
1

That’s all about traversing a stack in C++.

Share this: