225. 用队列实现栈
题目:请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push
、top
、pop
和 empty
)。
本题可采用一个队列或两个队列完成,这里我使用一个队列实现栈,更加简洁,理解起来也不难。
栈的特点是先进后出,队列则是先进先出。也就是说要让队列从先进先出转化为先进后出。
要实现这一点,只需让队列先进的元素弹出(除了最后一个元素),再让其添加到该队列中。
如上图所示,将4前面的所有元素弹出再添加到队尾, 就能得到右边栈相同的最外面的元素在最前面。需要注意的是,要想保持队列最后一个元素不动,进入while循环的size 必须为size-1;
完整代码如下:
class MyStack {
private Queue<Integer> q1;
public MyStack() {
q1 = new LinkedList<>();
}
public void push(int x) {
q1.add(x);
int size = q1.size();
size--; // 循环前size需减1
while(size > 0){
q1.add(q1.remove());
size--;
}
}
public int pop() {
return q1.remove();
}
public int top() {
return q1.peek();
}
public boolean empty() {
return q1.isEmpty();
}
}
232.用栈实现队列
题目:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push
、pop
、peek
、empty
)
要解决此题,需要准备两个栈,stack1 和 stack2 。 为了实现队列里的先进先出,需要将栈出口的方向反过来。如图所示:
原先stack1的出栈顺序是4 3 2 1 ,翻转其出口后,出栈顺序就和队列一样为1 2 3 4。
若想将出栈口颠倒 , 只需让stack1依次弹出并添加到stack2中。
完整代码如下:
class MyQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
标签:q1,队列,用栈,&&,size,stack2,public,stack1
From: https://blog.csdn.net/m0_73904503/article/details/139830811