7、栈(一种特殊的线性表，只能固定在一端进行插入、删除操作 可分为顺序栈结构和链式栈结构)
7.1、栈的特性
递归的本质 栈
1、递归是函数里调用自身
2、必须有一个明确的递归出口
3、在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，因此递归次数过多容易造成栈溢出
递归的基本思想：
1、是把规模较大的一个问题，分解成规模较小的多个子问题去解决
2、先解决子问题，再基于子问题来解决当前问题
递归和内存：每次递归调用都在内存中生成一个新的函数副本(仅仅是一些相关的变量)，一旦函数结束(即返回某些数据)，改返回函数的副本就从内存中删除。
递归一般用于解决三类问题：
1、数据的定义是按递归定义的。（Fibonacci函数，n的阶乘）
2、问题解法按递归实现。（动态规划/分治/回溯）归并排序和快速排序用到了递归的思想
3、数据的结构形式是按递归定义的。（二叉树的/先/中/后序遍历，图的深度/广度优先搜索）
7.2、栈的使用场景 美团
- 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中
- JVM中的栈帧
- 处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数、区域变量等数据存入堆栈中
- 表达式的转换和求值
- 二叉树的遍历
- 图的深度优先搜索
- 浏览器的前进、后退功能
- 字符串反转
1、栈在表达式求值中的应用：(一个保存操作符的栈，另一个是保存运算符的栈)
我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较(栈顶元素优先级高就取出运算符，从操作数栈取两个操作数，结果压入操作数栈)
- LeetCode150 逆波兰表示式求值(后缀表达式)(逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序)
public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (int i = 0; i < tokens.length; i++) { String str = tokens[i]; if (str.length() == 1) { char ch = str.charAt(0); if (ch - '0' >= 0 && ch - '0' <= 9) { Integer a = Integer.valueOf(str); stack.push(a); } else {//如果是运算符 if (stack.size() < 2) return 0; int num2 = stack.pop(); int num1 = stack.pop(); switch (ch) { case '+': stack.push(num1 + num2); break; case '-': stack.push(num1 - num2); break; case '*': stack.push(num1 * num2); break; case '/': stack.push(num1 / num2); break; } } } else { int n = Integer.valueOf(str); stack.push(n); } } return stack.pop(); }
栈在括号匹配中的应用：(我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号)
- LeetCode20：有效的括号 给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效
public class 有效的括号 { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); char[] chars = s.toCharArray(); for (char aChar : chars) { if (stack.size() == 0) { stack.push(aChar); } else if (isSym(stack.peek(), aChar)) { stack.pop(); } else { stack.push(aChar); } } return stack.size() == 0; } //括号是否能匹配成功 private boolean isSym(char c1, char c2) { return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}'); } }
变体1：给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度 例如：输入: "(()"输出: 2 输入: “)()())” 输出: 4
对于这种括号匹配问题，一般都是使用栈，我们先找到所有可以匹配的索引号，然后找出最长连续数列！O(nlogn)
public class 最长有效括号 { public int longestValidParentheses(String s) { if (s == null || s.length() == 0) return 0; Deque<Integer> stack = new ArrayDeque<>(); stack.push(-1); //System.out.println(stack); int res = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') stack.push(i); else { stack.pop(); if (stack.isEmpty()) stack.push(i); else { res = Math.max(res, i - stack.peek()); } } } return res; } }
思路2：动态规划
public int longestValidParentheses(String s) { if (s == null || s.length() == 0) return 0; int[] dp = new int[s.length()];//状态转移表 下标表示对应考察元素 返回值表示最长有效括弧 int res = 0; for (int i = 0; i < s.length(); i++) { if (i > 0 && s.charAt(i) == ')') { if (s.charAt(i - 1) == '(') { dp[i] = (i - 2 >= 0 ? dp[i - 2] + 2 : 2); } else if (s.charAt(i - 1) == ')' && i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') { dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0); } } res = Math.max(res, dp[i]); } return res; }
编程题5：如何实现浏览器的前进、后退功能？
我们使用两个栈，X和Y，我们把首次浏览的页面依次压入栈X，当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据依次放入栈Y.当我们点击前进按钮时，
我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，那就说明没有页面可以继续后退浏览了。当栈Y中没有数据，那就说明没有页面可以点击前进按钮浏览了。
递归需要满足的三个条件：1、一个问题的解可以分解为几个问题的解；2、这个问题与分解后的子问题，除了数据规模不同，求解思路完全一样；3、存在递归终止条件
首先是定义ListNode，最基础的数据结构(包含int value，指向下一个结点点的指针)，然后有结点构成栈(包含pop/push/print/clear等功能)，最后实现浏览器功能()
public class 用栈实现浏览器的前进后退 { private String currentPage; //使用两个栈，X和Y private LinkedListBasedStack backStack; //LinkedListBasedStack为基于链表实现的栈，功能有入栈/出栈/获取栈顶元素/打印栈中元素 private LinkedListBasedStack forwardStack; //构造函数 public 用栈实现浏览器的前进后退() { this.backStack = new LinkedListBasedStack();//第一个栈 打开新页面时入栈，页面前进时入栈 后退时出栈 this.forwardStack = new LinkedListBasedStack();//第二个栈 前进时出栈 后退时入栈 } public void open(String url) { if (this.currentPage != null) { this.backStack.push(this.currentPage);//入栈 第一个栈 this.forwardStack.clear(); } showUrl(url, "Open"); } public boolean canGoBack() { return this.backStack.size() > 0; } public boolean canGoForward() { return this.forwardStack.size() > 0; } //后退功能 public String goBack() { if (this.canGoBack()) { this.forwardStack.push(this.currentPage);//第二个栈入栈 String backUrl = this.backStack.pop();//第一个栈出栈 showUrl(backUrl, "Back"); return backUrl; } System.out.println("* Cannot go back, no pages behind."); return null; } //前进功能 public String goForward() { if (this.canGoForward()) { this.backStack.push(this.currentPage);//第一个栈入栈 String forwardUrl = this.forwardStack.pop();//第二个栈出栈 showUrl(forwardUrl, "Foward"); return forwardUrl; } System.out.println("** Cannot go forward, no pages ahead."); return null; } public void showUrl(String url, String prefix) { this.currentPage = url; System.out.println(prefix + " page == " + url); } public void checkCurrentPage() { System.out.println("Current page is: " + this.currentPage); } }
编程题3：用数组实现一个顺序栈
public class 用数组实现栈 { private String[] items; // 数组 private int count; // 栈中元素个数 private int n; // 栈的大小 // 初始化数组，申请一个大小为n的数组空间 public 用数组实现栈(int n) { this.items = new String[n]; this.n = n; this.count = 0; } // 入栈操作 public boolean push(String item) { // 数组空间不够了，直接返回false，入栈失败。 if (count == n) return false; // 将item放到下标为count的位置，并且count加一 items[count] = item; ++count; return true; } // 出栈操作 public String pop() { // 栈为空，则直接返回null if (count == 0) return null; // 返回下标为count-1的数组元素，并且栈中元素个数count减一 String tmp = items[count - 1]; --count; return tmp; } }
编程题4：用链表实现一个链式栈
public class 用链表实现栈 { private ListNode top = null; //入栈 public void push(int value) { ListNode newNode = new ListNode(value, null); //判断是否栈空 if (top == null) { top = newNode; } else { newNode.next = top; top = newNode; } } //出栈 public int pop() { if (top == null) return -1; int value = top.data; top = top.next; return value; } public void printAll() { ListNode p = top; while (p != null) { System.out.print(p.data + " "); p = p.next; } System.out.println(); } }
8、队列部分知识点(关键点：确定队空/队满的判定条件)
8.1、具有某种特性的队列：循环队列、阻塞队列、并发队列(在片底层的系统、框架、中间件开发中，起着重要的作用，如高性能队列Disruptor、Linux环形缓存，用到了循环并发队列
java concurrent并发包利用ArrayBlockingQueue来实现公平锁等)
分类：顺序队列和链式队列(用数组实现的队列和链表实现的队列) 基于链表实现的无界队列(可能会导致过多的请求排队，响应时间较长)，基于数组实现的有界队列(大小有限)
8.2、队列使用场景 美团
- 排队请求；
- 数据库连接池；
- 高性能队列Disruptor
8.3、高性能队列Disruptor(内存消息队列) kafka
Disruptor(线程之间用于消息传递的队列)(应用apache Storm/canal/log4j2) 性能比常用的内存消息队列ArrayblockingQueue要高出一个数量级，它还因此获得过Oracle官方的Duke大奖
1、Disruptor详解？
基于循环队列保证数据被消费的顺序性。(实现了一个最简单的“生产者-消费者模型”)在这个模型中，“生产者”生产数据，并且将数据放到一个中心存储容器中。之后，“消费者”从中心存储容器中，取出数据消费。而存储数据的中心存储容器，是用什么样的数据结构来实现的呢？(1、基于链表实现的链式队列；2、基于数组实现的顺序队列(循环队列))
基于循环队列的生产者/消费者模型：思路(当队列满了之后，生产者就轮询等待，当队列空了后，消费者就轮训等待)
public class Queue { private Long[] data;//基于数据实现 private int size = 0, head = 0, tail = 0; public Queue(int size) { this.data = new Long[size]; this.size = size; } public boolean add(Long element) { if ((tail + 1) % size == head) return false;//循环队列满了 data[tail] = element; tail = (tail + 1) % size; return true; } public Long poll() { if (head == tail) return null;//循环队列为空 long ret = data[head]; head = (head + 1) % size; return ret; } } public class Producer { private Queue queue; public Producer(Queue queue) { this.queue = queue; } public void produce(Long data) throws InterruptedException { while (!queue.add(data)) { Thread.sleep(100);//说明添加失败，队列为满，等待消费 } } } public class Consumer { private Queue queue; public Consumer(Queue queue) { this.queue = queue; } public void comsume() throws InterruptedException { while (true) { Long data = queue.poll(); if (data == null) { Thread.sleep(100); } else { // TODO:...消费数据的业务逻辑... } } } }
上述代码存在的问题：多线程下，多个生产者写入的数据可能会互相覆盖，多个消费者可能会读取重复的数据
解决方法：1、加锁(同一时间只允许一个线程执行add()函数，相当于并行改成了串行)，可以使用CAS乐观锁机制减少加锁的粒度。
基于无锁的并发“生产者-消费者模型”
- 对于生产者来说，它往队列中添加数据之前，先申请可用空闲存储单元，并且是批量地申请连续的n个（n≥1）存储单元。后续往队列中添加元素，就可以不用加锁了；
- 对于消费者来说，处理的过程跟生产者是类似的。它先去申请一批连续可读的存储单元，当申请到这批存储单元之后，后续的读取操作就可以不用加锁了。
源码中，Disruptor采用的是RingBuffer和AvailableBuffer这两个结构
需要注意的地方：生产者A申请到一组连续的存储单元，假设下标是3到6的存储单元，生产者B紧跟着申请到下标是7到9的存储单元，那么3-6没有完全写入数据之前，7-9的数据是无法读取的，这是Disruptor实现思路的一个弊端。实际上，不管架构设计还是产品设计，往往越简单的设计思路，越能更好地解决问题。
4、实现一个消息队列系统
编程题1：用数组实现一个顺序队列
public class 用数组实现的队列 { // 数组：items，数组大小：n private String[] items; private int n = 0; // head表示队头下标，tail表示队尾下标 private int head = 0; private int tail = 0; // 申请一个大小为capacity的数组 public 用数组实现的队列(int capacity) { items = new String[capacity]; n = capacity; } // 入队 public boolean enqueue1(String item) { // 如果tail == n 表示队列已经满了 if (tail == n) return false; items[tail] = item; ++tail; return true; } //入队操作，将item放入队尾 并更新head/tail的索引 可以动态扩容的队列 public boolean enqueue2(String item) { // tail == n表示队列末尾没有空间了 if (tail == n) { //tail ==n && head==0，表示整个队列都占满了 if (head == 0) return false;// 表示整个队列都占满了 // 数据搬移 for (int i = head; i < tail; ++i) { items[i - head] = items[i]; } //搬移完之后重新更新head和tail tail -= head; head = 0; } items[tail] = item; ++tail; return true; } // 出队 public String dequeue() { // 如果head == tail 表示队列为空 if (head == tail) return null; // 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了 String ret = items[head]; ++head; return ret; } }
编程题2：用链表实现一个链式队列
public class 基于链表实现的队列 { // 队列的队首和队尾 private ListNode head = null; private ListNode tail = null; // 入队 public void enqueue(String value) { if (tail == null) { //新建的队列 ListNode newNode = new ListNode(value, null); head = newNode; tail = newNode; } else { tail.next = new ListNode(value, null); tail = tail.next; } } // 出队 public String dequeue() { if (head == null) return null; String value = head.data; head = head.next; if (head == null) { tail = null; } return value; } public void printAll() { ListNode p = head; while (p != null) { System.out.print(p.data + " "); p = p.next; } System.out.println(); } }
编程题3：实现一个循环队列(最关键的是，确定好队空和队满的判定条件)（我使用数组实现）
队列为空的判断条件仍然是head == tail，当队满时，(tail+1)%n=head，循环队列会浪费一个数组的存储空间。
public class 循环队列 { //数组：items，数组大小：n private String[] items; private int n = 0; // head表示队头下标，tail表示队尾下标 private int head = 0; private int tail = 0; // 申请一个大小为capacity的数组 public 循环队列(int capacity) { items = new String[capacity]; n = capacity; } // 入队 public boolean enqueue(String item) { // 队列满了 if ((tail + 1) % n == head) return false; items[tail] = item; tail = (tail + 1) % n; return true; } // 出队 public String dequeue(){ // 如果head == tail 表示队列为空 if (head == tail) return null; String ret = items[head]; head = (head + 1) % n; return ret; } }
编程题4：实现一个双端队列 java中有工具包Deque
public class 自己动手实现双端队列 { private Object[] data; private int head = 0; private int tail = 0; public 自己动手实现双端队列(int k) { data = new Object[k]; } public boolean insertFront(int value) { if(isFull()){ return false; } head= decr(head); data[head] = value; return true; } public boolean insertLast(int value) { if(isFull()){ return false; } data[tail] = value; tail = incr(tail); return true; } public boolean deleteFront() { if(isEmpty()){ return false; } data[head] = null; head = incr(head); return true; } public boolean deleteLast() { if(isEmpty()){ return false; } tail = decr(tail); data[tail] = null; return true; } public int getFront() { if(isEmpty()){ return -1; } return (int)data[head]; } public int getRear() { if(isEmpty()){ return -1; } return (int) data[decr(tail)]; } public boolean isEmpty() { return head == tail && data[head] == null && data[tail] == null; } public boolean isFull() { return tail== head && data[head] != null && data[tail] != null; } //前进一步 private int incr(int index){ return ++index % data.length; } //后退一步 private int decr(int index){ return (--index + data.length) % data.length; } }
编程题5：滑动窗口最大值
public int[] maxSlidingWindow(int[] nums, int k){ if(nums==null||nums.length<2) return nums; //双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数按从大到小排序 LinkedList<Integer> list = new LinkedList(); // 结果数组 int[] result = new int[nums.length-k+1]; for(int i=0;i<nums.length;i++){ //保证从大到小 如果前面数小 弹出 while(!list.isEmpty()&&nums[list.peekLast()]<=nums[i]){ list.pollLast(); } //添加当前值对应的数组下标 list.addLast(i); //初始化窗口 等到窗口长度为k时 下次移动在删除过期数值 if(list.peek()<=i-k){ list.poll(); } //窗口长度为k时 再保存当前窗口中最大值 if(i-k+1>=0){ result[i-k+1] = nums[list.peek()]; } } return result; }
- 编程题6：两个栈实现队列
思路：用栈a栈b模拟队列q，a为插入栈，b为弹出栈，栈a提供入队功能，栈b提供出队功能。入队时，入栈a即可，出队时，分两种情况：
*1、栈b不为空，直接弹出栈b的数据 *2、栈b为空，则依次弹出栈a的数据，放入栈b中，再弹出栈b的数据。
public class 两个栈实现队列<E> { Stack<E> s1 = new Stack<E>();//E为链表或数组 Stack<E> s2 = new Stack<E>(); public synchronized void put(E e) { s1.push(e); } public synchronized E pop() { if (s2.isEmpty()) { while (!s1.isEmpty()) { s2.push(s1.pop()); } } return s2.pop(); } }
编程题7：使用两个队列实现栈
思路：确保有一个队列总是空的， 入栈：在任何一个非空队列中插入元素，检查队列q1是否为空，如果q1为空，那么对q2执行入队操作；
出栈：如果队列q1非空，那么从q1移n-1个元素到q2中，然后对q1中的最后一个元素执行出队操作并返回该元素。
public class 使用队列实现栈<E> { Queue<E> queue1 = new LinkedBlockingQueue<E>();//E为链表或数组; Queue<E> queue2 = new LinkedBlockingQueue<E>();; public void push(E data) { if (queue1.isEmpty()) { queue2.add(data); } else { queue1.add(data); } } public E Pop(){ int i,size; if (queue2.isEmpty()) { size = queue1.size(); i=0; while (i < size-1) { queue2.add(queue1.remove()); i++; } return queue1.remove(); }else { size = queue2.size(); i=0; while (i < size-1) { queue1.add(queue2.remove()); i++; } return queue2.remove(); } } }
8.4、写一个生产者-消费者队列 政采云问到了 ***非常好的题目 通过arrayblockingqueue的put/take+callable实现，详见后面的阻塞队列
- 1、可以通过阻塞队列实现 2、也可以通过wait-notify来实现 3、通过无锁的内存高性能队列Disruptor实现“生产者-消费者模型”
- 后续补充具体例子
