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

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

比如有栈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; // 出口栈
}

 

（全文完）

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