栈

栈也是用来存储逻辑关系为 “一对一” 数据的线性存储结构
栈对数据 “存” 和 “取” 的过程有特殊的要求：

  1. 栈只能从表的一端存取数据，另一端是封闭的
  2. 在栈中，无论是存数据还是取数据，都必须遵循”先进后出”的原则，即最先进栈的元素最后出栈。

通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。

进栈和出栈

基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：

  • 向栈中添加元素，此过程被称为”进栈”（入栈或压栈）；
  • 从栈中提取出指定元素，此过程被称为”出栈”（或弹栈）；

    栈的具体实现

    栈包括 顺序栈 和 链式栈
  1. 顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
  2. 链栈：采用链式存储结构实现栈结构；

    栈的应用

    基于栈结构对数据存取采用 “先进后出” 原则的特点，它可以用于实现很多功能。
    例如，我们经常使用浏览器在各种网站上查找信息。假设先浏览的页面 A，然后关闭了页面 A 跳转到页面 B，随后又关闭页面 B 跳转到了页面 C。而此时，我们如果想重新回到页面 A，有两个选择：
  • 重新搜索找到页面 A；
  • 使用浏览器的”回退”功能。浏览器会先回退到页面 B，而后再回退到页面 A。

浏览器 “回退” 功能的实现，底层使用的就是栈存储结构。当你关闭页面 A 时，浏览器会将页面 A 入栈；同样，当你关闭页面 B 时，浏览器也会将 B入栈。因此，当你执行回退操作时，才会首先看到的是页面 B，然后是页面 A，这是栈中数据依次出栈的效果。
不仅如此，栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号（小括号、中括号和大括号），括号的错误使用（通常是丢右括号）会导致程序编译错误，而很多开发工具中都有检测代码是否有编辑错误的功能，其中就包含检测代码中的括号匹配问题，此功能的底层实现使用的就是栈结构。
同时，栈结构还可以实现数值的进制转换功能。例如，编写程序实现从十进制数自动转换成二进制数，就可以使用栈存储结构来实现。

顺序栈

顺序栈：即用顺序表实现栈存储结构。
image.png

链栈

链栈：即用链表实现栈存储结构。
链栈的实现思路同顺序栈类似，顺序栈是将数顺序表（数组）的一端作为栈底，另一端为栈顶；链栈也如此，通常我们将链表的头部作为栈顶，尾部作为栈底
将链表头部作为栈顶的一端，可以避免在实现数据 "入栈" 和 "出栈" 操作时做大量遍历链表的耗时操作.
链表的头部作为栈顶，意味着：

  • 在实现数据”入栈”操作时，需要将数据从链表的头部插入；
  • 在实现数据”出栈”操作时，需要删除链表头部的首元节点；

因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表。
image.png