剑指Offer-题9-用两个栈实现队列 | Orange's Blog

题目：用两个栈实现队列

题目一：用两个栈实现队列

用两个栈实现一个队列。队列的声明如下：请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。

template<typename T>class CQueue
{
public:
    CQueue();
    ~CQueue();

    void appendTail(const T& node);
    T deleteHead();

private:
    stack<T> stack1;
    stack<T> stack2;
};

题目二：用两个队列栈实现栈

用两个队列实现一个栈。请实现它的两个函数appendTail和deleteTail。

解析

解析题目一

栈：先进后出
堆：先进先出
想用栈实现堆，只能将栈倒放。好在有两个栈，可以倒序存取。故代码如下

template<typename T>
void CQueue<T>::appendTail(const T& node)
{
    while (!stack2.empty())
    {
        stack1.push(stack2.top());
        stack2.pop();
    }
    stack1.push(node);
}

template<typename T>
T CQueue<T>::deleteHead()
{
    while (!stack1.empty())
    {
        stack2.push(stack1.top());
        stack1.pop();
    }
    T temp = stack2.top();
    stack2.pop();
    return temp;
}

以上代码存在两大问题😭

1. stack2.pop() 未进行栈空判断
2. 存取均拷贝栈数据，效率低下

深入分析，栈结构符合存储操作，无需改动；删除操作只需改变单个栈结构，一个当堆头，一个当堆尾。如图所示

以下是优化后的代码

template<typename T>
void CQueue<T>::appendTail(const T& node)
{
    stack1.push(node);
}

template<typename T>
T CQueue<T>::deleteHead()
{
    if (stack2.empty())
        while (!stack1.empty())
        {
            stack2.push(stack1.top());
            stack1.pop();
        }
    if (stack2.empty())
        throw new exception("queue is empty");
    T temp = stack2.top();
    stack2.pop();
    return temp;
}

解析题目二

堆结构符合存储操作，无需改动；删除操作需转移中执行，故两个堆轮流使用。

template<typename T>
void CStack<T>::appendTail(const T& node)
{
    queue<T> saveQueue = !queue1.empty() ? queue1 : queue2;
    saveQueue.push(node);
}

template<typename T>
T CStack<T>::deleteTail()
{
    queue<T> readQueue = !queue1.empty() ? queue1 : queue2;
    queue<T> saveQueue = queue1.empty() ? queue1 : queue2;
    while (!readQueue.size() > 1)
    {
        saveQueue.push(readQueue.top());
        readQueue.pop();
    }
    if (saveQueue.empty())
        throw new exception("stack is empty");
    T temp = readQueue.top();
    readQueue.pop();
    return temp;
}

本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可