侧边栏壁纸
博主头像
CoderKui

坐中静,舍中得,事上练

  • 累计撰写 51 篇文章
  • 累计创建 69 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

数据结构-栈

CoderKui
2021-10-28 / 0 评论 / 0 点赞 / 252 阅读 / 827 字 / 正在检测是否收录...

栈就像枪的弹匣一样,放入子弹的时候只能从上面一个一个压入,取子弹时也只能从上面一颗颗取。

最先放进出去的子弹只能最后取出,同样的,『先进后出』就是数据结构中的栈了。

栈的应用场景有很多,最常见就是函数调用栈了,程序在执行时,操作系统给每个线程分配了一块独立空间,而这块内存就是用“栈”来组织的。

程序每调用一个函数,意味着一次入栈操作,而入栈的内容为该函数,称为栈帧。函数执行结束返回结果值,代表一次出栈操作。

实现一个栈

栈对外只暴露两个操作接口,分别为栈顶的「插入」和「删除」操作。

而栈既可以用数组实现,也可以用链表实现,前者称为顺序栈,后者称为链式栈。

数组和链表作为两大基础数据结构,成为了复杂数据结构的载体。栈、队列、树、图等结构都可以用数组或链表来表示。

使用Java实现的顺序栈如下:

// 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           // 栈的大小

  // 初始化数组,申请一个大小为n的数组空间
  public ArrayStack(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;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空,则直接返回null
    if (count == 0) return null;
    // 返回下标为count-1的数组元素
    String tmp = items[--count];
    return tmp;
  }
}

由于栈只能对栈顶进行操作,入栈和出栈的时间复杂度都为O(1)。

这个顺序栈在初始化时指定了大小,所以当栈满时,就不能继续添加数据了。解决方法有两个,一是改为链式栈,二是增加扩容机制。

链式栈虽然支持动态扩容,但每项数据都额外存储了next指针,加大了内存开销。

增加扩容机制其实就是数组的扩容机制,当空间不够时,申请一个新的空间更大的数组,将原数组迁移到新数组。

END

写到一半写不下去了:),因为栈的内容本身就很精炼,只要知道「先进后出」这个原则就好了。

对于栈,不要停留在它的定义上,我们更多关注它在算法和软件工程中的应用场景。栈的结构是单调的,但运用的思想却是巧妙的。

比如算法中的括号匹配、表达式运算、拼写检查等,还有递归的调用栈、JVM的虚拟机栈、浏览器的前进后退功能等等。

0

评论区