现在的位置: 首页 > 综合 > 正文

用两个栈实现队列

2013年10月27日 ⁄ 综合 ⁄ 共 1053字 ⁄ 字号 评论关闭

     栈是一中先进后出的数据结构,而队列是一种先进先出的数据结构,我们可以用两个栈stack1stack2来模拟队列。在不弹出元素之前,我们把所有的元素都压入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《名企面试官精讲典型编程题》

抱歉!评论已关闭.