剑指offer刷题(持续更新...)

本文最后更新于:1 年前

本栏目记录在 剑指offer 刷题中的一些思考和反思,持续更新…

如果觉得我代码太烂,欢迎留言拍砖。🎉

Tip

  • 建议PC端查看此文,因为有目录可以参考。
  • 此文只列举(浪费时间多的)部分题,如需讨论,欢迎留言或私信。

面试题09. 用两个栈实现队列

传送门:面试题09. 用两个栈实现队列

一、思路

入队时,直接压入 stack01;

出队时,将 stack01 中的元素,全部弹出,并压入 stack02,实现首尾顺序调换,让 stack02 栈顶弹出,再将 stack02 元素依次弹出,压入 stack01。

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
/*
执行用时 :1144 ms, 在所有 C++ 提交中击败了6.53%的用户
内存消耗 :111.2 MB, 在所有 C++ 提交中击败了100.00%的用户
*/

class CQueue {
public:
stack<int> stack01;
stack<int> stack02;

CQueue() {

}

void appendTail(int value) {
stack01.push(value);
}

int deleteHead() {
if (stack01.empty()) {
return -1;
} else {
while (!stack01.empty()) {
stack02.push(stack01.top());
stack01.pop();
}
}
int hand = stack02.top();
stack02.pop();
while (!stack02.empty()) {
stack01.push(stack02.top());
stack02.pop();
}
return hand;
}
};

二、优化

思路中的 “再将 stack02 元素依次弹出,压入 stack01” 为多余步骤。

因为只有两个操作,入队和出队。入队从 stack01 完成,直接压栈;出队从 stack02 完成,直接弹出顶部元素,无需考虑中间元素一起存放。

需增加判断,当 stack02 为空,需再次判断 stack01 是否为空

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
/*
执行用时:632 ms, 在所有 C++ 提交中击败了35.90%的用户
内存消耗:103.6 MB, 在所有 C++ 提交中击败了100.00%的用户
*/
class Queue {
public:
stack<int> stack01;
stack<int> stack02;

CQueue() {

}

void appendTail(int value) {
stack01.push(value);
}

int deleteHead() {
if (stack02.empty()) { //modified
if (stack01.empty()) { //modified
return -1;
} else {
while (!stack01.empty()) {
stack02.push(stack01.top());
stack01.pop();
}
}
}
int hand = stack02.top();
stack02.pop();
return hand;
}
};