深入理解栈（Stack）

清疚 2023-09-28 14:02 162阅读 0赞

**目录**

1. 栈（Stack）之概念

2. 栈（Stack）之模拟实现

3. 栈（Stack）之使用

4.栈（Stack）之使用场景

4.1 改变元素的序列

4.2 将递归转化为循环

4.3 括号匹配

4.4 逆波兰表达式求值

4.5 出栈入栈次序匹配

--------------------

## 1. 栈（Stack）之概念 ##

**首先明确：**

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

![89eb55bf018b4401ad9524f887a2ea31.png][]

> **（1）栈顶：进行数据插入和删除操作的一端** 
> 
> **（2）栈顶：栈顶的另一端**
> 
> **（3）入栈：栈的插入操作，也叫做压栈/进栈，****入数据在栈顶**
> 
> **（4）出站：栈的删除操作，****出数据也在栈顶**

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

![bec27a5ba4724c7ab2ed630ba182024e.png][]

分析一下，

**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的线程是安全的**

![d53dd5de1429498bb5c312b22ca5dc5f.png][]

**先写一个栈**

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<Integer> 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）先看牛客上的一道题**

![43cc35cb78de49418b42bd6cfb7b3c8d.png][]

分析一下 ，答案选C![6c4e451be2964db399d0736210ee0f8b.png][]

> **（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**

![b0e3f94a7f024a65a7bc50ee6cfb5e26.png][]

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

**分析一下，答案选B**

![5de33be05c294395958fafc436cf8ad2.png][]

--------------------

### 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<Node> 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）][20. _ - _LeetCode]

**题目要求**

![454a30e1f20045d4a3fef23931ba49cb.png][]

**分析一下**

![5ad6eaf3dc614400b46e40951e289e6e.png][]

**上代码**

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 {
                    //此时ch 是右括号
                    //说明走到右边括号了
                    if(stack.empty()) {
                        //遇到有括号了，但是栈空了，说明1.右括号多
                        return false;
                    }
                    char top = stack.peek();
                    if(ch == ')' && top == '(' || ch == ']' && top == '[' || ch == '}' && top == '{') {
                        //说明当前字符是匹配的
                        stack.pop();
                    }else {
                        //2.左右括号不匹配
                        return false;
                    }
                }
            }
            if(stack.empty()) {
                return true;
            }else {
                //3.说明是左括号多
                return false;
            }
        }
    }

--------------------

### 4.4 逆波兰表达式求值 ###

链接[ 150. 逆波兰表达式求值 - 力扣（LeetCode）][150. _ - _LeetCode]

在说这道题前先明白 **逆波兰表达式又叫做后缀表达式**

**（1）后缀表达式又可以通过中缀表达式来转化出来（考研-选择题）**

![066fb4755471490b946b9603cbfb67ae.png][]

**所以中缀变后缀三步走**

> **（1）按规则加括号 （2）将运算符放括号外面 （3）去掉所有括号**

**（2）后缀表达式计算结果（代码题）**

![49f1fe4d14e24619ba233f14a75ff7f5.png][]

**后缀计算4步走**

> **（1）将数字按顺序依次放入栈中**
> 
> **（2）遇到运算符后，拿出栈顶两个元素**
> 
> **（3）按这样的规则计算（ 次栈顶元素 运算符 栈顶元素 ）**
> 
> **（4）将计算的结果，继续放入栈中，继续执行前面操作**

好了，下面看一下这道题

![47219a0d83f14cff82d5434ae6aa48f5.png][]

**根据前面的后缀计算4步走验证一下这个例子**

![988ca94b37014a2187b019b64dc35754.png][]

class Solution {
        public int evalRPN(String[] tokens) {
            Stack<Integer> 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)][_nowcoder.com]

**题目要求：**

![c0a58d8be1e54551b2e6ca338d606796.png][]

**分析一下**

![0c2d1ce262364acabc207c394dd6e030.png][]

**上代码**

import java.util.*;
    import java.util.ArrayList;
    
    public class Solution {
        public boolean IsPopOrder(int [] pushA,int [] popA) {
            Stack<Integer> stack = new Stack<>();
            int j = 0;
          for(int i = 0; i < pushA.length; i++) {
              stack.push(pushA[i]);
              while(j <popA.length && !stack.empty() && stack.peek().equals(popA[j])) {
                  stack.pop();
                  j++;
              }
          }
        return stack.empty();
        }
    }

--------------------

[89eb55bf018b4401ad9524f887a2ea31.png]: https://img-blog.csdnimg.cn/89eb55bf018b4401ad9524f887a2ea31.png
[bec27a5ba4724c7ab2ed630ba182024e.png]: https://img-blog.csdnimg.cn/bec27a5ba4724c7ab2ed630ba182024e.png
[d53dd5de1429498bb5c312b22ca5dc5f.png]: https://img-blog.csdnimg.cn/d53dd5de1429498bb5c312b22ca5dc5f.png
[43cc35cb78de49418b42bd6cfb7b3c8d.png]: https://img-blog.csdnimg.cn/43cc35cb78de49418b42bd6cfb7b3c8d.png
[6c4e451be2964db399d0736210ee0f8b.png]: https://img-blog.csdnimg.cn/6c4e451be2964db399d0736210ee0f8b.png
[b0e3f94a7f024a65a7bc50ee6cfb5e26.png]: https://img-blog.csdnimg.cn/b0e3f94a7f024a65a7bc50ee6cfb5e26.png
[5de33be05c294395958fafc436cf8ad2.png]: https://img-blog.csdnimg.cn/5de33be05c294395958fafc436cf8ad2.png
[20. _ - _LeetCode]: https://leetcode.cn/problems/valid-parentheses/
[454a30e1f20045d4a3fef23931ba49cb.png]: https://img-blog.csdnimg.cn/454a30e1f20045d4a3fef23931ba49cb.png
[5ad6eaf3dc614400b46e40951e289e6e.png]: https://img-blog.csdnimg.cn/5ad6eaf3dc614400b46e40951e289e6e.png
[150. _ - _LeetCode]: https://leetcode.cn/problems/evaluate-reverse-polish-notation/
[066fb4755471490b946b9603cbfb67ae.png]: https://img-blog.csdnimg.cn/066fb4755471490b946b9603cbfb67ae.png
[49f1fe4d14e24619ba233f14a75ff7f5.png]: https://img-blog.csdnimg.cn/49f1fe4d14e24619ba233f14a75ff7f5.png
[47219a0d83f14cff82d5434ae6aa48f5.png]: https://img-blog.csdnimg.cn/47219a0d83f14cff82d5434ae6aa48f5.png
[988ca94b37014a2187b019b64dc35754.png]: https://img-blog.csdnimg.cn/988ca94b37014a2187b019b64dc35754.png
[_nowcoder.com]: https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[c0a58d8be1e54551b2e6ca338d606796.png]: https://img-blog.csdnimg.cn/c0a58d8be1e54551b2e6ca338d606796.png
[0c2d1ce262364acabc207c394dd6e030.png]: https://img-blog.csdnimg.cn/0c2d1ce262364acabc207c394dd6e030.png