您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

用队列实现栈(图文)

第十三双眼睛2023-12-04【数据结构与算法】人已围观

简介用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路：创建两个队列，队列一用来存储元素，队列二用来临时辅助，当有元素入栈时，先直接将元素入队列二，如果队列一不为空的话，就让队列一的元素都出队列，然后入队列二，完毕以后，交换两个队列的指针，此时就完成了元素入栈，出栈时，直接将队列一中的元素出队列，并且栈顶指针指向队列一中的第一个元素，peek方法，直接返回队列一的第一个元素即可，判断空的方法直接判断队列一是否为空就行。代码如下：

public class MyStack {
int top;
Queue<Integer> queue1 = null;
Queue<Integer> queue2 = null;
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
public void push(int x) {
queue2.offer(x);
top = x;
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop() {
Integer res = queue1.poll();
if (!queue1.isEmpty()) {
top = queue1.peek();
} else {
top = 0;
}
return res;
}
public int top() {
return top;
}
public boolean empty() {
return queue1.isEmpty();
}
}

Tags：

很赞哦！ ()

上一篇：完全二叉树的节点个数(图文)

下一篇：翻转二叉树(图文)