题目描述：（栈和队列）
09——用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )；
解题思路：
1.栈无法去实现队列功能：栈底元素无法直接删除，需要将上方的所有元素出栈
2.使用双栈即可实现列表倒序及列表元素删除功能
对于这题我们可以直接使用两个函数，利用栈A用于加入队尾操作，栈B用于删除操作（将A元素倒序）
1 class CQueue{ 2 3 LinkedList<Integer> A.B; 4 public CQuere(){ 5 6 A = new LinkedList<Integer>(); 7 B = new LinkedList<Integer>(); 8 } 9 //加入操作 10 public void appendTail(int value){ 11 12 A.addLast(value); 13 14 } 15 16 public int deleteHead(){ 17 18 if(!B.isEmpty()) return B.removeLast(); 19 if(A.isEmpty()) return -1; 20 while(!A.isEmpty()){ 21 B.addLast(A.removeLast()); 22 } 23 return B.removeLast(); 24 } 25 26 }
30——定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
解题思路：
由于普通栈的push()和pop()函数的复杂度为O(1) ；而获取栈的最小值min() 函数需要遍历整个栈，复杂度为O(N)
我们如果要降低复杂度的话，可以建立通过辅助栈实现
数据栈A：栈A用于储存所有元素，保证入栈的push函数，出栈的pop函数，及获取栈顶的top函数的正常逻辑
辅助栈B：栈B用来储存A中所有“非严格降序”的元素，栈A中的最小元素始终对应栈B的栈顶元素，所以min函数只要返回B的栈顶元素即可
1 class MinStack{ 2 3 Stack<Integer> A,B; 4 public MinStack(){ 5 6 A = new Stack<Integer>(); 7 B = new Stack<Integer>(); 8 } 9 10 public void push(int x){ 11 A.add(x); 12 if(B.isEmpty() || B.peek() >= x){ 13 B.add(x); 14 } 15 } 16 public void pop(){ 17 18 if(A.pop().equals(B.peek()){ 19 B.pop(); 20 } 21 } 22 public int top(){ 23 return A.peek(); 24 } 25 26 public int min(){ 27 return B.peek(); 28 } 29 }