1. 实现一个最小栈
题目：
思路：
把题目要求的最小栈内部分为两个栈，一个stack用于储存所有元素，另一个min_stack用于储存最小的元素
压入第一个元素时，这个元素就是当前栈里最小元素，所以不光要压入stack栈中也要压入min_stack栈中
压入第二个元素的时候，要判断这个元素是否小于min_stack里的栈顶元素，如果小于，则将其压入min_stack
总之min_stack栈顶元素要始终保持是栈里最小的元素
删除栈顶元素的时候，除了要弹出stack里的栈顶元素
还要判断这个栈顶元素是否和min_stack栈里的栈顶元素相同，如果相同则要把min_stack栈里的栈顶元素也弹出
因为min_stack只是辅助栈，一个元素如果在储存元素的栈里都没了，辅助栈里怎么能还有呢？
获取栈顶元素就简单了，直接用java自带的方法peek（）就好了，只是获取，不操作
检索最小元素就更简单了，min_stack栈是用来干嘛的？
就是用来存最小元素的嘛，直接弹出min_stack栈栈顶元素可以了
这个栈顶元素必然是整个栈里的最小元素
实现代码
class MinStack { Stack<Integer> stack; Stack<Integer> MinStack; public MinStack() {//构造两个栈，一个普通栈，一个辅助栈 stack = new Stack<>(); MinStack = new Stack<>(); } public void push(int val) { stack.push(val);//压入元素 if(MinStack.isEmpty()){ MinStack.push(val);如果两个栈都是空，也要将此元素压入辅助栈 } else{ if(val <= MinStack.peek())//如果新压入的元素小于辅助栈栈顶元素 MinStack.push(val);//将新元素压入辅助栈 } } public void pop() { //如果从普通栈中弹出的元素等于辅助栈的栈顶元素，那么也要将此元素从辅助栈弹出 if(stack.pop().equals(MinStack.peek())){//这里要用eqauls，不能用==，pop方法和peek方法返回的是一个object类型，也就是两个对象，我们要比较对象的值，如果用==，比较的是对象的地址 MinStack.pop();//弹出辅助栈栈顶元素 } } public int top() { if(MinStack.isEmpty()){ return -1; } return stack.peek();//查看普通栈栈顶元素 } public int getMin() { if(MinStack.isEmpty()){ return -1; } return MinStack.peek();//查看辅助栈栈顶元素 } }
2. 括号匹配问题
题目：
思路：
- 左括号和右括号是
匹配关系，考虑用栈的方法实现 - 栈里只放三种
左括号 - 遍历字符串，
遇到左括号，将其入栈，遇到右括号，就查看栈顶的左括号，看是否能匹配。如果能匹配上，就将此左括号出栈（删除），如果最后栈为空，那么它是有效的括号，反之不是。
实现代码
class Solution { public boolean isValid(String s) { if(s==null||s.length()==0){ return true; } //定义一个栈，来存放左括号 Stack stack = new Stack(); //遍历字符串 for(int i =0; i<s.length(); i++){ //获取当前i小标是一个啥字符 char ch = s.charAt(i); //判断当前的字符是哪个左括号，因为题上说 只有3种左括号。 if(ch=='('||ch=='['||ch=='{'){ stack.push(ch); }else{ //进入else 说明当前i下标是一个右括号 //但是 要判断栈空不空，有可能第一个括号就是右括号 if(stack.empty()){ //说明右括号多了 return false; } //获取栈顶元素，只是查看是否能和读取到的括号匹配，不是出栈 char tmp = (char)stack.peek(); if(tmp=='('&& ch == ')'||tmp=='['&& ch == ']'||tmp=='{'&& ch == '}'){ //如果有可匹配的，就出栈当前的栈顶的括号 stack.pop(); }else{ //说明括号不匹配 return false; } } } //字符遍历完了，判断栈是否为空 if(stack.empty()){//如果栈最终为空，说明括号刚好都匹配上了 return true; }else{//左括号多了 return false; } } }
3. 用队列实现栈
题目：
思路：
栈是先进后出，队列是先进先出，所以这里用两个队列来回倒，从而实现栈
抓住一个关键点，不管入栈还是出栈，都找不为空的队列进行操作
入栈时，找到不为空的队列，从队列尾部插入元素即可，就达到了入栈的效果
出栈时，找到不为空的队列，将size-1个元素加入到另一个空的队列里，然后把这个队列最后一个元素出列，就达到了出栈效果
返回栈顶元素方法与出栈类似（注意，只查看，不删除），不过要设置一个临时变量tmp储存最后出队的那个元素，而且最后出队的这个元素也要继续加入另一个队列，不然就是出栈操作了
实现代码：
class MyStack { //创建两个队列 Queue<Integer> que1; Queue<Integer> que2; public MyStack() { que1 = new LinkedList<>();//队列是接口，不能直接实例化 que2 = new LinkedList<>();//队列是由链表实现的，所以要用链表来实例化队列 } public void push(int x) { if(empty()){//一开始两个队列都是空的时候，默认将第一个元素插入到que1中 que1.offer(x); }else{//从第二个元素开始，哪个队列不为空，对哪个队列进行插入操作 if(que1.isEmpty()){ que2.offer(x); }else{ que1.offer(x); } } } public int pop() { if(empty()){ return -1; } //出栈也是找哪个队列不为空，就对哪个队列进行操作 if(que1.isEmpty()){ int size = que2.size(); for(int i =0 ; i<size-1 ;i++){ int tmp = que2.poll(); que1.offer(tmp); } return que2.poll(); }else{ int size = que1.size(); for(int i =0 ; i<size-1 ;i++){ int tmp = que1.poll(); que2.offer(tmp); } return que1.poll(); } } public int top() { if(empty()){ return -1; } //查看栈顶元素，和出栈类似，只不过记得把队列最后一个元素继续插入到另一个队列的最后 //不然就是出栈操作了 if(que1.isEmpty()){ int size = que2.size(); int tmp = -1; for(int i =0 ; i<size ;i++){ tmp = que2.poll(); que1.offer(tmp); } return tmp; }else{ int size = que1.size(); int tmp = -1; for(int i =0 ; i<size ;i++){ tmp = que1.poll(); que2.offer(tmp); } return tmp; } } public boolean empty() { return que1.isEmpty() && que2.isEmpty(); } }
