问题描述
用两个栈实现队列用两个队列实现栈
问题分析
用两个栈实现队列
stackPush 用作 Push 操作，Push 是直接 push 进这个栈。stackPop 用作 Pop 操作，若 stackPop 当前不为空，那么直接 pop ,若为空，那么将 stackPush 全部倒入 stackPop 中，然后 stackPop 再 pop 出一个元素用两个队列实现栈
用两个队列 queue 队列 与 help 队列Push 时直接 push 进 queue队列Pop 时先检查queue队列是否为空，若为空，说明所要实现的栈中不存在元素。若不为空，则将 queue队列中的元素装入 help中，queue中只剩最后一个，那么这便是应该Pop的元素，将该元素pop。pop之后，交换两队列，原help队列作现queue，原queue作现help即可。
代码实现
package basic_class_03;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class MyStackAndQueueConvert {
public static class TwoStackQueue{
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;
public TwoStackQueue() {
this.stackPop =
new Stack<>();
this.stackPush =
new Stack<>();
}
public void push (
int pushInt) {
stackPush.push(pushInt);
}
public int poll() {
if (stackPop.isEmpty() && stackPush.isEmpty()) {
throw new RuntimeException(
"Queue is empty!");
}
else if (stackPop.isEmpty()) {
while (! stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
public int peek() {
if (stackPop.isEmpty() && stackPush.isEmpty()) {
throw new RuntimeException(
"Queue is empty!");
}
else if (stackPop.isEmpty()) {
while (! stackPush.isEmpty()) {
stackPop.push(stackPop.pop());
}
}
return stackPop.peek();
}
}
public static class TwoQueuesStack{
private Queue<Integer> queue;
private Queue<Integer> help;
public TwoQueuesStack() {
queue =
new LinkedList<>();
help =
new LinkedList<>();
}
public void push(
int pushInt) {
queue.add(pushInt);
}
public int peek() {
if (queue.isEmpty()) {
throw new RuntimeException(
"Stack is empty!");
}
while (queue.size() !=
1) {
help.add(queue.poll());
}
int res = queue.poll();
help.add(res);
swap();
return res;
}
public int pop() {
if (queue.isEmpty()) {
throw new RuntimeException(
"Stack is empty!");
}
while (queue.size() !=
1) {
help.add(queue.poll());
}
int res = queue.poll();
swap();
return res;
}
public void swap() {
Queue<Integer> temp = queue;
queue = help;
help = temp;
}
}
}
