用栈实现队列

1、栈的特点

栈的特点是先进后出，进出元素都是在同一端（栈顶）。

入栈：

出栈：

2、队列的特点

队列的特点是先进先出，出入元素是在不同的两端（队头和队尾）。

入队：

出队：

3、两个栈实现队列

我们拥有两个栈，可以让其中一个栈作为队列的入口，负责插入新元素；另一个栈作为队列的出口，负责移除老的元素。

队列的主要操作无非有两个：入队和出队。在模拟入队操作时，每一个新元素都被压入到栈A当中。

         让元素1“入队”：

         让元素2“入队”：

         让元素3“入队”：

         这时候，我们希望最先“入队”的元素1“出队”，需要怎么做呢？

         让栈A中的所有元素按顺序出栈，再按照出栈顺序压入栈B。这样一来，元素从栈A弹出并压入栈B的顺序是3,2,1，和当初进入栈A的顺序1，2,3是相反的：

         此时让元素1“出队”，也就是让元素1从栈B弹出：

         让元素2“出队”：

         如果这个时候又想做入队操作了呢？当有新元素入队时，重新把新元素压入栈A。

         让元素4“入队”：

         此时的出队操作仍然从栈B弹出元素。

         让元素3“出队”：

         这个时候栈B已经空了，如果再想出队怎么办呢？只要栈A还有元素就像刚才一样，把栈A元素弹出并压入栈B。

         让元素4“出队”：

4、实现思路

（1） 使用两个栈A,B，其中假定A负责push操作，B负责pop操作。使用一个变量back_elem来存储最后添加的元素。

（2） 实现队列的push操作， 每次进行添加操作，都会相应得对栈A进行添加元素。并对back_elem赋值

（3） 实现队列的pop操作，每次进行删除操作，因为栈B负责pop操作，

首先判断栈B是否为空？

a.如果B为空，则判断A是否为空？ 

          如果A也为空，则输出错误信息，此时队列为空。

          如果A不为空，则将栈A中的所有数据存储到B中。执B.push(A.top()),   A.pop().   然后在对栈B执行，B.pop()操作，将队列的头元素删除

b.如果B不为空， 则直接对B执行 B.pop()操作。

           例如对a,b,c实现push操作，然后实现pop操作

                   

（4）实现队列的front()操作，方法如pop操作相同，只是在最后一步使用B.top()返回值。

（5）实现队列的back()操作，因为我们变量back_elem保存着最后一个输入的数据，故直接将其返回。

（6）实现队列的size()操作，和empty()操作，就是对A,B分别执行操作。

5、代码实现

#include <iostream>
#include <stack>
#include <string>
using namespace std;template<typename T>
class Queue {
private:stack<T>stackA;	//栈Astack<T>stackB;	//栈BT back_elem;	//用于存储新添加的元素
public:void push(T elem);	//将新元素压入队列（压入栈A）中void pop();			//将元素弹出队列（从栈B中弹出）T front();			//队首元素T back();			//队尾元素int size()const;    //队列长度bool empty()const;  //队列是否为空
};/*
入队操作
实现队列的push操作， 每次进行添加操作，都会相应得对栈A进行添加元素。并对back_elem赋值
*/
template<typename T>
void Queue<T>::push(T elem)
{stackA.push(elem);//将元素压入队列back_elem = elem;	//存储新添加的元素
}/*
出队操作
实现队列的pop操作，每次进行删除操作，因为栈B负责pop操作。
首先判断栈B是否为空？
a.如果栈B为空，则判断A是否为空？如果A也为空，则输出错误信息，此时队列为空。如果A不为空，则将栈A中的所有数据存储到B中。执B.push(A.top()), A.pop().然后在对栈B执行，B.pop()操作，将队列的头元素删除
b.如果栈B不为空， 则直接对栈B执行 B.pop()操作。*/
template<typename T>
void Queue<T>::pop()
{//判断栈B是否为空？if (!stackB.empty())	//栈B不为空， 则直接对栈B执行 B.pop()操作。{stackB.pop();}else if (!stackA.empty())	//栈B为空，则判断栈A是否为空？栈A不为空,则将栈A中的所有数据//存储到B中。执B.push(A.top()), A.pop().然后在对栈B执行，B.pop()操作，将队列的头元素删除{stackB.push(stackA.top());stackA.pop();}else{std::cout << "error pop(),empty queue!" << std::endl;}
}/*
队首元素
*/
template<typename T>
T Queue<T>::front()
{if (!stackB.empty()){return stackB.top();}else if (!stackA.empty()){while (!stackA.empty()){stackB.push(stackA.top());stackA.pop();}return stackB.top();}else{std::cout << "error front(),empty queue!" << std::endl;}
}/*
队尾元素
*/
template<typename T>
T Queue<T>::back()
{if (!empty()){return back_elem;}else{std::cout << "error back(),empty queue!" << std::endl;}
}/*
队列长度
*/
template<typename T>
int Queue<T>::size() const
{return stackA.size() + stackB.size();
}/*
队列是否为空
*/
template<typename T>
bool Queue<T>::empty() const {return stackA.empty() && stackB.empty();
}int main()
{Queue<int>queue;//入队操作queue.push(1);queue.push(2);queue.push(3);queue.push(4);cout << "Four times push() After:" << endl;//队首元素cout << "The queue front:" << queue.front() << endl;//队尾元素cout << "The queue back:" << queue.back() << endl;//队列sizecout << "The queue size:" << queue.size() << endl;//出队操作queue.pop();queue.pop();queue.pop();queue.pop();cout << "----------------------------" << endl;cout << "Four times pop() After:" << endl;//队首元素cout << "The queue front:" << queue.front() << endl;//队尾元素cout << "The queue back:" << queue.back() << endl;//队列sizecout << "The queue size:" << queue.size() << endl;//system("pause");return 0;
}

结果：

Four times push() After:
The queue front:1
The queue back:4
The queue size:4
----------------------------
Four times pop() After:
error front(),empty queue!
The queue front:260750304
error back(),empty queue!
The queue back:260750304
The queue size:0
请按任意键继续. . .

6、时间复杂度

入队操作的时间复杂度显然是O(1)。至于出队操作，如果涉及到栈A和栈B的元素迁移，时间复杂度是O(n)，如果不用元素迁移，时间复杂度是O(1)。