数据结构-栈和队列

栈

我们把类似于弹夹那种先进后出的数据结构称为栈，栈是限定仅在表尾进行插入和删除操作的线性表，我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈，栈又称后进后出的线性表，简称LIFO结构。

栈首先是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系，只不过它是一种特殊的线性表而已。

栈的特殊之处在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。

栈的插入操作，叫做进栈；栈的删除操作叫做出栈。

1.栈的存储结构

用来存放栈的数据元素对应的数据存储结构称为栈的存储结构。

1.1栈的顺序存储结构

栈是线性表的特例，所以栈的顺序存储结构其实就是线性表顺序存储结构的简称，我们简称为顺序栈。线性表是用数组来实现的，对于栈这种只能一头插入删除的线性表来说，用数组下标为0（栈底不变，只需要跟踪栈顶的变化即可）的一端作为栈底比较合适。

顺序栈定义如下：

1.2栈的链式存储结构

把栈顶放在单链表的头部，用链表来存储栈的的数据结构称为链栈。

链栈结点定义如下：

2.栈的操作

2.1顺序栈的操作

对于顺序栈，一共有4个要素，包括两个特殊状态和两个操作。

特殊状态： 1）栈空状态：st.top == -1,也有的用st.top = 0表示栈空，这个时候栈顶位置为0。 2）栈满状态：st.top == maxsize-1表示栈满。maxsize为栈中最大元素个数，maxsize-1为栈满时栈顶元素在数组中的位置，因数组位置是从0开始的。

操作： 顺序栈的进栈和出栈操作都是在栈顶进行的，所以只需要更改栈顶位置即可达到进栈和出栈的目的。

1)初始化栈：

2)进栈操作：

3)出栈操作： 出栈与进栈是相对应的操作

4)简化版的操作：

2.2链栈的操作

与顺序栈对应，链栈也有4个元素，包括两个状态和两个操作。

状态： 1）栈空：lst -> next == NULL,即栈没有后继结点时，栈为空。 2）栈满：如果存储空间无限大的话，不会存在栈满的情况。

操作： 链栈的进栈就是头插法建立链表的插入操作；出栈就是单链表的删除操作。

1)链栈初始化：

2)进栈：

3)出栈：

4)简化版操作：

队列：

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表，队列是一种先进先出的线性表，简称FIFO，允许插入的一端称为队尾（Rear），允许删除的一端称为队头(Front)。向队中插入元素称为进队，新元素进队后成为新的队尾元素；向队中删除元素称为出队，元素出队后，其后继元素就成为新的队头元素。

1.队列的存储结构

用来存储队列数据元素的数据结构。

1.1队列的顺序存储结构：

使用顺序表存储队列时，队列元素的出队是在队头，即下标为0的地方，当有元素出队时，出队元素后面的所有元素都需要向前移动，保证队列的队头始终处在下标为0的位置，此时会大大增加时间复杂度。

用顺序表来存储队列元素的数据结构称为队列的顺序存储结构，定义如下：

1.2队列的链式存储结构：

用链表来存储队列元素的数据结构称为队列的链式存储结构，定义如下：

队列结点类型定义：

链队类型定义：

2.队列操作

2.1循环队列

因为顺序队列出队时时间复杂度较高，有问题总是要解决的，为什么一定要让队头出现在下标为0的位置呢？所以有人提出了不去限制队列元素必须存储在数组的前n个单元这一条件，这样队头元素就不需要一定在下标为0的位置。但是随着队列元素的出队，队头指针在向后移动，假设队尾指针已经在maxsize-1的位置，这个时候虽然队列还有存储空间，但是队尾已经无法进队了，比如下图这样：

虽然下标为0和1的位置处还有空间，但是队尾已经无法再有新元素进队，我们把这种情况称为"假溢出"，为了解决这种假溢出的问题，就提出了循环队列的概念，让队列的头尾进行相连，这种头尾相连的顺序存储结构称为循环队列。

循环队列需要损失一定的空白，这样只有在队空的时候才会出现front=rear。

循环队列的要素：

两个状态： 队空状态：

队满状态：

两个操作： 元素x进队操作（移动队尾指针）

元素x出队操作（移动队头指针）

初始化队列算法：

进队算法：

出队算法：

2.2链队：

链队就是采用链式存储结构存储队列。链队的四个要素：队空和队满，元素进队和出队操作。

队空状态：

队满状态： 一般来说不存在队满的情况，只要内存足够大。

元素进队操作(指针p指向进队元素)

元素出队操作（x存储出队元素）

初始化链队算法

判断队空算法

入队算法

出队算法

End.

作者：张俊红