剑指Offer09 - 用两个栈实现队列
Cleo Lv2
 2021-04-16 22:14:27    

题目描述

用两个栈实现一个队列。队列的生命如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入整数和在队列头部删除整数的功能。（若队列中没有元素，deleteHead操作返回-1）。

1
2
3
4
5
6
/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

思路

使用两个栈实现队列，考察的是栈和队列的工作方式。栈是后进先出，队列是先进先出。假设有栈s1和栈s2，分析如下：

  • 入队列：直接入栈s1
  • 出队列：
    • 如果栈s2为空，栈s1不为空，由于出栈是从栈顶弹出元素，而出队列是从队列首弹出元素，因此不能直接从栈s1出栈，需要借助栈s2。可以将s1中的元素逐个弹出并压入s2中，此时，最后入栈s1的就在栈s1的栈底，而最先入栈s1的元素在栈s2的栈顶。因此只要再从s2出栈，即可拿到最先入队列的元素。
    • 如果栈s2为空，栈s1也为空，则队列中没有任何元素，返回-1。
    • 如果栈s2不为空，可直接从s2出栈，得到的就是当前队列的队首元素。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class CQueue {
public:
    stack<int> s1, s2;

    CQueue() {
        while (!s1.empty())
            s1.pop();
        while (!s2.empty())
            s2.pop();
    }
    
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {
        int temp;
        if (s2.empty())
        {
            while (!s1.empty())
            {
                temp = s1.top();
                s1.pop();
                s2.push(temp);
            }
        }
        if (s2.empty())
            return -1;
        temp = s2.top();
        s2.pop();
        return temp;
    }
};