两个队列实现栈 思路:队列queue是专职进出栈的,队列help只是个中转站,起辅助作用。 入栈:直接入队列queue即可 出栈:把queue的除最后一个元素外全部转移到队help中,然后把刚才剩下queue中的那个元素出队列。之后把q2中的全部元素转移回q1中(或者两个队列互换) 入栈:
出栈:
import java.util.LinkedList;
import java.util.Queue;
public class QueuesStack {
private Queue<Integer> queue;
private Queue<Integer> help;
public QueuesStack() {
queue = new LinkedList<Integer>();
help = new LinkedList<Integer>();
}
private 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 void swap(){
Queue<Integer> tmp;
tmp = queue;
queue = help;
help = tmp;
}
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;
}
}
*两个栈实现队列 思路:
import java.util.Stack;
public class StacksQueue {
private Stack<Integer> stackPop;
private Stack<Integer> stackPush;
public StacksQueue() {
stackPop = new Stack<Integer>();
stackPush = new Stack<Integer>();
}
public void push(int pushInt) {
stackPush.push(pushInt);
}
public int peek() {
if(stackPush.empty() && stackPop.empty()) {
throw new RuntimeException("Queue is empty");
} else if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
public int poll() {
if(stackPush.empty() && stackPop.empty()) {
throw new RuntimeException("Queue is empty");
} else if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
}