剑指offer09.用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]

示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

class CQueue {public CQueue() {}public void appendTail(int value) {}public int deleteHead() {}
}

解题思路：

栈实现队列的出队操作效率低下：栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈。

列表倒序操作可使用双栈实现：设有含三个元素的栈 A = [1,2,3] 和空栈 B = [] 。若循环执行 A 元素出栈并添加入栈 B ，直到栈 A 为空，则 A = [] , B = [3,2,1] ，即栈 B 元素为栈 A 元素倒序。

利用栈 B 删除队首元素：倒序后，B 执行出栈则相当于删除了 A 的栈底元素，即对应队首元素。

函数设计：
加入队尾 appendTail() ： 将数字 val 加入栈 A 即可。
删除队首deleteHead() ： 有以下三种情况。
当栈 B 不为空： B中仍有已完成倒序的元素，因此直接返回 B 的栈顶元素。
否则，当 A 为空： 即两个栈都为空，无元素，因此返回 -1 。
否则： 将栈 A 元素全部转移至栈 B 中，实现元素倒序，并返回栈 B 的栈顶元素。

 

 

 

 

 

代码如下：

class CQueue {LinkedList<Integer> A, B;public CQueue() {A = new LinkedList<Integer>();B = new LinkedList<Integer>();}public void appendTail(int value) {A.addLast(value);}public int deleteHead() {if(!B.isEmpty()) return B.removeLast();if(A.isEmpty()) return -1;while(!A.isEmpty())B.addLast(A.removeLast());return B.removeLast();}
}

---

剑指 Offer 30. 包含 min 函数的栈 

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

class MinStack {public MinStack() {}public void push(int x) {}public void pop() {}public int top() {}public int min() {}
}

解题思路： 

普通栈的 push() 和 pop() 函数的复杂度为 O(1)O(1) ；而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N)O(N) 。

本题难点： 将 min() 函数复杂度降为 O(1)O(1) 。可借助辅助栈实现：

数据栈 A ： 栈 A 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。
辅助栈 B ： 栈 B 中存储栈 A 中所有 非严格降序 元素的子序列，则栈 A 中的最小元素始终对应栈 B 的栈顶元素。此时， min() 函数只需返回栈 B 的栈顶元素即可。

函数设计：
push(x) 函数： 重点为保持栈 B 的元素是 非严格降序 的；

执行「元素 x 压入栈 A」 ；
若「栈 B 为空」或「x ≤ 栈 B 的栈顶元素」，则执行「元素 x 压入栈 B」 ；
pop() 函数： 重点为保持栈 A , B 的 元素一致性 ；

执行「栈 A 元素出栈」，将出栈元素记为 y ；
若 「y 等于栈 B 的栈顶元素」，则执行「栈 B 元素出栈」；
top() 函数： 直接返回栈 A 的栈顶元素，即返回 A.peek() ；

min() 函数： 直接返回栈 B 的栈顶元素，即返回 B.peek() ；

 

 

 

 

 

 

采用 “非严格” 降序原因：

在栈 A 具有 重复 最小值元素时，非严格降序可防止栈 B 提前弹出最小值元素，示例如下：

代码如下：

注：Java 代码中，由于 Stack 中存储的是 int 的包装类 Integer ，因此需要使用 equals() 代替 == ，以比较对象的值。 

class MinStack {Stack<Integer> A, B;public MinStack() {A = new Stack<>();B = new Stack<>();}public void push(int x) {A.add(x);if(B.empty() || B.peek() >= x)B.add(x);}public void pop() {if(A.pop().equals(B.peek()))B.pop();}public int top() {return A.peek();}public int min() {return B.peek();}
}