《剑指offer》 09.用两个栈实现队列

剑指offer
留言

note: 这道题乍一看非常简单，当然做起来也很简单，但是中间过程如何简化就需要再想一想。每次删除和增加操作都需要“倒空”么？高效的回答当然是否定的。

题目描述

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

示例 1：

1
2
3
4
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

1
2
3
4
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

  • 1 <= values <= 10000
  • 最多会对 appendTail、deleteHead 进行 10000 次调用

方法一 暴力思考

思路

既然双栈实现，我就搞一个删除栈一个增加栈，每次执行删除操作前都将另一个栈进行清空，来保证删除或增加的元素的次序是正确的。

代码

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
34
35
36
37
38
39
40
41
42
43
44
45
class CQueue {
    
    stack<int> stk1;
    stack<int> stk2;
public:
    CQueue() {
        while(!stk1.empty()){
            stk1.pop();
        }

        while(!stk2.empty()){
            stk2.pop();
        }
    }
    
    void appendTail(int value) {
        while(!stk2.empty()){
            stk1.push(stk2.top());
            stk2.pop();
        }
        stk1.push(value);
    }
    
    int deleteHead() {
        while(!stk1.empty()){
            stk2.push(stk1.top());
            stk1.pop();
        }
        if(stk2.empty())
            return -1;
        else{
            int ans = stk2.top();
            stk2.pop();
            return ans;
        }

    }
};

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

复杂度

  • 时间复杂度：$O(n)$。执行每次操作我都需要调整栈。所以需要线性时间复杂度
  • 空间复杂度：$O(n)$。两个栈来存储元素

方法二

思路

仔细思考上面的思路，我们很快就会发现我们做了很多无用功。因为我们没有必要在添加的时候将所有的删除栈中的元素倒腾到添加栈，或者说我们没有必要时刻保证两个栈必有一个栈是空的。我们只需要在我们删除的时候，如果删除栈存在元素，直接删除删除栈中的元素，直到删除栈中的元素删除完了，我们再将添加栈中的元素捣腾到删除栈进行删除。

代码

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 {
	stack<int> stk1,stk2;
public:
    CQueue() {
		while(!stk1.empty()){
			stk1.pop();
		}
		while(!stk2.empty()){
			stk2.pop();
		}
    }
    
    void appendTail(int value) {
		stk1.push(value);
    }
    
    int deleteHead() {
		if(stk2.empty()){
			while(!stk1.empty()){
				stk2.push(stk1.top());
				stk1.pop();
			}
		}
		if(stk2.empty()){
			return -1;
		}
		else{
			int ans = stk2.top();
			stk2.pop();
			return ans;
		}
    }
};

复杂度分析

  • 时间复杂度$O(1)$。对于插入和删除操作，时间复杂度均为$O(1)$.插入显然是常数。删除操作虽然看上去线性时间复杂度，但是实际上因为每个元素最多从stk2中被push和pop一次。所以均摊下来每个元素被删除的时间复杂度仍然是$O(1)$。
  • 空间复杂度$O(n)$。用到两个栈来存储已有的元素。