如何在C++中遍历堆栈？

Question

在C++中，能否遍历std::stack？

以下方法不能用于遍历。因为std::stack没有成员end。

std::stack<int> foo;

// ..

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

- user1857492

---

这就是为什么它被称为“堆栈”。理论上，后进先出，就是这样。 - deviantfan

可能是Does std::stack expose iterators?的重复问题。 - marcinj

你选择了错误的数据类型。如果想要迭代它，请不要使用堆栈（stack）。 - David Heffernan

Answer 1

在C++中是否可以遍历std::stack？

不行。Stack是一种数据结构，当你想把元素放在栈顶并从栈顶获取元素时应该使用它。如果你需要一个可遍历的Stack，可以考虑使用其他数据结构来模拟栈的行为（例如std::vector），或者自己编写一个可遍历的Stack。

- utnapistim

Answer 2

由于 std::stack 没有 end 成员，因此无法直接遍历它，这就是栈数据结构的设计，即只有一个指针。但是，这里有两个懒惰的方法来遍历它：

1）基于循环：

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

循环方法存在的问题：

• 原始栈会变为空。

2) 基于递归的方法：

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

递归方法的优点：

• 维护原始堆栈元素。

递归方法存在的问题：

• 维护内部堆栈。
• 对于堆栈大小较大时可能失败。

- Arun Suryan

---

基于for循环，您可以始终将从原始堆栈弹出的元素推送到另一个堆栈上。然后，在迭代完成后，将另一个堆栈排入原始堆栈，保持原始状态。基本上，您正在使用调用堆栈中的递归解决方案执行相同的操作。 - cwebb91

Answer 3

正如您所提到的，由于调试需要，您可能需要打印一些内容。也许以下内容对您有帮助：

// 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);
}

输出结果如预期的那样是 "9 11"。

- A. Knorre

---

有人对此进行了负评，因为堆栈不应该被这样使用。但是你说这是为了调试目的，你是正确的。开发人员在生产中必须要行事得当，但为了测试有时需要打破一些默认行为。 - José Manuel Blasco

Answer 4

我认为无法通过栈进行遍历。我所能想到的最好的方法是使用std::vector，并使用push_back()，pop_back()。

栈没有提供begin或end成员函数，因此您无法将其与需要这两个函数的基于范围的for循环一起使用。

在您的情况下，如果您真的想要迭代它，最好选择其他数据结构。

- user3414693

Answer 5

#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

- Ben Crowhurst

---

那会改变/清空栈。我最初想要的只是遍历栈并打印出来以进行调试。 - user1857492

Answer 6

可以编写一个简单的包装器，覆盖STL的std::stack并迭代基础容器，因为引用自参考资料：

容器必须满足SequenceContainer的要求

可以通过受保护成员c访问此容器，因此类似于this的内容可能适用于您的情况：

#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();
    }
}

输出：

1 2 3 4 
1 
First Second Third Fourth 
First 

可以将auto返回类型更改为DebugStack（如此处所示），以使此解决方案适用于C++11，因为自动推断返回类型是在C ++14中引入的。

- Zoso

---

这看起来很酷。这能在C++的哪个最早版本中运行？ - user1857492

@user1857492 已更新我的答案，包括 C++ 版本信息。它可以很容易地与 C++11 兼容，而且不需要做出太多更改。 - Zoso

Answer 7

我不建议这样做，但是你可以通过指针转换来获取堆栈的值，这对编译后类在内存中的存储方式有一定的假设，总体来说不是一个好主意。

只要不改变默认的底层容器，即std::deque，你可以：

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;

在不弹出堆栈的情况下输出：

1234
789

- Kaaf

Answer 8

我们无法遍历栈。栈是一种容器适配器，专门设计用于在后进先出（LIFO）的上下文中操作，其中元素仅从容器的一端插入和提取。元素从特定容器的“后面”推入/弹出，这被称为堆栈的顶部。它不打算展示这种行为，因此我们有其他容器。

- DNamto

Answer 9

如果您想要实现LIFO概念并能够同时迭代，请使用std :: deque。要模拟栈，请使用push_front（），front（）和pop_front（）。

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

内部deque是一系列“单独分配的固定大小数组”，因此在处理大量数据时比栈表现更好，但比向量表现更差。

- OverInflatedWalrus

Answer 10

        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();
        }

我只是为了检查Leetcode问题中堆栈出现了什么问题而不得不这样做。显然在实际工作中，使用调试器可能更有意义。

- iverson