如何用两个栈来实现一个队列,并分析有关队列操作的运行时间。_百度知 ...

发布网友发布时间：2022-05-13 03:06

共1个回答

热心网友时间：2022-04-22 17:53

队列的操作主要有：入队，出队，返回队列长度，返回队首元素，判断队列是否为空。代码实现如下所示： #include <stack> #include <string> #include <iostream> #include <cassert> usingnamespace std; template <class T> class YL_Queue { public: void enqueue(const T &element); //入队 T dequeue(); //出队 T top(); //队首元素bool empty() const; //判断队列是否为空 size_t size() const; //队列的尺寸大小private: stack<T> inStack; stack<T> outStack; }; template <class T> void YL_Queue<T>::enqueue(const T &element) { inStack.push(element); } template <class T> T YL_Queue<T>::dequeue() { assert(!empty()); T temp; if (!outStack.empty()) { temp=outStack.top(); outStack.pop(); return temp; } else { while(!inStack.empty()) { temp=inStack.top(); inStack.pop(); outStack.push(temp); } temp= outStack.top(); outStack.pop(); return temp; } } template <class T> T YL_Queue<T>::top() { assert(!empty()); T temp; if (!outStack.empty()) { temp=outStack.top(); return temp; } else { while(!inStack.empty()) { temp=inStack.top(); inStack.pop(); outStack.push(temp); } temp= outStack.top(); return temp; } } template <class T> bool YL_Queue<T>::empty() const { return (size()==0); } template <class T> size_t YL_Queue<T>::size() const { return inStack.size()+outStack.size(); } void main() { YL_Queue<int> myqueue; myqueue.enqueue(1); myqueue.enqueue(2); myqueue.enqueue(3); myqueue.enqueue(4); myqueue.enqueue(5); cout<<"1队列的大小为: "<<myqueue.size()<<endl; cout<<"1队首的元素为: "<<myqueue.top()<<endl; myqueue.dequeue(); myqueue.dequeue(); cout<<"2队列的大小为: "<<myqueue.size()<<endl; cout<<"2队首的元素为: "<<myqueue.top()<<endl; myqueue.dequeue(); myqueue.dequeue(); myqueue.dequeue(); cout<<"3队列的大小为: "<<myqueue.size()<<endl; }