队列算法之【用队列实现栈】

目录

LeetCode-225题

LeetCode-225题

使用队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶
• int pop() 移除并返回栈顶元素
• int top() 返回栈顶元素
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false

class MyStack {//内部使用的是一个队列private final Queue<Integer> queue;public MyStack() {queue = new LinkedList<>();}// 入栈：直接将元素添加到队列中public void push(int x) {queue.offer(x);}// 出栈：将队列中除了最后一个元素，其它元素先出队再进队public int pop() {int size = queue.size();for (int i = 0; i < size - 1; i++) {queue.offer(queue.poll());}// 此时出队的是最后进入的元素，保证后进先出的特点return queue.poll();}// 查看栈顶元素public int top() {int size = queue.size();for (int i = 0; i < size - 1; i++) {queue.offer(queue.poll());}Integer result = queue.poll();queue.offer(result);// 最后添加的元素为栈顶元素return result;}// 判空public boolean empty() {return queue.isEmpty();}
}