队列之双队列

双队列指的是两个队列，不是双端队列，2333。

如果题目要求你用队列实现DFS，你是否会高呼amazing，unbelievable!其实，用队列实现DFS的本质就是问用队列实现栈结构，因为DFS本身就是基于栈实现的。

我们知道，基础队列是先进先出的，而栈是先进后出的，两个完全相反的结构，但是正因为相反，才有相互转换的可能。

假设我们有两个队列data、help，用他们两个实现一个栈。

push:将数据打进data队列

pop:将队列中的元素在保留队尾的情况下，将其他的数据全部打入help，输出data的元素，清空data，再将help与data交换即可。

因为栈的pop要的只是最后一个入栈的元素，对于队列来说，这个元素一定在队尾，所以只要将前面的元素按照顺序维持在另一个结构里【自然是help队列】，将队尾元素pop后，交换两个队列即可。

top:将队列中的元素在保留队尾的情况下，将其他的数据全部打入help，输出data的元素，但不清空data。

代码：

#include<queue>
#include<cstdio>
using namespace std;
typedef struct{
    queue<int>data,help;
    void push(int val){
        data.push(val);
    }
    void pop(){
        while(data.size()>1){
            help.push(data.front());
            data.pop();
        }
        data.pop();
        swap(help,data);
    }
    int top(){
        while(data.size()>1){
            help.push(data.front());
            data.pop();
        }
        return data.front();
    }
}Stack;

int main(){
    Stack V;
    V.push(1);
    V.push(2);
    V.push(3);        
    V.push(4);
    printf("1234入栈后,栈顶:%d\n",V.top());
    V.pop();
    printf("出栈一个后,栈顶:%d\n",V.top());
}