首页 > itarticle > 剑指offer-题9-用两个栈实现队列 解析

剑指offer-题9-用两个栈实现队列 解析

admin 11月 12, 2020 0

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
template<typename T>class 
{
public:
    CQueue();
    ~CQueue();

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

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

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

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

解析

解析题目一

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
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. 存取均拷贝栈数据，效率低下

深入分析，栈结构符合存储操作，无需改动；删除操作只需改变单个栈结构，一个当堆头，一个当堆尾。如图所示
动画演示
以下是优化后的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
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;
}

解析题目二

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
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许可协议署名非商业性使用相同方式共享
本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能