数据结构——栈和队列的相互模拟

栈：只能一端进行插入和删除，具有先进后出的特点

队列：一端进行插入一端进行删除，具有先进先出的特点

1.两个栈来模拟一个队列：

此时我们将第一个栈称为S1，将第二个栈称为S2。

思路：

入队：

栈的插入是只有一端进行插入。

队列的插入也是只有一端进行插入。

所以在宏观视觉上，栈的插入和队列的插入没有什么区别。

所以我们此时在进行插入是时候只需在S1这个栈上进行插入即可。

出队：

因为队列只能一端进行插入而另一端进行删除，具有先进先出的特点。

而栈是只有一端进行插入和删除，具有先进后出的特点。

此时我们拥有两个栈，在S1这个栈中已经拥有数据元素，我们想要实现队列的删除效果

需要将S1中的数据元素，插入到S2中此时，在最开始插入的数据本应在S1的栈底，此时就在了S2的栈顶，进行删除，只需删除S2中的元素即可。

具体思路是如此，但是仍然有瑕疵，如果S2中还有没有被删除完全的元素S1有新插入的元素并且我们还要删除元素呢？

那么此时我们我们就不能让S1中的数据，先插入到S2当中，因为相较于S1中的数据，此时S2中的数据是先插入S1的，只不过我们将其放置到了S2中而已，为了满足队列的先进先出特特点我们此时必须先删除S2中的数据。也就意味着，每次删除的时候，我们必须先去判断S2是否为空，不空则直接从S2中出一个数，如果S2的空了，则说明剩余数据全部均在S1中，此时只需要将S1中的数据全部插入到S2中，此时S2中有数据，在S2上进行删除即可。

图文解释：

假设一开始我们在S1中先插入了 45 然后是 56 最后是67

此时我要删除数据，就需要先将S1中的数据放置到S2中再进行删除 shan

删除完45，之后此时S2中剩下了 56 67 如果此时我再进行对S1的插入，并且删除的话，我仍然只能先删S2中的值，当S2中的值完全没有的时候再将S1中的值全部插入到S2中

代码实现：

1.结构体定义：

typedef struct TwoStack_toQueue { std::stack<int> S1; //std::->表示用C++标准库里面的东西 //stack->表示栈 //<int>->表示栈里面存的数据是int 型 //S1:表示入队栈 //S2：表示出队栈 std::stack<int> S2; }TwoStack_toQueue;

入队：

bool TSQ_Push(TwoStack_toQueue* ptsq, int val) { //插入规则：无脑的向S1插入 ptsq->S1.push(val); //通过指针找到入队栈S1 调用系统自带的插入函数 将val这个值进行插入 return true;

出队：

bool TSQ_Pop(TwoStack_toQueue* ptsq) { if (!ptsq->S2.empty()) { ptsq->S2.pop(); return true; } //判断S2是否为空 如果不为空 直接删除 while (!ptsq->S1.empty()) //将S1中的全部的数据按照栈插入放置到S2中 { int tmp = ptsq->S1.top(); //获取栈顶元素值 获取栈顶元素只具有将其值获取出来 没有其他权限 //将获取出的值初始化给tmp ptsq->S1.pop(); //删除S1中的栈顶元素值 不然每次获取的栈顶元素都是一个值 ptsq->S2.push(tmp); //将获取的值插入到S2中 } ptsq->S2.pop(); //删除S2中的栈顶元素值 return true; }

2.两个队列来模拟一个栈：

队列:一端进行插入和一端进行删除，具有先进先出的特点

站栈：只能在一端进行插入和删除，具有先进后出的特点

假设此时有两个队列，分别为Q1 Q2

思路：

入栈：

因为栈的插入就是一端进行插入

队列也是一端进行插入，他们的区别只在于删除

所以宏观视觉上两个没有什么区别

此时只需在Q1中持续插入即可

出栈：

栈具有在同一端插入和删除，具有先进后出的特点

队列在一端插入一段删除，具有先进后出的特点

为了满足栈的先进后出的特点

如果Q1非空，此时就意味着，我们要删除的值就在Q1的队尾，将除了队尾元素外的其他元素全部按照队列插入，插入到Q2中，最后再删除Q1中的值。

如果Q1空了，此时就意味着，我们要删除的值一定在Q2的队尾，将除了队尾元素外的其他元素全部按照队列插入，插入到Q1中，最后再删除Q1中的值

图文表示：

在队列Q1中插入值 12 23 34

Q1非空，所以此时我们要删除的值就是34，也就是队尾元素，将除了队尾元素外全部按照队列插入到Q2中

直接删除34即可

继续删除，Q1空了此时我们要删除的元素就是23，也就是Q2的队尾元素，将除了队尾元素外，将其他元素按照队列插入到Q1中。

删除元素即可

代码表示：

入栈：

bool TQS_Push(TwoQueue_toStack* ptqs, int val) { //插入规则：无脑的向Q1插入 ptqs->Q1.push(val); return true; }

出栈：

bool TQS_Pop(TwoQueue_toStack* ptqs) { if (!ptqs->Q1.empty()) { int Size_Q1 = ptqs->Q1.size(); //获取队列有几个元素 for (int i = 0; i < Size_Q1 - 1; i++) //因为我们要将除了队尾元素外，其他的元素全部按照队列插入到Q2 所以循环只能是size-1 { ptqs->Q2.push(ptqs->Q1.front()); ptqs->Q1.pop(); } ptqs->Q1.pop(); return true; } int Size_Q2 = ptqs->Q2.size(); for (int i = 0; i < Size_Q2 - 1; i++) { ptqs->Q1.push(ptqs->Q2.front()); ptqs->Q2.pop(); } ptqs->Q2.pop(); return true; }