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++)
{
// ...
}
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.
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:
while(!st.empty()) {
cout << st.top();
st.pop();
}
Problems with the loop-based approach:
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:
Problems with Recursion based approach:
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"
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.
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
#include <stack>
using std::stack;
stack< int > numbers;
numbers.push( 1 );
numbers.push( 2 );
while ( not numbers.empty( ) )
{
int number = numbers.top( );
numbers.pop( );
}
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.
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.
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
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.
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();
}
};
You can do a for loop:
for (stack<T> newStack = stack; !newStack.empty(); newStack.pop()){
T item = newStack.top();
}
