不用弹出元素就能实现的数据结构遍历

OIer_AKIOI · 2024-08-27 11:59:20 · 算法·理论

该技巧使用到了指针，注意遍历栈需把代码第 16 行的 ++ 改成 --，其它数据结构与示例的 queue 一样。该技巧主要受用指针遍历数组的启发，因为老师说数组中每个元素的地址是连续的，我就想类似 queue、stack 这样普通遍历只能用弹出元素来实现的数据结构，它们的地址不也应该是连续的吗？那就可以用指针来实现这些数据结构的遍历，这样遍历这些数据结构就不用 pop 了，内部元素不会丢失。

示例代码如下：

#include<iostream>
#include<queue>
using namespace std;
queue<int>q;
int main(){
    int n,a;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        q.push(a);
    }
    int *p=&q.front();
    for(int i=0;i<n;i++){
        cout<<*p<<" ";
        p++;
    }
    cout<<endl;
    while(!q.empty()){
        cout<<q.front()<<" ";
        q.pop(); 
    }
    return 0;
}

输出第一行为指针遍历的结果，第二行为普通遍历的结果。

需要注意的是 priority_queue 不适用于该技巧，作者正在寻找解决方案，各位大佬如果知道的话欢迎私信我！