使用两个栈实现一个队列
思路：使用两个栈来实现一个队列，插入操作使用Stack1来完成，删除操作使用Satck2，当Stack2为空的时候，将Stack1中所有的数据转移到Stack2中
使用两个队列实现一个栈
思路：用两个队列实现一个栈，在入栈操作时只将元素插入到非空队列中，空的队列用来做出栈操作，出栈时要得到的元素是非空队列的最后一个元素，将非空队列（size为n）的前n-1个元素转移到空队列中，第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
public class QueueImplementByTwoStacks {
private Stack stack1;
private Stack stack2;
public Q088QueueImplementByTwoStacks() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void offer(int o) { // 入队操作在stack1中进行
stack1.push(o);
}
public int poll() { // 出队操作
int ret = 0;
if (!stack2.isEmpty()) { //不为空的时候直接弹出stack2的栈顶
ret = stack2.pop();
} else { //为空的时候将stack1中所有数据转移到stack2中
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
if(!stack2.isEmpty()) {
ret = stack2.pop();
}
}
return ret;
}
}
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
public class StackImplementByTwoQueues {
private Queue queue1;
private Queue queue2;
public StackImplementByTwoQueues() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int o) { //push操作只在非空的队列中进行
if(queue1.isEmpty() && queue2.isEmpty()) {
queue1.offer(o);
}
if(!queue1.isEmpty()) {
queue1.offer(o);
} else if(!queue2.isEmpty()) {
queue2.offer(o);
}
}
public int pop() throws Exception { //将非空队列的中的数据转移到空队列中，留下最后一个作为栈pop的元素
int ret = 0;
if(queue1.isEmpty() && queue2.isEmpty()) {
throw new Exception("栈为空");
} else {
if(queue2.isEmpty()) {
while(queue1.size() > 1) {
queue2.offer(queue1.poll());
}
ret = queue1.poll();
} else if(queue1.isEmpty()) {
while(queue2.size() > 1) {
queue1.offer(queue2.poll());
}
ret = queue2.poll();
}
}
return ret;
}
}