莱芜区政协网站,建设娱乐网站的要求,大庆企业做网站,网页设计如何换行✅面试编程题#xff1a;如何用队列实现一个栈 #x1f4a1;典型回答 #x1f4a1;典型回答
使用两个队列可以实现一个栈#xff0c;一个队列用来存储栈中的元素#xff0c;另一个队列用来在pop操作时暂存元素。
上才艺#xff1a;
import java.util.LinkedList;
impo… ✅面试编程题如何用队列实现一个栈 典型回答 典型回答
使用两个队列可以实现一个栈一个队列用来存储栈中的元素另一个队列用来在pop操作时暂存元素。
上才艺
import java.util.LinkedList;
import java.util.Queue;public class MyStackT {private QueueT queue; // 主队列private QueueT tempQueue; // 辅助队列public MyStack() {queue new LinkedList();tempQueue new LinkedList();}// 添加元素到栈顶public void push(T element) {queue.offer(element);}// 弹出栈顶元素并返回public T pop() {if (isEmpty()) {throw new RuntimeException(stack is empty);}// 将主队列中除了最后一个元素外的所有元素移到辅助队列中while (queue.size() 1) {tempQueue.offer(queue.poll());}T element queue.poll(); // 获取最后一个元素QueueT temp queue; // 交换主队列和辅助队列的引用queue tempQueue;tempQueue temp;return element;}// 获取栈顶元素但不弹出public T peek() {if (isEmpty()) {throw new RuntimeException(stack is empty);}// 将主队列中除了最后一个元素外的所有元素移到辅助队列中while (queue.size() 1) {tempQueue.offer(queue.poll());}T element queue.poll(); // 获取最后一个元素tempQueue.offer(element); // 将最后一个元素放回主队列QueueT temp queue; // 交换主队列和辅助队列的引用queue tempQueue;tempQueue temp;return element;}// 判断栈是否为空public boolean isEmpty() {return queue.isEmpty();}
}
其中push方法用来入栈直接将元素加入queue队列中。
pop方法用来出栈先将queue队列中的元素倒入tempQueue队列中直到queue队列中只有一个元素将其弹出即可。
peek方法用来获取栈顶元素与pop方法类似只是在弹出元素之前需要先将其加入tempQueue队列中
isEmpty方法用来判断栈是否为空如果queue队列为空则栈为空。
这个实现的时间复杂度为O(n)空间复杂度为O(n)其中n为栈中元素的个数。
