队列实现栈（leetcode225）
题目描述：请你仅使用两个队列实现一个后入先出（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
思路：
- 定义两个队列，一个主队列，一个辅助队列，模拟栈后进先出。
- 当入栈操作时，先将该数据入队辅助队列，然后主队列内容导入辅助队列（while循环），最后将将主队列和辅助队列进行交换。
- 其实，了解了上述思路（将当前加入元素加到已经按照栈排好的元素最前边），我们只需要一个队列即可。
复杂度分析
- 时间复杂度：入栈操作 O(n)，其余操作都是 O(1)。
入栈操作需要将queue 1中的 n个元素出队，并入队 n+1 个元素到queue 2 ，共有 2n+1 次操作，每次出队和入队操作的时间复杂度都是 O(1)，因此入栈操作的时间复杂度是 O(n)。
出栈操作和获取栈顶元素对应将 queue 1的前端元素出队，时间复杂度是 O(1)。
判断栈是否为空操作只需要判断queue 1是否为空，时间复杂度是 O(1)。 - 空间复杂度：O(n)，其中 n 是栈内的元素。需要使用两个队列存储栈内的元素。
代码实现：
class MyStack { private Queue<Integer> queue1; private Queue<Integer> queue2; public MyStack() { queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } public void push(int x) { queue2.offer(x); // 特别注意，while循环 while (!queue1.isEmpty()) { queue2.offer(queue1.poll()); } Queue<Integer> temp = queue1; queue1 = queue2; queue2 = temp; } public int pop() { return queue1.poll(); } public int top() { return queue1.peek(); } public boolean empty() { return queue1.isEmpty(); } }
使用一个队列实现（将当前加入的元素放在已经是栈顺序序列的最前边，实现后进先出原则而）
class MyStack { private Queue<Integer> queue; public MyStack() { queue = new LinkedList<>(); } public void push(int x) { queue.offer(x); int cnt = queue.size(); while (cnt-- > 1) { queue.offer(queue.poll()); } } public int pop() { return queue.poll(); } public int top() { return queue.peek(); } public boolean empty() { return queue.isEmpty(); } }
栈实现队列（leetcode232）
问题描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
- 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
要求：
- 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
示例：
输入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 1, 1, false] 解释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false
思路：
- 定义两个栈用于数据的输入和输出。
- 当进行pop和poll操作时，如果输出栈为空，那么将输入栈数据全部移到输出栈。所以，当移到输出栈中然后进行输出的时候（出队列），就满足先进先出的结构。
复杂度分析：
- 时间复杂度：push 和empty 为 O(1)，pop 和 peek 为均摊 O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)。
- 空间复杂度：O(n)O(n)。其中 n是操作总数。对于有 n 次 push 操作的情况，队列中会有 n 个元素，故空间复杂度为 O(n)。
代码实现：
class MyQueue { private Deque<Integer> inStack; private Deque<Integer> outStack; public MyQueue() { inStack = new LinkedList<>(); outStack = new LinkedList<>(); } public void push(int x) { inStack.push(x); } // 获取栈中的元素时，需要检查输出栈是否为空 public int pop() { if (outStack.isEmpty()) { inToOut(); } return outStack.pop(); } public int peek() { if (outStack.isEmpty()) { inToOut(); } return outStack.peek(); } public boolean empty() { return inStack.isEmpty() && outStack.isEmpty(); } // 将输入栈中的元素移到输出栈 private void inToOut() { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } }
对于均摊复杂度的说明：参考@宫水三叶
我们先用另外一个例子来理解「均摊复杂度」，大家都知道「哈希表」底层是通过数组实现的。
- 正常情况下，计算元素在哈希桶的位置，然后放入哈希桶，即插入操作复杂度为 O(1)，假定是通过简单的“拉链法”搭配「头插法」方式来解决哈希冲突。
- 但当某次元素插入后，「哈希表」达到扩容阈值，则需要对底层所使用的数组进行扩容，这个复杂度是 O(n)
- 显然「扩容」操作不会发生在每一次的元素插入中，因此扩容的 O(n) 都会伴随着 n 次的 O(1)，也就是 O(n) 的复杂度会被均摊到每一次插入当中，因此哈希表插入仍然是 O(1)的。
同理，我们不是发生在每一次的「输出操作」中，而是集中发生在一次「输出栈为空」的时候，因此 pop 和 peek 都是均摊复杂度为 O(1)的操作。
补充：Queue接口分析：add和offer区别，remove和poll方法到底啥区别
这些方法的主要区别在于，如果执行失败，是抛出异常还是返回值。
- queue的增加元素方法add和offer的区别在于，add方法在队列满的情况下将选择抛异常的方法来表示队列已经满了，而offer方法通过返回false表示队列已经满了；在有限队列的情况，使用offer方法优于add方法；
- remove方法和poll方法都是删除队列的头元素，remove方法在队列为空的情况下将抛异常，而poll方法将返回null；
- element和peek方法都是返回队列的头元素，但是不删除头元素，区别在与element方法在队列为空的情况下，将抛异常，而peek方法将返回null
总结：我们一般希望抛出返回值，优先使用offer，poll和peek方法。
