思维导图：
1.栈（Stack）：
- 栈是一种线性表，只允许固定的一端进行插入和删除操作，栈中元素遵循着“先进后出”的原则。往栈中插入元素叫做压栈；栈中弹出删除元素叫做出栈。想象一下装满子弹的弹夹，先装的子弹最后才会被打出去；而最后装的子弹最先打出去，栈就和弹夹的类似。底层上看栈就类似于数组。
- 栈的使用方法
| 方法 | 作用 |
| push（x）； | 压栈，将元素x入栈 |
| pop（）； | 出栈，删除栈顶元素 |
| peek（）； | 获取栈顶元素，但不删除 |
| size（）； | 获取栈中有效的元素个数 |
| empty（）； | 检测栈是否为空，空返回 true |
- 栈和虚拟机栈还有函数栈帧不是一个东西！
2.栈的模拟实现：
底层是数组实现的
public class MyStack { public int[] elem; public int usedSize;//存放有效元素个数 public static final int DEFAULT_CAPACITY = 20;//默认容量 public MyStack(){ elem = new int[DEFAULT_CAPACITY]; } //压栈 public void push(int data){ if(isFull()){ elem = Arrays.copyOf(elem,elem.length*2); } elem[usedSize] = data; usedSize++; } //判断elem有没有满，满了返回true private boolean isFull() { return elem.length == usedSize; } //判断elem是否为空，空则返回true public boolean isEmpty(){ return usedSize==0; } //删除栈顶元素 public int pop(){ if(isEmpty()){ return -1; } int oldvalue = elem[usedSize-1]; usedSize--; return oldvalue; } //查看栈顶元素，不删除 public int peek(){ if(isEmpty()){ return -1; } int ret = elem[usedSize-1]; return ret; } //获取栈中元素个数 public int size(){ return usedSize; } }
3.栈的OJ题：
1.不可能的出栈顺序：出栈的时候也可以进栈。
2.逆波兰表达式（往栈中存放数字，遇到符号就从栈中拿出俩个数字，运算后结果放回栈中）。
public class Test { public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (String x : tokens){ if(!isOpeation(x)){ stack.push(Integer.parseInt(x)); }else{ //num2在+-*/的右边，num1在左边。顺序不能换 int num2 = stack.pop(); int num1 = stack.pop(); switch (x){ case "+": stack.push(num1+num2); break; case "-": stack.push(num1-num2); break; case "*": stack.push(num1*num2); break; case "/": stack.push(num1/num2); break; } } } return stack.pop(); } private boolean isOpeation(String str) { if(str.equals("+")||str.equals("-") ||str.equals("*")||str.equals("/")){ return true; } return false; } }
3.判断括号匹配（判断匹配有俩个条件，字符串遍历完成了；栈为空）。
class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); if(ch=='[' || ch=='{' || ch=='('){ stack.push(ch); }else{ //必须要判断栈是否为空，否则会报错 if(stack.empty()){ return false; } if(ch == ']' && stack.peek() == '[' ||ch == '}' && stack.peek() == '{' ||ch == ')' && stack.peek() == '('){ stack.pop(); }else{ return false; } } } //如果栈不为空，则左括号多 if(stack.empty()){ return true; }else{ return false; } } }
4.实现递归：逆序打印链表。
class Solution { //实现递归 public void printList(ListNode head){ if(head == null) return; if(head.next == null){ System.out.println(head.val+" "); return; } printList(head.next); System.out.println(head.val+" "); } //栈实现递归,使用到了单链表 public void printList2(ListNode head){ Stack<ListNode> stack = new Stack<>(); ListNode cur = head; while(cur != null){ stack.push(cur); cur = cur.next; } while(!stack.empty()){ System.out.print(stack.pop()); } } }
5.判断出栈次序是否匹配。
public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { if(pushA.length == 0 || popA.length == 0){ return false; } Stack<Integer> stack = new Stack<>(); int j = 0; for (int i = 0; i < pushA.length; i++) { stack.push(pushA[i]); //特别注意这个循环条件 while(i < popA.length && !stack.empty() //stack.peek()和popA[j]比较时用equal更好，==不严谨 && stack.peek().equals(popA[j])){ stack.pop(); j++; } } return stack.empty(); } }
4.队列（Queue）：
- 队列是允许一端进行插入元素和另外一端进行删除操作，队列遵循“先进先出”的原则。类似于大家排队做核酸，先来的人就先做。Queue是一个接口，底层是通过链表实现的；在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
- 队列的使用方法
| 方法 | 作用 |
| offer（x）； | 将元素x尾插放入队列 |
| poll（）； | 将队头元素移出队列，返回改元素 |
| peek（）； | 获取队头元素 |
| size（）； | 获取队列中有效元素的个数 |
| isEmpty（）； | 检测队列是否为空，空返回 true |
- 双端队列（Deque）：元素可以从队头入队和出队，也可以从队尾出队和入队。
5.队列的模拟实现：
底层是由单链表实现的采用链式存储，加上了一个尾节点，这样尾插法入队还是头节点出队时间复杂度都为O(1)。
public class MyQueue { static class ListNode{ public int val; public ListNode next; public ListNode(int val) { this.val = val; } } public ListNode head; public ListNode last;//队列的尾巴节点 //入队 public void offer(int data){ ListNode node = new ListNode(data); if(head == null){ head = node; last = node; }else{ last.next = node; last = last.next; } } //出队 public int poll(){ if(head == null){ return -1; } int oldvalue = head.val; if(head.next == null){ head = null; last = null; }else{ head = head.next; } return oldvalue; } //peek()查看当前队头元素是谁 public int peek(){ if(head == null){ return -1; } return head.val; } //检查队列是否为空 public boolean isEmpty(){ return head == null; } //获取队列中有效元素的个数 public int size(){ if(head == null) return 0; int count = 0; ListNode cur = head; while(cur != null){ count++; cur = cur.next; } return count; } }
6.队列的OJ题：
1.用队列实现栈（用到俩个队列，俩个队列之间元素的相互调整来实现栈的基本功能）。
public class MyStack { //用队列来实现栈 Queue<Integer> qu1; Queue<Integer> qu2; public int usedSize; public MyStack(){ qu1 = new LinkedList<>(); qu2 = new LinkedList<>(); } //入栈 public void push(int data){ if(!qu1.isEmpty()){ qu1.offer(data); } else if (! qu2.isEmpty()) { qu2.offer(data); }else{ qu1.offer(data); } usedSize++; } //出栈 public int poll(){ if (empty()) { return -1; } if(! qu1.isEmpty()){ //size()会发生变化，用cursize记录下来就好 int cursize = qu1.size(); for (int i = 0; i < cursize-1; i++) { int ret = qu1.poll(); qu2.offer(ret); } usedSize--; return qu1.poll(); }else{ int cursize = qu2.size(); for (int i = 0; i < cursize-1; i++) { int ret = qu2.poll(); qu1.offer(ret); } usedSize--; return qu2.poll(); } } //如果为空返回true private boolean empty(){ return usedSize==0; } //获取栈顶元素 public int peek(){ if (empty()) { return -1; } if(! qu1.isEmpty()){ int cursize = qu1.size(); int ret = -1; for (int i = 0; i < cursize; i++) { ret = qu1.poll(); qu2.offer(ret); } return ret; }else{ int cursize = qu2.size(); int ret = -1; for (int i = 0; i < cursize; i++) { ret = qu2.poll(); qu1.offer(ret); } return ret; } } }
2.用栈实现队列（用到俩个栈，将元素从一个栈转到另外一个栈从而完成队列的基本功能）。
//用栈来模拟实现队列 public class MyQueue { Stack<Integer> s1; Stack<Integer> s2; public MyQueue(){ s1 = new Stack<>(); s2 = new Stack<>(); } //入队 public void offer(int data){ s1.push(data); } //出栈 public int pop(){ if(isEmpty()){ return -1; } if(s2.empty()){ while(!s1.empty()){ s2.push(s1.pop()); } } return s2.pop(); } //查看队头元素 public int peek(){ if(isEmpty()){ return -1; } if(s2.empty()){ while(!s1.empty()){ s2.push(s1.pop()); } } return s2.peek(); } //检查元素是否为空，空返回 public boolean isEmpty(){ return s1.empty() && s2.empty(); } }
3.实现一个最小栈（用到俩个栈，一个存放push进来的元素，一个存放最小的元素）。
public class MinStack { Stack<Integer> s; Stack<Integer> minStack; public MinStack(){ s = new Stack<>(); minStack = new Stack<>(); } //入栈 public void push(int data){ s.push(data); if(minStack.empty()){ minStack.push(data); }else{ if(minStack.peek() >= data){ minStack.push(data); } } } //出栈 public void pop(){ if(!s.empty()) { int popV = s.pop(); int minV = minStack.peek(); if (popV == minV) { minStack.pop(); } } } //获取栈顶元素，不是删除 public int peek(){ if(!s.empty()){ return s.peek(); } return -1; } //获取栈顶最小元素 public int peekmin(){ if(!minStack.empty()){ return minStack.peek(); } return -1; } }
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
