数据结构与算法是计算机科学的基础，本章主要讨论两种重要的数据结构：栈和队列，它们都是线性表的特殊形式。
2.4.1 栈的定义与特性
栈是一种特殊的线性表，它的主要特点是仅允许在表的一端进行插入和删除操作，这一端被称为栈顶，而另一端则称为栈底。当表为空时，我们称之为空栈。假设栈S包含元素a1到an，a1是栈底元素，an则是栈顶元素。栈遵循“后进先出”（LIFO）原则，即最后进入栈的元素最先退出，这与日常生活中的堆叠物品如书或盘子的行为类似。栈的这种性质使得它在处理逆序操作或者回溯问题时非常有用。
栈的存储结构
栈可以采用顺序存储结构（顺序栈）或链式存储结构（链栈）实现。在顺序栈中，通常使用数组来存储元素，栈顶的索引top用于跟踪当前栈顶位置。例如，当元素入栈时，先将元素存入数组，然后top加1；出栈时，先将top减1，再取出元素。如果栈的大小固定，需要注意防止溢出，即栈满的情况。为了克服这个问题，可以使用循环队列的概念。
栈的改进 - 两个栈共享存储空间
为了节省空间，可以将两个栈放在同一个数组的两端，栈顶向数组的中间扩展。这种方式称为双端栈，可以有效利用存储空间。
链栈则是使用链表结构来实现栈，每个节点包含一个数据域和一个指向下一个节点的指针。链栈的操作与顺序栈类似，但插入和删除操作在链表头部进行。
2.4.2 队列的定义与特性
队列是另一种线性表，它的特点是只允许在表的一端（队尾）插入元素，在另一端（队头）删除元素。队列遵循“先进先出”（FIFO）原则，即最先加入队列的元素最先离开。队列常被比喻为等待服务的人群，先来的先接受服务。
队列的存储结构
队列可以使用顺序存储结构（顺序队列）或链式存储结构（链队列）实现。在顺序队列中，数组用于存储元素，队头和队尾通过front和rear索引来跟踪。在循环队列中，为了避免“假满”现象，可以使用数组的模运算来实现，这样可以充分利用存储空间。队列的操作包括入队（在队尾添加元素）和出队（从队头移除元素）。
总结：
栈和队列作为基础数据结构，广泛应用于计算机算法设计中，如递归、表达式求值、深度优先搜索、广度优先搜索、内存管理等。理解并掌握它们的定义、性质、存储结构以及操作方法对于提升编程能力至关重要。通过合理的数据结构选择和实现，可以有效地提高程序的效率和性能。
