Java 数据结构 - 栈

数据结构与算法之美目录：https://www.cnblogs.com/binarylei/p/10115867.html

我们今天要讲的数据结构是栈，比如浏览器的前进后退功能就可以用栈来实现。

1. 什么是栈

栈是一种先进后出的线性存储结构，先进先出就是队列结构。

栈（stack）是限制插入和删除只能在一个位置上进行的线性表，该位置是表的末端，叫作栈的顶（top）。对栈的基本操作有 push（进栈）和 pop（出栈），前者相当于插入，后者则是删除最后插入的元素。

1.1 栈的主要特性

• 栈中的数据元素遵守”先进后出”（First In Last Out）的原则，简称 FILO 结构。
• 限定只能在栈顶进行插入和删除操作。

从功能上来说，数组或链表确实可以替代栈。但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。

1.2 栈的相关概念

• 栈顶（top）与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。
• 压栈（push）栈的插入操作，叫做进栈，也称压栈、入栈。
• 弹栈（pop）：栈的删除操作，也叫做出栈。

2. 复杂度分析

栈的两种实现方案，我们简单分析一下栈的复杂度：

• 动态栈（链表）：也叫链式栈。
• 静态栈（数组）：也叫顺序栈。

2.1 链式栈

由于都是操作指定位置的结点，所以其进栈和出栈的时间复杂度都是 O(1)。

2.2 顺序栈

一般来说，如果用数组实现的栈，其大小是固定的，不支持动态扩容。对于这种固定大小的栈结构，进栈和出栈的时间复杂度也都是 O(1)。

当然，也有少数场景，也需要用利用数据实现动态扩容的栈结构。对于可动态扩容的顺序栈，出栈的时间复杂度同样是 O(1)。入栈的最好时间复杂度也是 O(1)，只有执行 n 次入栈后需要扩容时，最坏时间复杂度才是 O(n)，如果使用摊还分析法，其均摊时间复杂度仍是 O(1)。由此也可以看出，均摊时间复杂度一般都等于最好情况时间复杂度。

3. 栈在软件工程中应用

栈在计算机中应用相当广泛，包括递归的调用和返回、二叉树和森林的遍历、调用子程序及从子程序返回、表达式的转换和求值、CPU 的中断处理等等。

3.1 表达式求值

编译器就通过两个栈来实现表达式求值。

• 操作数栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；
• 运算符栈。当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

3.2 括号匹配

编译器语法校验，如 [] () {} 必须成对匹配，并且它们可以任意嵌套。同样也可以借助栈来检查表达式中的括号是否匹配。

3.3 函数调用

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

每天用心记录一点点。内容也许不重要，但习惯很重要！

Java 数据结构 - 栈

原文：https://www.cnblogs.com/binarylei/p/12400470.html