栈是一中先进后出的数据结构,而队列是一种先进先出的数据结构,我们可以用两个栈stack1和stack2来模拟队列。在不弹出元素之前,我们把所有的元素都压入stack1,比如压入{a1,a2,a3},此时a1位于栈底,a3位于栈顶。
在需要弹出元素的时候,我们把栈1中的元素依次弹出,然后再压入stack2.次数stack2中元素的顺序为{a3,a2,a1}此时a1处于栈顶,a3处于栈底,stack2中元素的弹出顺序刚好与入队的顺序相同。
代吗如下:
#include<iostream> #include<stack> using namespace std; template<class T> class CQueue { public: CQueue(); ~CQueue(); void Push(const T&); T Pop(); private: stack<T> stack1; stack<T> stack2; }; template<class T> CQueue<T>::CQueue() { //do nothing } template<class T> CQueue<T>::~CQueue() { while(stack1.size()) stack1.pop(); while(stack2.size()) stack2.pop(); } template<class T> void CQueue<T>::Push(const T& element) { stack1.push(element); } template<class T> T CQueue<T>::Pop() { if(stack2.size()==0) { while(stack1.size()) { T element= stack1.top(); stack2.push(element); stack1.pop(); } //把栈1中的节点全部置如栈2 } if(stack2.empty()) return -1; //程序异常 T head= stack2.top(); stack2.pop(); return head; } int main() { CQueue<int> MyQueue; MyQueue.Push(2); MyQueue.Push(5); MyQueue.Push(7); MyQueue.Push(9); cout<<MyQueue.Pop()<<endl; cout<<MyQueue.Pop()<<endl; cout<<MyQueue.Pop()<<endl; return 0; }
Reference《名企面试官精讲典型编程题》