(二)用双栈实现队列

分析：队列是FIFO，而栈是FILO。这里考虑两个栈，mStack1和mStack2。push_back()操作时假设都push到mStack1中，如果需要front()操作或者pop_front()操作时，应该拿到mStack1中栈底的元素。这时就用到mStack2，把mStack1中的元素全部push到mStack2中，然后再进行mStack2的top()和pop()操作。理论上分析如果，每次pop_front()的都是最早进入的，而新加入元素都在mStack1的最上面，pop_front()的时候是最后的元素。

 

C++实现：

#include <iostream> #include <stack> #include <cassert> using namespace std; template <typename T> class stack2queue{ public: void pushBack(T); void popFront(); T& front(); bool empty() const; private: stack<T> mStack1; stack<T> mStack2; }; template <typename T> void stack2queue<T>::pushBack(T x){ mStack1.push(x); } template <typename T> void stack2queue<T>::popFront(){ if(mStack2.empty()){ while(!mStack1.empty()){ mStack2.push(mStack1.top()); mStack1.pop(); } } assert(!mStack2.empty()); mStack2.pop(); } template <typename T> T& stack2queue<T>::front(){ if(mStack2.empty()){ while(!mStack1.empty()){ mStack2.push(mStack1.top()); mStack1.pop(); } } assert(!mStack2.empty()); return mStack2.top(); } template <typename T> bool stack2queue<T>::empty() const{ return (mStack1.empty() && mStack2.empty()); } template <typename T> void printQueue(stack2queue<T> q){ cout << "From front to back:/t("; if(!q.empty()){ cout << q.front(); q.popFront(); while(!q.empty()){ cout << ", " << q.front(); q.popFront(); } }else{ cout << "NULL"; } cout << ")" << endl; } int main() { stack2queue<int> sq; sq.pushBack(1); printQueue(sq); sq.pushBack(2); printQueue(sq); sq.pushBack(3); printQueue(sq); sq.popFront(); printQueue(sq); sq.popFront(); printQueue(sq); sq.popFront(); printQueue(sq); return 0; }