CODEWITHSUNDEEP
c++stacktraversal
user1857492
user1857492

Reputation: 767

How to traverse stack in C++?

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++)
{
    // ...
}

Upvotes: 31

Views: 75068

Answers (12)

oxidia
oxidia

Reputation: 310

Since c++ stack doesn't have some kind of iterator
this is a basic stack with iterators.

MutantStack.hpp

#pragma once

#include <stack>

template <class T>
class MutantStack : public std::stack<T>
{
public:
    typedef typename std::stack<T>::container_type::iterator iterator;
    typedef typename std::stack<T>::container_type::const_iterator const_iterator;

    MutantStack(void) {}

    iterator begin(void)
    {
        return this->c.begin();
    }

    iterator end(void)
    {
        return this->c.end();
    }

    const_iterator cbegin(void) const
    {
        return this->c.cbegin();
    }

    const_iterator cend(void) const
    {
        return this->c.cend();
    }
};

Upvotes: 0

Arun Suryan
Arun Suryan

Reputation: 1695

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.

Upvotes: 15

Kaaf
Kaaf

Reputation: 380

I wouldn't do this, but you can get a stack values without popping with pointer casting, this makes some assumptions about how the compiled class is stored in memory, not a good idea in general.

As long as you don't change the default underlying container which is std::deque, you can:

std::stack<int>s;
s.push(1234);
s.push(789);

std::deque<int>* d;
d = (std::deque<int>*)&s;
cout << (*d)[0] << endl;
cout << (*d)[1] << endl;

output without popping the stack:

1234
789

Upvotes: 2

iverson
iverson

Reputation: 1

        stack<int> s,dbg; //s = not what's supposed to be

        while(!s.empty()) {
            cout << s.top() << " "; //print top of stack
            dbg.push(s.top());      //push s.top() on a debug stack
            s.pop();                //pop top off of s
        }

        //pop all elements of dbg back into stack as they were
        while(!dbg.empty()) {
            s.push(dbg.top());
            dbg.pop();
        }

I just had to do this to check out what the heck was going wrong with stack on a Leetcode problem. Obviously in the real world it probably makes more sense to just use a debugger.

Upvotes: 0

Zoso
Zoso

Reputation: 3465

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.

Upvotes: 2

OverInflatedWalrus
OverInflatedWalrus

Reputation: 189

Use std::deque if you want to implement LIFO concept and be able to iterate at the same time. To emulate stack, use push_front(), front(), pop_front()

https://en.cppreference.com/w/cpp/container/deque

Internally deque is a sequence of "individually allocated fixed-size arrays", so works significantly better for large amounts of data than stack but worse than vector.

Upvotes: 1

Shaun Wang
Shaun Wang

Reputation: 1

You can do a for loop:

for (stack<T> newStack = stack; !newStack.empty(); newStack.pop()){
   T item = newStack.top();
}

Upvotes: -2

A. Knorre
A. Knorre

Reputation: 124

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"

Upvotes: 5

Ben Crowhurst
Ben Crowhurst

Reputation: 8481

#include <stack>

using std::stack;    

stack< int > numbers;
numbers.push( 1 );
numbers.push( 2 );

while ( not numbers.empty( ) )
{
    int number = numbers.top( );
    numbers.pop( );
}

http://en.cppreference.com/w/cpp/container/stack

Upvotes: 1

DNamto
DNamto

Reputation: 1362

We can't traverse through stack. Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container. Elements are pushed/popped from the "back" of the specific container, which is known as the top of the stack. It is not intended for stack to show this behavior, for this we have other containers

Upvotes: 1

Rahul Tripathi
Rahul Tripathi

Reputation: 172408

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.

Upvotes: 2

utnapistim
utnapistim

Reputation: 27365

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.

Upvotes: 38

Related Questions