栈的特点和使用场景

2020-09-17  本文已影响0人  文景大大

前言

本篇文章主要解决如下问题：

  1. 栈的特点是什么？
  2. 使用栈的问题场景一般都可以使用数组或者链表解决，那么我们为什么还要使用栈？
  3. 如何实现一个栈？
  4. 栈有哪些应用场景？

一、栈的定义

后进先出，先进后出，是一种操作受限的线性表，只允许在一端插入和删除数据。大多数使用栈的场景都可以使用数组或者链表进行代替，但是数据和链表暴露了太多操作的接口，看上去很灵活，但是对应的风险增大了，更加地不可控。

二、实现一个栈

2.1 顺序栈

用数组实现的栈，我们称为顺序栈，大致代码如下：

public class MyStack {

    private String[] items;
    private int counter;
    private int size;

    // 初始化栈
    public MyStack(int size) {
        this.items = new String[size];
        this.size = size;
        this.counter = 0;
    }

    public boolean push(String item) {
        // 栈已满
        if (counter >= size) {
            return false;
        }

        items[counter] = item;
        counter++;
        return true;
    }

    public String pop() {
        // 栈为空
        if (counter <= 0) {
            return null;
        }

        String result = items[counter - 1];
        counter--;
        return result;
    }

}

@Slf4j
public class StackTest {

    public static void main(String[] args) {
        MyStack myStack = new MyStack(6);
        myStack.push("12");
        myStack.push("13");
        myStack.push("14");
        String result = myStack.pop();
        log.info("{}", result);
    }

}

入栈和出栈的时间复杂度都是O(1)，除了本身就需要的n个存储空间外，额外的空间复杂度也为O(1)。

2.2 链式栈

用链表实现的栈称为链式栈，相较于顺序栈，链式栈不需要占用连续的内存空间，也更加方便动态扩展，比较适合入栈和出栈操作，但是顺序栈更加方便查找。

三、栈的使用场景

3.1 函数调用

操作系统会给每个线程分配一块独立的内存区域，这块内存区域就是一种栈的结构，用来存储函数调用时的一些临时变量。每进入一个函数，就会将临时变量保存在一个栈帧中入栈，当函数执行完返回后，就会将最近一个栈帧出栈。

3.2 表达式求值

用两个栈来实现四则运算，一个栈用来保存操作数，另一个栈用来保存运算符。当我们从左往右遍历表达式的时候：

我们来举个例子：表达式2+3*6-7，那么两个栈的运算过程如下：

3.3 括号匹配

假设一个表达式为三种括号任意嵌套的，要求使用栈来检查这个表达式是否合法，那么怎么做呢？

我们使用一个栈即可，当遍历表达式的时候：

3.4 浏览器的前进和后退功能

我们使用两个栈，比如A和B：

上一篇 下一篇

猜你喜欢

热点阅读