利用双栈来实现队列

利用双栈来实现队列

数据结构中,队列和栈是较为常用的 两个数据结构。它们各有自己的特点,栈特点是“先进后出”,队列是“先进先出”。

如果已经实现了一个栈的类,可以用它来构建一个队列类,其方法较为有意思。

比如有栈CStack, 其接口Push() 进栈,Pop() 出栈和IsEmpty() 判断是非栈空,基于栈的接口可以用来构造一个队列了,定义队列的接口入队列为InQueue(),出队列为OutQueue()。如下

思路:

1、OutQueue 内两个CStack成员:m_EnterStack、m_ExportStack;
2、调用数据进队列时候,OutQueue 把数据 入栈m_EnterStack内;
3、调用数据出队列时候,OutQueue 读取m_ExportStack 内的数据:
3.1) m_ExportStack 如果没有数据,把m_EnterStack 的数据全部Pop 出栈,之后入栈到m_ExportStack 内,之后跳到3.3;
3.2)m_ExportStack 如果存在数据,跳到3.3;
3.3)调用 m_ExportStack.Pop,取出数据,之后出队列。

图解:

双栈实现队列

伪代码:

class CQueue
{
public:
    bool IsEmpty()
    {
        return m_EnterStack.IsEmpty() && m_ExportStack.IsEmpty();
    }
    
    void InQueue(data)
    {
        m_EnterStack.Push(data);
    }

    data OutQueue()
    {
        if (m_ExportStack.IsEmpty()) {
            while(!m_EnterStack.IsEmpty()) {
                m_ExportStack.Push(m_EnterStack.Pop());
            }
        }

        return m_ExportStack.Pop();
    }


protected:
    CStack m_EnterStack;  // 入口栈
    CStack m_ExportStack; // 出口栈
}

 

(全文完)

原文链接:http://blog.yuccn.net/archives/758.html

(欢迎转载本站文章,但请注明作者和出处 云域 – Yuccn

发表评论

电子邮件地址不会被公开。 必填项已用*标注