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

栈实现队列(图文)

第十三双眼睛2024-01-23【数据结构与算法】人已围观

简介栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

思路：定义两个栈，一个栈用来入栈，另一个用来出栈。入队列的逻辑很简单，负责入栈的直接入栈即可。出队列时，先判断负责出栈的栈是不是为空，如果不为空，则直接出栈，如果为空，就将负责入栈的栈中的数据全部出栈到负责出栈的栈，然后再出栈，peek也一个道理，判断是否为空需要两个栈都为空才是空。代码如下：

public 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()) {
return stack2.pop();
} else {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
if (!stack2.isEmpty()) {
return stack2.peek();
} else {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
return stack2.isEmpty() && stack1.isEmpty();
}
}

Tags：

很赞哦！ ()

上一篇：链表的中间节点(图文)

下一篇：返回列表