李明徽的算法|剑指Offer（面试题9-1）——用两个栈实现队列李明徽的数据结构|面试题

剑指Offer（面试题9-1）题目请用栈实现一个队列，支持如下四种操作：

push(x) – 将元素x插到队尾；
pop() – 将队首的元素弹出，并返回该元素；
peek() – 返回队首元素；
empty() – 返回队列是否为空；

注意：

你只能使用栈的标准操作：push to top，peek/pop from top, size 和 is empty；
如果你选择的编程语言没有栈的标准库，你可以使用list或者deque等模拟栈的操作；
输入数据保证合法，例如，在队列为空时，不会进行pop或者peek等操作；

样例

MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false

思路 ? 在做这道题之前，我们应该先搞清楚栈和队列的特点：栈是一种后入先出的数据结构，而队列是一种先入先出的数据结构
? 我们可以通过两个栈来实现一个队列，st1作为接收入队元素的栈，st2作为控制出队元素的栈，当我们要入队时，就将入队元素压入st1中，这时我们发现，如果需要出队，根据队列先入先出的特性，st1的栈底元素需要最先被弹出，这时就要用到第二个栈st2了，我们将st1中所有的元素全部出栈，并依次压入st2，可以发现，因为栈是后入先出的数据结构，st1的栈顶元素会被压入st2的栈底，而我们要得到的最先入队的元素，也就是原st1的栈底元素，此时在st2的栈顶，我们直接对st2进行出栈操作，就可以得到需要出队的元素了
【李明徽的算法|剑指Offer（面试题9-1）——用两个栈实现队列】? 这里我们需要注意，每次出栈时，我们应该先检测st2中是否还有值，如果有值我们就不需要将st1的元素压入st2中，直接从st2出栈即可，下面是代码，这里我是用 Java 中自带的栈，使用数组模拟栈也是完全可以的
代码

class MyQueue {private Stack st1; private Stack st2; /** Initialize your data structure here. */ public MyQueue() { st1 = new Stack(); st2 = new Stack(); }/** Push element x to the back of queue. */ public void push(int x) { st1.push(x); }/** Removes the element from in front of queue and returns that element. */ public int pop() { if (st2.empty()) { while (!st1.empty()) st2.push(st1.pop()); } return st2.pop(); }/** Get the front element. */ public int peek() { if (st2.empty()) while (!st1.empty()) st2.push(st1.pop()); return st2.peek(); }/** Returns whether the queue is empty. */ public boolean empty() { if (st1.empty() && st2.empty()) return true; return false; } }/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */