前言
众所周知，在写广搜的时候，我们经常会使用队列（queue）来实现广搜的伪同步
但是，如果有一个人问你
你能不能手写一个队列？
请问你会怎么回答？
是回答
Yes,I do.
还是回答No,I don’t.呢
正在你犹豫不决时，他又问你
那，用栈手写，你会吗？
这下，你彻底懵逼了
那么，这篇文章就会教你怎么用两个栈实现队列
正片
1.基础原理
栈是先进后出，队列是先进先出。但是，如过有两个栈，情况就不一样了
当只有一个栈时，入栈顺序为1,2,3出栈顺序为3,2,1
但是，再加上一个队列，先把第一个栈的数据转存到第二个栈里面，输入1,2,3第一个栈把数据转存到第二个栈时3,2,1的入栈顺序，那么，第二个栈的出栈顺序就负负得正，变成了1,2,3
那么现在，
2.代码基础原理
我们定义两个栈，分别为in和out
入栈1,栈中为1,无
入栈2,栈中为1,2,无
入栈3,栈中为1,2,3,无
这时，我们要出栈，那么就可以把栈in的内容全部转移到栈out中
转移栈,栈中为无,3,2,1
再输出栈out
输出,栈中为无,3,2,1,输出1
弹出栈顶元素，栈中为无,3,2
以此类推
恭喜你，已经了解了用栈实现队列的基础原理，接下来，开始代码实操吧
3.代码实操
首先，我们定义两个栈
stack<int> stack_in;
stack<int> stack_out;
再写一个推入函数
void push(int n){
stack_in.push(n);
}
再写一个读取函数
int front(){
return stack_out.top();
}
但是，这时候我们如果直接读取，可能out栈中没有元素，就会报错
那么，我们就加上一段判断是否为空的代码
int front(){
if(stack_out.empty()){
make_stack_in_to_stack_out();
}
return stack_out.top();
}
再写一个转移函数
void make_stack_in_to_stack_out(){
while(!stack_in.empty()){
stack_out.push(stack_in.top());
stack_in.pop();
}
}
再加上一个清空队头的函数
void pop(){
if(stack_out.empty()){
make_stack_in_to_stack_out();
}
stack_out.pop();
}
最后，再协商一些 附属函数
bool empty(){
return stack_in.empty()&&stack_out.empty();
}
int size(){
return stack_in.size()+stack_out.size();
}
那么，恭喜你，成功地写成了一个栈
结合代码
stack<int> stack_in;
stack<int> stack_out;
void make_stack_in_to_stack_out(){
while(!stack_in.empty()){
stack_out.push(stack_in.top());
stack_in.pop();
}
}
void push(int n){
stack_in.push(n);
}
int front(){
if(stack_out.empty()){
make_stack_in_to_stack_out();
}
return stack_out.top();
}
void pop(){
if(stack_out.empty()){
make_stack_in_to_stack_out();
}
stack_out.pop();
}
bool empty(){
return stack_in.empty()&&stack_out.empty();
}
int size(){
return stack_in.size()+stack_out.size();
}
4.支持不同类型
我们平常用的栈都是支持不同类型的，如结构体
那么，怎么让我们的代码支持不同类型？
很简单，只要用template<typename T>语句定义一个T，用于存储变量就可以了
代码：
template<typename T>
stack<T> stack_in;
stack<T> stack_out;
void make_stack_in_to_stack_out(){
while(!stack_in.empty()){
stack_out.push(stack_in.top());
stack_in.pop();
}
}
void push(T n){
stack_in.push(n);
}
T front(){
if(stack_out.empty()){
make_stack_in_to_stack_out();
}
return stack_out.top();
}
void pop(){
if(stack_out.empty()){
make_stack_in_to_stack_out();
}
stack_out.pop();
}
bool empty(){
return stack_in.empty()&&stack_out.empty();
}
int size(){
return stack_in.size()+stack_out.size();
}
5.最终封装
那么最后，奉上class封装代码支持不同类型，使用queue_usingstack来使用
复制时注意加上template<typename T>
#include<bits/stdc++.h>
using namespace std;
template<typename T>
class queue_usingstack{
private:
stack<T> stack_in;
stack<T> stack_out;
void make_stack_in_to_stack_out(){
while(!stack_in.empty()){
stack_out.push(stack_in.top());
stack_in.pop();
}
}
public:
void push(T n){
stack_in.push(n);
}
T top(){//top=front 功能相同
if(stack_out.empty()){
make_stack_in_to_stack_out();
}
return stack_out.top();
}
T front(){
if(stack_out.empty()){
make_stack_in_to_stack_out();
}
return stack_out.top();
}
void pop(){
if(stack_out.empty()){
make_stack_in_to_stack_out();
}
stack_out.pop();
}
bool empty(){
return stack_in.empty()&&stack_out.empty();
}
int size(){
return stack_in.size()+stack_out.size();
}
};
int main(){
return 0;
}