题目二：实现一个特殊的栈，在实现栈的基本功能的基础上，再返回栈中最小元素的操作。 【要求】 1、pop\push\getMin操作的时间复杂度都是O(1) 2、设计的栈类型可以使用现成的栈结构
思路解析
设计两个栈一个栈作为数据栈，另一个栈用来存储最小值数据栈每压入一个数，就要与最小值栈的栈顶进行比较，如果栈顶较小，最小值栈压入最小值，如果新来的数较小，则最小值栈压入新来的数，即可用O(1)实现当数弹出去的时候，两个栈都要同时弹出去，保持最小值的同步，这个是很重要的 import java.util.Stack; public class ZuoShen_mystack { /*题目二：实现一个特殊的栈，在实现栈的基本功能的基础上，再返回栈中最小元素的操作。 【要求】左神b站初级班3 1、pop\push\getMin操作的时间复杂度都是O(1) 2、设计的栈类型可以使用现成的栈结构*/ private Stack<Integer> data; private Stack<Integer> mins; public ZuoShen_mystack() { this.data = new Stack<Integer> (); this.mins = new Stack<Integer> (); } public int getmin() { if(mins.isEmpty()) throw new RuntimeException("Your stack is empty"); return mins.peek();//应该使用peek函数而不是pop，因为peek的意思是返回栈顶的元素但是不弹出 } public void push(int num) { data.push(num); if(mins.isEmpty()) { mins.push(num); }else { //int d = num < mins.pop()? num:mins.pop();//不能用pop，因为会弹出来！！！ int d = num < mins.peek()? num:mins.peek(); mins.push(d); } } public void poll() { if(data.isEmpty()) throw new RuntimeException("Your stack is empty!"); data.pop(); mins.pop(); } }题目三：（1）如何仅用队列结构实现栈结构？ （2）如何仅用栈结构实现队列结构？ 图的深度优先遍历要用栈结构来实现，面试官会问你如何只用队列实现深度优先遍历，这个时候只需要用队列实现栈结构即可
（1）如何仅用队列结构实现栈结构： 要使用两个队列实现栈结构，如果想让后进的数据先出来，就把前面的n-1个数据都装到helper队列中，然后将剩下的最后一个数据返回给用户即可。
import java.util.Queue; import java.util.LinkedList; public class ZuoShen_twoqueuesstack { //如何仅用队列结构实现栈结构？使用两个队列实现栈结构 private Queue<Integer> data; private Queue<Integer> help; public ZuoShen_twoqueuesstack() { this.data = new LinkedList<Integer>(); this.help = new LinkedList<Integer>(); } public void put(int num) { data.add(num); } public int poll() { int size = data.size(); if(size == 0) throw new RuntimeException("The Stack is empty!"); while(size > 1) { int d = data.poll(); help.add(d); size = data.size(); } int res = data.poll(); swap(); return res; } public int peek() { if(data.isEmpty()) throw new RuntimeException("The stack is empty"); while(data.size() > 1) { help.add(data.poll()); } int res = data.poll(); help.add(res); swap(); return res; } public void swap() { Queue<Integer> tmp = data; data = help; help = tmp; } }（2）如何仅用栈结构实现队列结构？ 同样使用两个栈 第一个栈的 入栈顺序1,2,3 出栈顺序3,2,1 第二个栈的 入栈顺序3,2,1 出栈顺序1,2,3 这样以来即可实现栈结构变成队列结构
package base_learn; import java.util.Stack; public class ZuoShen_twostackqueue { //如何仅用栈结构实现队列结构？ //我的笨方法，每次弹出一个值以后，再倒值回去，维持原队列顺序，防止新加入的值破坏顺序 private Stack<Integer> data; private Stack<Integer> help; public ZuoShen_twostackqueue() { this.data = new Stack<Integer>(); this.help = new Stack<Integer>(); } public void put(int num) { data.push(num); } public int peek() { if(data.isEmpty()) throw new RuntimeException("The queue is empty!"); while(!data.isEmpty()) { help.push(data.pop()); } int res = help.peek(); swap(); return res; } public int poll() { if(data.isEmpty()) throw new RuntimeException("The queue is empty!"); while(!data.isEmpty()) { help.push(data .pop()); } int res = help.pop(); swap(); return res; } public void swap() { while(!help.isEmpty()) { data.push(help.pop()); } } } 根据左神的思想进行改进，栈的使用要有两个原则， 1.每次data栈倒数据的时候要全部倒完 2.当help栈中不为空的时候，data栈不能倒数据 只要满足这两个原则，就可以保证正确性 ```java import java.util.Stack; public class ZuoShen_twostackqueue { //如何仅用栈结构实现队列结构？ //改进 private Stack<Integer> data; private Stack<Integer> help; public ZuoShen_twostackqueue() { this.data = new Stack<Integer>(); this.help = new Stack<Integer>(); } public void put(int num) { data.push(num); } public int peek() { if(data.isEmpty()) throw new RuntimeException("The queue is empty!"); dao(); return help.peek(); } public int poll() { if(data.isEmpty()) throw new RuntimeException("The queue is empty!"); dao(); return help.pop(); } public void dao() { if(!help.isEmpty())//当help栈不为空时，数据栈不能倒数据 return; while(!data.isEmpty()) { help.push(data.pop()); } } }