数据结构基础：栈和队列学习笔记

1、栈

1.1 栈的定义

栈是只能通过访问它的一端来实现数据的存储和检索的一种特殊的线性数据结构。栈的修改要遵循先进后出的原则，这个是栈的核心。在栈中进行插入和删除操作的一端称为栈顶（Top）。另一端被称为栈底（bottom）。不包含任何元素的栈称为空栈。

1.1.1 栈的运算

1.2 栈的存储结构

1.2.1 栈的顺序存储

栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设置指针top指示栈顶元素的位置。顺序存储的栈也被称为顺序栈。这种存储方式，需要预先定义或申请栈的存储空间，所以顺序栈的空间容量是有限的。在入栈的时候要判断是否栈满的情况。否则会出现上溢的异常。

1.2.2 栈的链式存储

为了解决顺序栈可能存在上溢的不足，可以用链表存储栈中的元素。链式存储的栈也被称为链栈。元素的插入、删除操作仅能在栈顶一端进行。因此可以不必设置头节点。

1.2.3 栈的用途

栈的典型应用包括表达式求值、括号匹配等。在编程领域实现将递归过程转变为非递归过程的处理中，栈可以起到重要作用。还可以实现数据的逆向输出。 

2、队列

2.1 队列的定义

队列是一种先进先出的线性表，它只允许在表的一端插入元素，在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾（Rear），允许删除元素的一端称为队头（Front）

2.2 队列的基本运算

2.2 队列的存储结构

2.2.1 队列的顺序存储

利用一组地址连续的存储单元存放队列中的元素。由于队列中的元素插入和删除限定在两端进行，因此设置队头指针和队尾指针需要分别指示当前的队头元素和队尾元素。顺序队列的存储空间是提前设定好的，因此队尾指针会有一个上限值，达到上限就不能够再入队操作了。需要等队头有元素被移除。这个和日常买东西排队是很相似的，比如买东西限定排队人数为20人，如果当前已经排满了，此时工作人员会阻止你的排队行为，直到第一个买东西离开后，你就就可以继续排队了。判断顺序队列位空队列的方法是队头和队尾的值相同。

注意：针对空队列要能区分队头队尾元素，可以通过标识位来区分队头和队尾元素的不同。

2.2.2 队列的链式存储

队列的链式存储称为链队列。链队列判断是否位空队列的条件是值相同并且均指向头节点。

2.3 队列的用途

队列常用于需要排队的场合，比如打印机打印文件、离散事件的计算机模拟、消息队列、定时任务等方面。