225. 用队列实现栈
LeetCode题目要求
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
实现 MyStack 类:
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
注意:
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
示例
输入:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]
解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
解题思路
使用两个队列,一个是主队列,来操作 top、pop、empty 操作
一个备份队列,用于在 push 时交换 队列,
Deque
Deque
// 模拟过程如下:首次 q1 q2 均为空, 操作逻辑大致如下
// 1、[放入q2操作] 将元素 1 放入 q2 , q2 <- 1
// 2、[q1 元素到q2] 此时 q1 为空,无操作
// 3、[交换 q1 q2], 由于 q1 为空 交换后 此时 q1 <- 1 ; q2 为空
// 栈的结构 顶 1 底
// 4、[放入q2操作] 放入 元素2 到 q2, q2 <- 2
// 5、[q1 元素到q2] 此时 q1 不为空,将 q1 中的元素放入到 q2, 即 q2 <- 2 <- 1
// 6、[交换 q1 q2], 由于 q1 不为空,交换后 q1 <- 2 <- 1 , q2 <- 1
// 栈的结构 顶 2 - 1 底
上代码
lass MyStack {
// 两个队列实现栈
Deque<Integer> q1; //主队列
Deque<Integer> q2; //备份队列
public MyStack() {
q1 = new ArrayDeque<>();
q2 = new ArrayDeque<>();
}
// offerLast(e)
// peekFirst()
// pollFirst()
public void push(int x) {
// 放入元素是放入到 q2 中
q2.offerLast(x);
// 如果 q1 不为空,就把 q1 中的元素全部放入 q2 , 这里的操作可以画图理解
// 模拟过程如下:首次 q1 q2 均为空, 操作逻辑大致如下
// 1、[放入q2操作] 将元素 1 放入 q2 , q2 <- 1
// 2、[] 此时 q1 为空,无操作
// 3、[交换 q1 q2], 由于 q1 为空 交换后 此时 q1 <- 1 ; q2 为空
// 栈的结构 顶 1 底
// 4、[放入q2操作] 放入 元素2 到 q2, q2 <- 2
// 5、[] 此时 q1 不为空,将 q1 中的元素放入到 q2, 即 q2 <- 2 <- 1
// 6、[交换 q1 q2], 由于 q1 不为空,交换后 q1 <- 2 <- 1 , q2 <- 1
// 栈的结构 顶 2 - 1 底
while (!q1.isEmpty()) {
q2.offerLast(q1.pollFirst());
}
// 交换 两个 queue
Deque<Integer> tq = q1;
q1 = q2;
q2 = tq;
}
public int pop() {
return q1.pollFirst();
}
public int top() {
return q1.peekFirst();
}
public boolean empty() {
return q1.size() == 0;
}
}
后续拓展:使用单个队列模拟栈操作
附:学习资料链接
标签:q1,10,q2,队列,pop,push,225,Day,empty From: https://www.cnblogs.com/blacksonny/p/17038786.html