栈和队列

什么是栈

栈存储结构与之前学习的线性存储结构有所差异，这缘于栈对数据“存”和“取”的过程有特殊的要求：

  1. 栈只能从表的一端存取数据，另一端是封闭的

  2. 在栈中，无论是存数据还是取数据，都必须遵循“先进后出”的原则，即最先进栈的元素最后出栈。

因此，栈是一种只能从表的一端存取数据且遵循“先进后出”原则的线性存储结构。

进栈和出栈

在实际应用中，通常只会对栈执行以下两种操作：

l 向栈中添加元素，此过程被称为“进栈”（入栈或压栈）

l 从栈中取出元素，此过程被称为“出栈”（或弹栈）

栈的具体实现

栈是一种“特殊”的线性存储结构，具体实现有以下两种方式：

  1. 顺序栈

  2. 链栈

两种实现方式的区别，仅限于数据元素在实际物理空间上存放的相对位置，顺序栈底层采用的是数组；链栈底层采用的是链表。

栈的应用

l 浏览器的“回退”功能

l 检测代码中的括号匹配问题

l 数值的进制转换功能

l …

顺序栈实现及其基本操作

见代码。

链栈实现及其基本操作

见代码。

什么是队列

与栈结构不同的是，队列的两端都是“开口”，要求数据只能从一端进，从另一端出。

通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。

队列中数据的进出要遵循“先进先出”的原则。

注意：栈和队列不要混淆，栈结构是一端开口，特点是”先进后出”；而队列的两端全是开口，特点是”先进先出”。

队列的实现

队列存储结构的实现有以下两种方式：

  1. 顺序队列 ：在 顺序表 的基础上实现的队列结构；

  2. 链队列：在 链表 的基础上实现的队列结构；

队列的实际应用

l 排队做核算

l 排队挂号（医院的挂号系统）

l …

顺序队列实现及其基本操作

见代码。

链式队列实现及其基本操作

见代码。