【数据结构】栈的使用|模拟实现|应用|栈与虚拟机栈和栈帧的区别

目录

一、栈(Stack)

1.1 概念

1.2 栈的使用

1.3 栈的模拟实现

1.4 栈的应用场景

1. 改变元素的序列

2. 将递归转化为循环

3. 括号匹配

4. 逆波兰表达式求值

5. 出栈入栈次序匹配

6. 最小栈

1.5 概念区分

---

推荐

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站

---

一、栈(Stack)

1.1 概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则（也就是先进后出）

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

出栈：栈的删除操作叫做出栈。出数据在栈顶

---

1.2 栈的使用

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回（有返回值）
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

public static void main(String[] args) {
        Stack s = new Stack();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.size()); // 获取栈中有效元素个数---> 4
        System.out.println(s.peek()); // 获取栈顶元素---> 4
        s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
        System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
        if (s.empty()) {
            System.out.println("栈空");
        } else {
            System.out.println(s.size());
        }
    }

---

1.3 栈的模拟实现

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的

栈的模拟实现有两种：一种是数组实现，另一种是链表（单链表或者双链表）实现，不管是哪种，都得保证入栈 出栈操作的时间复杂度为O（1）

下面这个是数组模拟实现栈的方式：

import java.util.Arrays;
//数组实现栈
public class MyStack {
    public int[] elem;//定义数组
    public int uesdSize;//记录当前数组的有效元素的个数，同时可以当作下标使用
    public static final int DEFAULT_CAPACITY = 10;//默认容量大小
    public MyStack() {
        this.elem = new int[DEFAULT_CAPACITY];
    }
    //判断栈是否满了
    public boolean isFull() {
        return uesdSize == elem.length;//这里不能写成DEFAULT_CAPACITY，DEFAULT_CAPACITY被final修饰不能变
    }
    //压栈 入栈
    public void push(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(elem,2*elem.length);//扩容为原数组
        } else {
            elem[uesdSize++] = val;
        }
    }
    //判空
    public boolean isEmpty() {
        return uesdSize == 0;
    }
    //出栈
    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException("栈为空...");
        }
        int oldVal = elem[uesdSize-1];
        uesdSize--;
        elem[uesdSize] = 0;
        return oldVal;
    }
    //获取栈顶元素
    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException("栈为空...");
        }
        return elem[uesdSize-1];
    }
}

如果采用单向链表实现栈，那么为了保证入栈出栈的时间复杂度为O（1）

入栈只能采用头插法，尾插法需要遍历链表直到尾结点，这样就不满足时间复杂度为O（1）

出栈也只能采用头删法，可能大家会想用last来标记尾结点，从而不用遍历，但是这样在删除了一次以后，尾节点还得去遍历找前一个结点，还是不满足时间复杂度为O（1）

如果采用双向链表实现栈，那么头插尾插都是可以的

---

1.4 栈的应用场景

1. 改变元素的序列

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

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

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

A: 12345ABCDE  B: EDCBA54321  C: ABCDE12345  D: 54321EDCBA

答：

1.由于栈的特性是先进后出，C选项中：当1，2，3都已经入栈后，3出栈，然后栈顶为2，不可能直接就让1进行出栈，所以错误

2.仍然考察的是栈的特性是先进后出，先进栈的元素最后出栈，那么也就是B

2. 将递归转化为循环

比如：逆序打印链表

// 递归方式
    void printList(Node head){
        if(null != head){
            printList(head.next);
        System.out.print(head.val + " ");
        }
    }

这里循环的方式就类似上面的第二题，入栈元素出栈也就相当于逆序 

// 循环方式
    void printList(Node head){
        if(null == head){
            return;
        }
    Stack s = new Stack();
        // 将链表中的结点保存在栈中
        Node cur = head;
        while(null != cur){
            s.push(cur);
            cur = cur.next;
        }
        // 将栈中的元素出栈
        while(!s.empty()){
            System.out.print(s.pop().val + " ");
        }
    }

3. 括号匹配

首先思考一下为什么这个题需要用到栈这个数据结构，什么时候会用到这个数据结构？

一般和顺序有关的就需要考虑栈

这题的思路：

首先要明白这个题目不是偶数就一定是匹配的，eg：[（ ] ）

 只要是左括号就入栈，遇到右括号就看是否匹配

以下三种情况是不匹配的：

（1）右括号不匹配 就直接返回false 

（2）字符串还没遍历完成 但是栈是空的 此时也是不匹配  eg：（））

（3）字符串遍历完了 但是栈不为空 此时也是不匹配  eg：（）（

class Solution {
    public boolean isValid(String s) {
        Stack stack = new Stack();
        //遍历字符串
        for(int i=0;i