深入理解栈（Stack）

���录

1. 栈（Stack）之概念

2. 栈（Stack）之模拟实现

3. 栈（Stack）之使用

4.栈（Stack）之使用场景

4.1 改变元素的序列

4.2 将递归转化为循环

4.3 括号匹配

4.4 逆波兰表达式求值

4.5 出栈入栈次序匹配

---

1. 栈（Stack）之概念

首先明确：

栈是一种特殊的线性表，它特殊在只能在一端进行插入删除操作，并且最重要的是先进后出

（1）栈顶：进行数据插入和删除操作的一端 

（2）栈顶：栈顶的另一端

（3）入栈：栈的插入操作，也叫做压栈/进栈，入数据在栈顶

（4）出站：栈的删除操作，出数据也在栈顶

 下面理解一下，先进后出，看图解

分析一下，

1. 栈是先进后出的，那么入栈和出栈的时间复杂度是多少

因为入栈和出栈的数据都是在栈顶进行操作的 ，所以

入栈时间复杂度O（1）  出栈时间复杂度O（1）

2. 前面说的顺序存储的方式，那么栈的链式存储是什么样的

 假设栈是以单向链表存储，那么插入数据有头插和尾插

（1）入栈是尾插法，那么时间复杂度就是O（N）

         出栈，删除尾结点也是O（N）        

（2）入栈是头插法，那么时间复杂度是O（1）从头结点插入不需要遍历链表

          出栈，删除头结点就是O（1）        

所以当栈的存储方式是链式时，并且是单链表，那么对比下来，

入栈就选头插法，出栈就删除头结点

3. 如果是以双向链表来看做栈，那么从哪里入哪里出 

（1）从头入栈，从头出栈

（2）从尾入栈，从尾出栈

两种时间复杂度都是O（1）因为双向链表有头结点和尾结点，两边入栈出栈都一样

---

2. 栈（Stack）之模拟实现

栈继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不过Vector的线程是安全的

先写一个栈

public int[] elem;    public int usedSize;    public static final int DEFAULT_CAPATI = 10;    public MyStack() {        elem = new int[DEFAULT_CAPATI];    }

  1.入栈push()

入栈前先要判断栈是否满的isFull()

    public boolean isFull() {        if (usedSize == elem.length) {            return true;        }    return false;    }

    public void push(int val) {        //判断栈满        if (isFull()) {            elem = Arrays.copyOf(elem,2*elem.length);        }        elem[usedSize] = val;        usedSize++;    }

2.删除栈顶元素pop()

删除栈顶元素前，先判断栈空isEmpty()

    public boolean isEmpty() {        return usedSize == 0;    }

如果栈是空的，还要写一个异常EmptyStackException

public class EmptyStackException extends RuntimeException{    public EmptyStackException() {    }    public EmptyStackException(String msg) {        super(msg);    }}

    public int pop() {        if (isEmpty()) {            throw new EmptyStackException("栈是空的");        }        int oldVal = elem[usedSize-1];        usedSize--;        return oldVal;    }

 3.获取栈顶元素，不删除peek()

    public int peek() {        if (isEmpty()) {            throw new EmptyStackException("栈是空的");        }        return elem[usedSize-1];    }

4.获取中有效元素个数getUsedSize()

    public int getUsedSize() {        return usedSize;    }

---

3. 栈（Stack）之使用

    public static void main(String[] args) {        Stack stack = new Stack();        stack.push(2);        stack.push(3);        stack.push(4);        stack.push(7);        System.out.println(stack.size());        System.out.println(stack.peek());        stack.pop();        System.out.println(stack.pop());    }

---

4.栈（Stack）之使用场景

4.1 改变元素的序列

（1）先看牛客上的一道题

 分析一下 ，答案选C

（2） 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

             A: 1,4,3,2      B: 2,3,4,1      C: 3,1,4,2       D: 3,4,2,1

 分析一下，答案选C

2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（）。 A: 12345ABCDE       B: EDCBA54321      C: ABCDE12345        D: 54321EDCBA 分析一下，答案选B

 

---

4.2 将递归转化为循环

写一个逆序打印链表

（1）递归

public class Demo01 {    static class Node{        public int val;        public Node next;        public Node(int val) {            this.val = val;        }    }    public Node head;    public void printList(Node head) {        if (head == null) {            return;        }        if (head.next == null) {            System.out.print(head.val + " ");            return;        }        printList(head.next);        System.out.print(head.val + " ");    }}

（2）非递归实现

既然栈是先进后出的，那么可以将数字依次放进去，然后再pop取出栈顶元素，打印出来，这不就实现了逆序打印

    public void printList2(Node head) {        Stack stack = new Stack();        Node cur = head;        //将元素全部依次放入栈中        while(cur != null) {            stack.push(cur);            cur = cur.next;        }        //给栈pop取出栈顶元素然后拿出val打印        while(!stack.empty()) {            Node top = stack.pop();            System.out.println(top.val + " ");        }    }

---

4.3 括号匹配

链接   20. 有效的括号 - 力扣（LeetCode）

题目要求

分析一下

 上代码

class Solution {    public boolean isValid(String s) {        Stack stack = new Stack();        for(int i = 0; i  
4.4 逆波兰表达式求值
 
链接 150. 逆波兰表达式求值 - 力扣（LeetCode）
 
在说这道题前先明白 逆波兰表达式又叫做后缀表达式
 
（1）后缀表达式又可以通过中缀表达式来转化出来（考研-选择题）
  
 所以中缀变后缀三步走
   
（1）按规则加括号  （2）将运算符放括号外面  （3）去掉所有括号
  
（2）后缀表达式计算结果（代码题）
  
后缀计算4步走
   
（1）将数字按顺序依次放入栈中
  
（2）遇到运算符后，拿出栈顶两个元素
  
（3）按这样的规则计算（ 次栈顶元素 运算符  栈顶元素  ）
  
（4）将计算的结果，继续放入栈中，继续执行前面操作
  
 好了，下面看一下这道题
  
根据前面的后缀计算4步走验证一下这个例子
   
class Solution {    public int evalRPN(String[] tokens) {        Stack stack = new Stack();        for(String x : tokens) {            if(!isOperation(x)) {                //不是加减乘除                //字符转成整数.放进栈中                stack.push(Integer.parseInt(x));            }else {                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 isOperation(String opera) {        if(opera.equals("+") || opera.equals("-") || opera.equals("*") || opera.equals("/")) {            return true;        }        return false;    }}
  
4.5 出栈入栈次序匹配
 
链接 栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
 
题目要求：
  
分析一下
  
 上代码 
 
import java.util.*;import java.util.ArrayList;public class Solution {    public boolean IsPopOrder(int [] pushA,int [] popA) {        Stack stack = new Stack();        int j = 0;      for(int i = 0; i