How to traverse stack in C++?

Question

Is it possible to traverse std::stack in C++?

Traversing using following method is not applicable. Because std::stack has no member end.

std::stack<int> foo;

// ..

for (__typeof(foo.begin()) it = foo.begin(); it != foo.end();  it++)
{
    // ...
}

Solution 1

Is it possible to traverse std::stack in C++?

No. A stack is a data structure you should use when you are interested in placing elements on top and getting elements from the top. If you want an iterable stack, either use a different data structure for a stack role (std::vector?) or write one yourself.

Solution 2

It is not possible to directly traverse an std:: stack as it does not have an end member and that's how a stack data-structure is supposed to be i.e. only have one pointer. But, still here are two lazy hacks to traverse it:

1) Loop Based:

while(!st.empty()) {
        cout << st.top();
        st.pop();
    }

Problems with the loop-based approach:

• The original stack gets empty.

2) Recursion Based:

template <typename T>
void traverse_stack(stack<T> & st) {
    if(st.empty())
        return;
    T x = st.top();
    cout << x << " ";
    st.pop();
    traverse_stack(st);
    st.push(x);
}

Advantages of Recursion based approach:

• Maintains the original stack elements.

Problems with Recursion based approach:

• Maintains an internal stack.
• May fail for large size of the stack.

Solution 3

As you mentioned you need printing for debugging purposes, maybe something like this would work for you:

// Example program
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <algorithm>

template <typename T>
void StackDebug(std::stack<T> s)
{
    std::vector<T> debugVector = std::vector<T>();
    while (!s.empty( ) )
    {
        T t = s.top( );
        debugVector.push_back(t);
        s.pop( );
    }

    // stack, read from top down, is reversed relative to its creation (from bot to top)
    std::reverse(debugVector.begin(), debugVector.end());
    for(const auto& it : debugVector)
    {
        std::cout << it << " ";
    }
}

int main()
{

    std::stack< int > numbers;
    numbers.push( 9 );
    numbers.push( 11 );

    StackDebug(numbers);
}

Output is, as expected, "9 11"

Solution 4

I don't think that it is possible to traverse through a stack. The best I can think of is using vector using std::vector using push_back(), pop_back()

The stack does not provide a begin or end member function so you cannot use it with a range based for loop which requires both.

In your case it would be better to choose some other data structure if you really want to iterate through it.

Solution 5

One can write a simple wrapper over STL's std::stack and iterate over the underlying container since, quoting from the reference:

The container must satisfy the requirements of SequenceContainer

This container is accessible via the protected member c, so something like this should probably work for your case:

#include <stack>
#include <iostream>
#include <iterator>

template <typename T, typename Container = std::deque<T>>
struct DebugStack : private std::stack<T, Container> {
    auto& push(T& elem) {
        std::stack<T>::push(elem);
        return *this;
    }
    auto& push(T&& elem) {
        std::stack<T>::push(elem);
        return *this;
    }
    auto& pop() {
        std::stack<T>::pop();
        return *this;
    }
    T top() {
        return std::stack<T>::top();
    }
    void print() {
        auto const& container = std::stack<T>::c;
        //T should be printable
        std::copy(begin(container), end(container), std::ostream_iterator<T>(std::cout, " "));
        std::cout<<'\n';
    }
};

int main() {
    {
        DebugStack<int> stack;
        stack.push(1).push(2).push(3).push(4);
        stack.print();
        stack.pop().pop().pop();
        stack.print();
    }

    {
        DebugStack<std::string> stack;
        stack.push("First").push("Second").push("Third").push("Fourth");
        stack.print();
        stack.pop().pop().pop();
        stack.print();
    }
}

Output:

1 2 3 4 
1 
First Second Third Fourth 
First 

One can change the auto return type to DebugStack (as in here) to make this solution work with C++11 since auto deduction of return types was introduced with C++14.

View more solutions

Comments

[deviantfan]

That´s why it is a "stack". Last in first out, that´s it (theoretically).

[marcinj]

possible duplicate of Does std::stack expose iterators?

[David Heffernan]

You've chosen the wrong data type. Don't use a stack if you want to be able to iterate over it.

[user1857492]

That changes/empties the stack. What I originally wanted was just traverse the stack and print it for debugging purposes.

[José Manuel Blasco]

Someone down-voted this because stacks are not suposed to use like this. But you said it's for debugging purposes, and you are right. Developers must act right in production, but for testing sometimes is necessary break some default behaviours.

[Ignatius]

I see a syntax error here! Also, the OP was looking for a solution that doesn't pop everything out.

[user1857492]

This looks very cool. What is the earliest version of C++ this will work on?

[Zoso]

@user1857492 Updated my answer to include the C++ version info. It can be made to work with C++11 without changing much.

[cwebb91]

For loop based, you can always push the elements you're popping from the original stack onto another stack. Then once you're done iterating, drain the other stack onto your original stack, maintaining the original state. Basically doing the same thing you've done in the recursive based solution with the call stack.