原题:用两个栈实现一个队列。
思想:
1.栈的特点不就是 先进后出,队列的特点就是先进先出。
2.用两个栈实现先进先出的功能;
图示:假设入队数据为 : 1,2,3,4,5,6,
,
红色方框中的 push 和 pop 等效为队列的push 和 pop
1.push就和栈stack1的push一样,没什么需要交代的:队列的插入push代码:
//入队 template<class T> void Queue<T>::Push(T A) { stack1.push(A); }push完成,栈stack1中的数据 像图1;即就是入栈后的顺序;
2.pop见图1到图2,将栈stack1出栈,将出栈的数据入栈到stack2中,之后的数据为stack2中所示,之后出栈,即就是出队列,依次出队,即依次出栈;
3.图三所示,意思为,如果stack2不为空,那么stack2中的数据定是stack1中出栈的结果,这个时候如果出栈,需要,先将stack2中的数据出栈,即出队;
看完整代码:
#include <iostream> #include <stack> using namespace std; /*两个栈实现队列*/ template<class T> class Queue { public: Queue() {} ~Queue() {} public: void Push(T A); int Pop(); private: stack<T> stack1; stack<T> stack2; }; //入队 template<class T> void Queue<T>::Push(T A) { stack1.push(A); } //出栈 template<class T> int Queue<T>::Pop() { int node = 0; if(stack2.empty()) { while(!stack1.empty()) { int num = stack1.top(); stack2.push(num); stack1.pop(); } } node = stack2.top(); stack2.pop(); return node; } void Test() { Queue<int> s1; s1.Push(1); s1.Push(2); s1.Push(3); s1.Push(4); s1.Push(5); s1.Push(6); s1.Push(7); for(int i = 0; i < 7; i++) { cout<<s1.Pop()<<"->"; } cout<<"NULL"<<endl; } int main() { Test(); return 0; }赐教!