栈-队列互相实现

两个栈实现队列

思路:

  • 循环 栈A元素出栈并入栈B,可实现 栈A元素倒序
  • 倒序后,栈B执行出栈相当于删除栈A栈底元素,即队列首元素
    • 如果栈B不为空:栈B还有已完成倒序的元素,直接返回栈顶元素
    • 否则,如果A为空,返回-1
    • 否则,如果A不为空,将A倒序进栈B,并返回栈B栈顶元素

class CQueue {
private static LinkedList<Integer> stack1,stack2;
public CQueue() {
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}

public void appendTail(int value) {
stack1.addLast(value);
}

public int deleteHead() {
if(!stack2.isEmpty()){
return stack2.removeLast();
}else{
if(stack1.isEmpty()) return -1;
while(!stack1.isEmpty()){
stack2.addLast(stack1.removeLast());
}
return stack2.removeLast();
}
}
}

两个队列实现栈

重点还是倒序的实现,看代码理解

class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;

public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}

public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}

public int pop() {
return queue1.poll();
}

public int top() {
return queue1.peek();
}

public boolean empty() {
return queue1.isEmpty();
}
}