题目：
题意：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 输入：
["CQueue","appendTail","deleteHead","deleteHead"]
这一行表示每一行代码的操作
[[],[3],[],[]]
这个表示每一行代码操作所需要的参数
举例：
CQueue 表示新建一个CQueue对象，对应的所需参数为[]，即此操作不需要参数。
appendTail 表示执行一个appendTail()操作，对应要被操作的元素为3。
deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。
deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。
以上的输入其实是一个代码执行的步骤描述与其对应所需参数。
即两个纬度：
1、操作描述
2、此次操作所需参数
3、操作描述与操作所需参数是通过默认顺序一一对应的。
|
题解：
1、方法一：使用普通的Stack对象实现
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
| public class CQueue {
Stack stack1 = null;
Stack stack2 = null;
public CQueue() {
stack1 = new Stack();
stack2 = new Stack();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if (stack2.empty()){
if (stack1.empty()) {
return -1;
}
while (!stack1.empty()) {
stack2.add(stack1.pop());
}
return (int)stack2.pop();
}else {
return (int)stack2.pop();
}
}
}
|
2、方法二：使用LinkedList双向链表来实现（优解）
如果你使用Stack的方式来做这道题，会造成速度较慢； 原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。 可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。 但是我的意思不是像100%代码那样直接使用一个LinkedList当做队列，那确实是快，但是不符题意。 贴上代码，这样的优化之后，效率提高了40%，超过97%。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class CQueue {
LinkedList<Integer> stack1;
LinkedList<Integer> stack2;
public CQueue() {
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}
public void appendTail(int value) {
stack1.add(value);
}
public int deleteHead() {
if (stack2.isEmpty()) {
if (stack1.isEmpty()) return -1;
while (!stack1.isEmpty()) {
stack2.add(stack1.pop());
}
return stack2.pop();
} else return stack2.pop();
}
}
|