第二章-线性表11(数据结构word版课件).doc

第二章 线性表、堆栈和队列
§2.1 线性表的定义和基本操作
定义2.1 一个线性表是由零个或多个具有相同类型的结点组成的有序集合。我们用（a0，a1，…，an-1）来表示一个线性表，n为一个自然数。当n = 0时，线性表中无结点（或曰包含零个结点），这样的线性表被称为空表；当n > 1时，称a0为线性表的表头（head），称an-1为线性表的表尾（tail），称ai为ai+1的前驱结点，称ai+1为ai的后继结点，其中0 £ i £ n-1；当n =1时，线性表中仅有一个结点，该结点既是表头，又是表尾。
§2.2 线性表的顺序存储结构
按照线性表结点间的逻辑顺序依次将它们存储于一组地址连续的内存单元中的这样一种存储方式被称为线性表的顺序存储方式。
按顺序存储方式存储的线性表具有顺序存储结构，一般称之为顺序表。换言之，在程序中采用定长的一维数组，按照顺序存储方式存储的线性表，被称为顺序表。若顺序表中元素按其值整序，则称其为有序顺序表。
若存储线性表的一个结点需要在内存中占据c个连续字节，则有
Loc (ai) = Loc (ai-1) +c
进而有
Loc (ai) = Loc (a0) + i´c
【插入算法】：要求在顺序表A中下标为k的结点后插入字段值为item的结点。该插入操作较容易实现，只需从后向前将A中下标大于等于k+1的元素均后移一个位置，但前提是必须保证表未满（length¹MaxSize），且插入位置合法。
插入算法描述如下：
算法 Insert (A, k, item)
// 在顺序表A中下标为 k 的结点后插入值为 item 的结点，length系指顺序表的当前长度
I1. [插入合法?] // 三种情况不能插入
IF ( k < 0 OR k > length-1 OR length = MaxSize) THEN (PRINT“插入不合法”. RETURN.)
I2.[插入]
//从后向前将下标大于等于k+1的元素均后移一个位置
FOR i =length-1 TO k+1 STEP -1 DO A[i+1]¬A[i].
A[k+1] ¬ item.
length ¬ length+1. // A的当前长度增1 ▐
【删除算法】：要求在顺序表A中删除下标为k的结点。
在保证顺序表非空且删除位置合法的前提下，实现该删除操作只需从前向后将顺序表中下标大于k的结点均前移一个位置。
算法 Delete(A, k) /*删除顺序表A中下标为 k 的结点 */
D1.[删除合法?]
IF (k < 0 OR k > length -1 OR length = 0) THEN ( PRINT “删除不合法”. RETURN.)
D2.[删除]
FOR i =k+1 TO length DO A[i-1]¬A[i]. // 从前向后将下标大于k的结点均前移一个位置
length ¬ length -1. // A的当前长度减1 ▐
§2.3 线性表的链接存储结构
用链接存储方式存储的线性表被称为链表。链表中的结点用存储单元（若干个连续字节）来存放，存储单元之间既可以是（存储空间上）连续的，也可以是不连续的，甚至可以零散地分布在存储空间中的任何位置。换言之，链表中结点的逻辑次序和物理次序之间并无必然联系。
为了能正确表示结点之间的逻辑关系，一个存储单元（假定每个结点需要一个存储单元）除了存放结点的数据字段的值，还必须存放其逻辑相邻结点（前驱结点或者后继结点）的地址信息，这个地址信息被称为指针。
2.3.1 单链表
一个单链表结点由两个域构成：
指针域
数据域
data next

其中数据域data存放该结点的数据域的值，指针域next存放该结点的后继结点的地址信息。
我们考虑一个由n个元素d1、d2、…、dn组成的线性表，若采用链接存储方式，则其存储结构如图2.3所示：
结点
结点
…
结点

d1

dn

d2

head
tail
NULL

图2.3 单链表

链表的第一个结点被称为头结点(也称为表头)，指向头结点的指针被称为头指针（head）. 链表的最后一个结点被称为尾结点（也称为表尾），指向尾结点的指针被称为尾指针（tail），验证一个结点是否是表尾，只须考察该结点的next域值是否为NULL .
单链表上的操作:
插入:InsertAfter函数 在当前结点this之后插入结点P .
算法InsertAfter（this ，P）
IA1 [将当前结点this的next域值赋给P的next域]
next（P）¬ next（this）.
IA2 [将P赋给当前结点的next域]
next（this）¬ P ▌
删除：DeleteAfter函数 删除当前结点this的后继结点，并返回指向被删除结点的指针tempptr。
算法DeleteAfter（this . tempptr）
// 删除当前结点的后继结点，并令指针tempptr指向被删除结点；
DA1 [this的next域值 = NULL？]
IF next（this）= NULL THEN tempptr ¬ NULL.
ELSE（tempptr ¬ next（this）. next（this）¬ next（tempptr） ）. ▌

构造链表
(1) 生成节点：结点生成函数GetNode：创建一个data域值为item、next域值为nextptr的结点，并用指针newNode指向该新节点。
算法GetNode（item ，nextptr . newNode）
// 结点生成算法
GN1 [为新结点申请空间]
newNode Ü AVAIL . // NewNode表示指向新创建结点的指针
GN2 [为结点诸域赋值]
data（newNode）¬ item.
next（newNode）¬ nextptr. ▌

(2) 表头插入结点：在头指针为head的链表中，插入一个data域值为item的新结点作为该链表的表头结点，并修改相关指针。
算法InsertFront（head ， item）
IF1 [调用函数GetNode]
GetNode（item，head. newNode）.
IF2 [head指向新结点]
head ¬ newNode. ▌
不难看出，通过不断生成结点，并将它们依次插入表头，就可形成一个链表。

（3）遍历链表
所谓遍历一个结构，是指按一定的次序访问结构中的所有结点，且每个结点恰被访问一次。遍历链表，就是按一定次序访问链表的所有结点。
我们知道，一条链必然有链头，抓住链头就意味着抓住了整条链。对于链表而言，头指针就相当于链表的链头，要想遍历整个链表，必须从头指针开始。
算法PrintList（head）
// 输出头指针为head的链表
PL 1 [取表头，计数器初始化]
currptr ¬ head .
PL 2 [遍历并输出链表结点的data值]
WHILE（currptr ≠ NULL） DO
（ PRINT（ data（currptr） ）.
currptr ¬ next（currptr）.
）▌

（4）表尾插入结点
我们知道，通过向表头插入结点可以构造链表。另一种构造链表的方法是将结点链接到表的尾部，这种方法被称为表尾插入。
要想进行表尾插入，必须先测试一下链表是否为空表。对于一个空链表，向表尾插入一个结点和向表头插入一个结点，得到的是相同的链表，故利用InsertFront就可实现对空链表的表尾插入。对于非空链表，要实施表尾插入操作必须先确定表尾结点，这一步要通过扫描整个链表来实现。
currptr

head
…

item

新结点

算法InsertRear（ head ，item ）
// 在头指针为head的链表尾部插入data域值为item的结点；
IR1 [取头指针]
currptr ¬ head .
IR2 [currptr = NULL？]
IF currptr = NULL THEN InsertFront（head ，item）
ELSE（
WHILE（next（currptr）≠ NULL） DO
currptr ¬ next（currptr）.
GetNode（item，NULL . newNode）.
InsertAfter（currptr ，newNode） ）▌
我们知道，无论以何种存储方式实现线性表，都要支持线性表的基本操作。但是，对图2.3所示的单链表，如果要执行删除操作，且被删除的结点是头结点，则必须修改头指针，令其指向新的头结点（原头结点的后继结点），插入操作也会遇到类似问题。解决办法就是在表的前端增加一个特殊的表头结点，称其为哨位结点，如图2.4 .
NULL
结点
dn

哨位结点

结点
d1

…
tail
head

图2.4 增加哨位结点的单链表

哨位结点的结构与其它表结点相同，也是由数据域和指针域构成的，但数据域没有被赋值，指针域则存储指向第一个真正表结点的指针。要说明的是，哨位结点不被看作表中的实际结点，本书在讨论链表中第k个结点时均指第k个实际的表结点，在讨论表的长度时，将非哨位结点的个数称为链表的长度；若表中只有哨位结点，则称其为空链表，即表长度为0 .
从图2.4可以看出，与顺序表不同，单链表无法直接访问指定位置的结点，而是需要从哨位结点head开始，沿着next指针逐个结点计数，直至到达指定位置。

【存取算法】：要求将链表中第k个结点的数据域值赋给item. 该操作很容易实现，只需在保证k合法的前提下，从表头开始逐一访问链表结点，直至找到第k个结点为止。
算法 Find ( k, item) // 将链表中第k个结点的字段值赋给item
F1. [k合法？] //
IF ( k < 1) THEN (PRINT“存取位置不合法”. RETURN.)
F2. [初始化]
p¬head . i¬0. //令指针p指向哨位结点，计数器初始值为0
F3. [找第k个结点]
WHILE (p≠NULL AND i<k) DO
( p¬next(p) . i¬i+1. ) // 若找到第k个结点或已到达表尾，则循环终止
IF p = NULL THEN ( PRINT“无此结点”. RETURN. )
item¬data(p). ▐

下面讨论存取算法的时间复杂度，为方便计，设表的长度为n .
对于算法Find，最好情况下的时间复杂度为O(1)；最坏情况下的时间复杂度为O(n)；平均情况下，假设k<1, k=1, …, k=n, k>n的概率相同，即每种情况的发生概率为1/(n+2) ，则WHILE循环的执行次数平均为

因此存取算法的时间复杂度为O(n).
【查找算法】：要求在链表head中查找字段值为item的结点并返回其在表中的位置。同存取算法类似，查找算法也需要从表头开始逐一访问链表结点，并比较每个结点的字段值是否为item，直至找到该结点或已遍历至表尾仍未找到（算法终止）。
算法 int Search (item .i) // 在链表中查找字段值为item的结点并返回其在表中的位置i（从1开始编号），如果item不在表中，则返回-1。
S1. [初始化]
p¬next(head) . i¬1. // 令指针p指向哨位结点的后继结点，计数器初始值为1
S2. [逐点访问]
WHILE (p ¹ NULL AND data(p) ¹ item) DO
( p¬next(p) . i¬i+1. ) // 令指针p指向下一个结点，且计数器加1
IF p¹NULL THEN RETURN i .
PRINT “无此结点”. RETURN -1. ▐
容易看出，Search算法最好情况下的时间复杂度为O(1)，最坏情况和平均情况下的时间复杂度皆为O(n).
单链表的插入和删除算法比顺序表要简单得多，它无需改变一系列存储单元的存储值，仅仅需要修改一下相关结点的next指针。插入和删除涉及到新结点存储空间的申请和无用结点存储空间的释放，在ADL语言中，申请新存储空间的操作用语句“xÜAVAIL”来描述，释放不用的空间则用语句“AVAIL Üx”来描述，其中AVAIL是一个可利用空间表。
【删除算法】：要求删除链表中第k个结点并将其字段值赋给item . 该算法首先需要找到第k-1个结点，并存取其后继结点（第k个结点）的字段值，其实现过程与存取算法Find类似；然后修改第k-1个结点的next指针使其指向第k+1结点。需要注意的是，在此过程中应该用一个临时指针指向被删除结点，并最终释放该结点所占用的存储空间，否则该部分空间将成为存储空间中无法利用的垃圾。
单链表删除算法如图2.5所示，要删除链表中结点p与q之间的结点s，只需修改结点p的next指针，使其指向结点q.

删除前
data

data
next

data

s

q
p

删除后

data

data
next

data

s

p
q
图2.5 单链表的删除算法

删除算法的ADL描述如下：
算法Delete ( k . item ) // 删除链表中第k个结点并将其字段值赋给item
D1. [k合法？]
IF ( k < 1) THEN (PRINT“删除不合法”. RETURN.)
D2. [初始化]
p¬head . i¬0. // 令指针p指向哨位结点，计数器初始值为0
D3. [找第k-1结点]//用p指向第k-1结点，q指向第k结点
WHILE (p¹NULL AND i<k -1) DO
( p¬next(p) . i¬i+1. )
IF p = NULL THEN ( PRINT “无此结点”. RETURN. )
D4. [删除]
q¬next(p). next(p) ¬next(q). // 修改p的next指针
item¬data(q). AVAILÜq. //存取q的字段值并释放其存储空间 ▐

【插入算法】：在链表中第k个结点后插入字段值为item的结点。该算法首先要找到第k个结点，其实现过程与存取算法Find类似. 为新插入结点申请存储空间，并令其next指针指向第k+1个结点；修改第k个结点的next指针，令其指向新插入结点。
插入算法如图2.6所示，要实现在指针p和q所指结点之间插入结点s，只需修改p和s的next指针,但两个指针的修改是有顺序的.
data
next

data

data
next

data

插入后
插入前

②
p
q
p

①
data

q
data
next

s
s
图2.6 插入算法示意图

插入算法的ADL描述如下：
算法Insert ( k, item ) // 在链表中第k个结点后插入字段值为item的结点。指针p指向第k个节点，指针s指向新生成的节点，算法在p之后插入s。
I1. [k合法？]
IF ( k < 0) THEN (PRINT“插入不合法”. RETURN.)
I2. [初始化]
p¬head . i¬0.
I3. [p指向第k结点]
WHILE (p¹NULL AND i<k) DO
( p¬next(p) . i¬i+1. )
IF p=NULL THEN ( PRINT “插入不合法”. RETURN. )
I4. [插入]
sÜAVAIL. data(s) ¬item. next(s) ¬next(p).
next(p) ¬s. ▐
删除算法和插入算法时间复杂度的计算与存取算法类似，本书不再赘述。

2.3.2 循环链表
从单链表一个结点出发，只能访问到链接在它后面的结点，而无法访问位于它前面的结点。这对一些实际应用很不方便。解决的办法是把链接结构“循环化”，即把表尾结点的next域存放指向哨位结点的指针，而不是存放空指针NULL（即L），这样的单链表被称为循环链表。循环链表使我们可从链表的任何位置开始，访问链表中的任一结点。图2.6给出了一个循环链表的示例。
图2.6 循环链表
…
data
next

data
next

data
next

next

head

空循环链表系指该单链表中只包含一个头指针head指向的哨位结点，其next域存放指向自身的指针。图2.7示出了一个空循环链表。
不难看出，对于单链表和循环链表，检测链表是否为空的方法不同：
单链表：next (head) ?= NULL，//有哨位结点的单链表
循环链表： next (head) ?= head .
next
图2.7 空循环链表
head

2.2.4 双向链表
找前驱
在循环链表中，从一个结点出发，必须遍历整个链表，方可找到其前驱结点，时间复杂度为O(n) . 双向链表很好地解决了该问题。
所谓双向链表（Double-Linked List），系指链表中任一结点P都是由data域、左指针域left和右指针域right构成的，左指针域和右指针域分别存放P的左右两边相邻结点的地址信息（如图2.8），链表中表头结点的left指针和表尾结点的right指针均为NULL. 指针head和tail分别指向双向链表的头结点和尾结点，双向链表也被称为双重链表。
left
data
right

图2.8 双向链表的结点

由具有两个链接域的结点构成的双向链表的链接结构如图2.9所示：
tail
图2.9 双向链表
¼

head

【插入算法】：考虑右插入：在结点s的右边插入指针p所指结点：
图2.10 双向链表——在结点s右边插入结点p

p
s
s的右结点

4
2
1
3

由图2.10可知，要将结点p插入到结点s的右边，需要执行如下4步：1. 保存s的右结点的地址信息，令p的右指针指向s的右结点；2. 令p的左指针指向结点s；3. 令s的右结点的左指针指向p；4. 令s的右指针指向p. 其中，2和3的执行次序可交换。右插入算法用ADL语言描述更为直观：
算法DLInsert（s , p）// 在结点s的右边插入结点p
DLI1.[ right (s) = L] // 若结点s是尾结点
IF right (s) = L THEN ( ( right (p) ¬L . left (p) ¬ s. right (s)¬p. RETURN. )
DLI2. [插入]
right (p) ¬ right (s).
left (p) ¬ s.
left (right (s)) ¬ p .
right (s) ¬ p . ▐
§2.4 复杂性分析
到目前为止，我们已详细介绍了线性表的两种存储方式——顺序存储和链接存储，下面从时空复杂性两方面对二者进行分析比较。

空间效率比较
顺序表所占用的空间来自于申请的数组空间，数组大小是事先确定的，很明显当表中的元素较少时，顺序表中的很多空间处于闲置状态，造成了空间的浪费；而链表所占用的空间是根据需要动态申请的，不存在浪费空间的问题，但是链表需要在每个结点上附加一个指针域，从而增加一定的空间开销。
时间复杂性比较
线性表的基本操作是存取、插入和删除。对于顺序表，随机存取是非常容易的，但是每插入或删除一个元素，都需要移动若干元素。对于链表，无法实现随机存取，必须要从表头开始遍历链表，直到找到要存取的元素，但是链表的插入和删除操作却非常简便，只需要修改几个指针值。
显然，当经常需要对线性表进行插入、删除操作时，链表的时间效率较高；当经常需要对线性表进行存取且存取操作比插入、删除操作更为频繁时，顺序表的时间效率较高。

§2.5 堆 栈

堆栈（Stack）和队列（Queue）是两种非常重要的数据结构，两者都是特殊的线性表：对于堆栈，所有的插入和删除（以至几乎所有的存取）都是在表的同一端进行；而对于队列来说，所有的插入都是在表的一端进行，所有的删除（以至几乎所有的存取）都是在表的另一端进行。
2.5.1 堆栈的定义和基本操作
定义2.2 堆栈（简称栈）是一种操作受限的线性表，只允许在表的同一端进行插入和删除操作，且这些操作是按后进先出的原则进行的。将进行插入和删除的一端称为栈顶，称另一端为栈底。当栈中无元素时称其为空栈。
在图2.12所示的堆栈中，诸元素以a1，a2，a3，a4，a5的顺序进栈，而退栈的次序则是a5，a4，a3，a2，a1 . 也就是说，从栈中取走元素是按后进先出的原则进行的，因此栈又被称作后进先出（Last in First Out）的线性表，简称为LIFO表。

a1
a5
a4
a3
a2
栈顶
栈底
出栈
进栈

图1 堆栈示意图

堆栈是受限的线性表，其基本操作包括：
Ÿ push ( item ) : 压入一个元素（插入）；
Ÿ pop ( item ) : 弹出一个元素（删除）；
Ÿ peek ( item ) : 存取栈顶元素值；
Ÿ clear ( ) : 清空栈；
Ÿ IsEmpty ( ) : 判断栈是否为空；
2.5.2 顺序栈
用顺序存储方式实现的堆栈称为顺序栈。顺序栈用数组存放栈元素，可方便地进行各种栈操作。某一堆栈的规模系指该堆栈最多能容纳的元素个数；存放堆栈的数组规模（或曰大小）应按堆栈的规模来确定。当堆栈中元素的个数达到堆栈规模（简称为栈满）时，则无法再向堆栈插入元素，换言之此时的插入操作将产生上溢出。
要实现顺序栈，应该创建一个数组来存放堆栈元素，这需要一个整型变量size来存放数组规模，以及一个整型变量top来存放栈顶元素在数组中的位置（下标）。当栈为空时，top值为-1，每入栈（出栈）一个元素，top值加1（减1），当top等于size-1时，说明栈满。

【顺序栈——入栈算法】：向顺序栈A中压入一个元素item. 入栈操作需要确定存储顺序栈的数组空间是否用完。
算法 Push (A, item) // 向顺序栈A中压入一个元素item
P1. [栈满？]
IF top=size-1 THEN (PRINT“栈满无法压入”. RETURN.)
P2. [入栈]
top¬top+1. // 更新栈顶元素的下标
A[top]¬item. // 压入新栈顶元素 ▐
【顺序栈——出栈算法】：从顺序栈A中弹出栈顶元素，并用指定变量item来存放。出栈操作需要确定栈非空。
算法 Pop (A.item) // 从顺序栈A中弹出栈顶元素，并存放在变量item中
P1. [栈空？]
IF top = -1 THEN (PRINT“栈空无法弹出”. RETURN.)
P2. [出栈]
item¬A[top]. // 保存栈顶元素值
top¬top-1. // 更新栈顶元素的下标 ▐

【顺序栈——存取栈顶元素】：与出栈算法类似，存取操作也要求用指定变量存放栈顶元素值，但不删除栈顶元素。
算法 Peek (A. item) // 将顺序栈A的栈顶元素存放在变量item中
P1. [栈空？]
IF top = -1 THEN (PRINT“栈空”. RETURN.)
P2. [读取栈顶元素]
item¬A[top]. // 保存栈顶元素值 ▐
2.5.3 链式栈
用单链表实现堆栈，首先要考虑栈顶对应链表的表头还是表尾。因为堆栈主要操作（插入、删除、存取）的对象是栈顶元素，若栈顶对应表尾，则每次栈顶操作都要对单链表进行遍历，其时间复杂性为O(n)（设链表的长度为n）；若栈顶对应表头，则每个操作的时间复杂性是O(1)，显然，栈顶对应表头是合理的。

【链式栈——入栈算法】：向链式栈top中压入一个元素，本质上是在表头插入一个新结点，并修改栈顶指针top.
算法 Push (item) // 向栈顶指针为top的链式栈中压入一个元素item
P1. [创建新结点]
sÜAVAIL. //为新结点申请空间
data(s) ¬item. next(s) ¬top. // 新结点的数据域存放item，指针域存放原栈顶结点的地址信息
P2. [更新栈顶指针]
top¬s. // 更新栈顶指针，令其指向新入栈结点▐
【链式栈——出栈算法】：从链式栈top中弹出栈顶元素，本质上是删除表头结点，并令top指向新表头结点（原次栈顶结点，即表头结点的后继结点）。出栈操作需要确定栈非空。
算法 Pop (. item) // 从栈顶指针为top的链式栈中弹出栈顶元素，并存放在变量item中
P1. [栈空？]
IF top= NULL THEN (PRINT“栈空无法弹出”. RETURN.)
P2. [出栈]
item¬data(top). // 保存栈顶结点的字段值
q¬next(top). // 令指针q指向次栈顶结点
AVAILÜtop. // 释放栈顶结点的空间
top¬ q. // 更新栈顶指针，令其指向q所指结点 ▐
【链式栈——存取栈顶元素】：该操作只需在确认栈非空的情况，把栈顶结点的字段值读取出来,存放在变量item中。
算法 Peek (. item) // 将栈顶指针为top的链式栈的栈顶元素存放在变量item中
P1. [栈空？]
IF top=NULL THEN (PRINT“栈空”. RETURN.)
P2. [存取栈顶]
item¬data(top). // 将栈顶结点的字段值保存在变量item中 ▐
【链式栈——栈清空】：清空链式栈top需要从栈顶开始逐一弹出结点并释放该结点的存储空间，直至栈空。
算法 Clear ( item) // 将栈顶指针为top的链式栈清空
P1. [逐一出栈，直至栈空]
WHILE top≠NULL DO
( q¬next(top). // 保存次栈顶结点的地址信息
AVAILÜtop. // 释放栈顶结点的存储空间
top¬q. ) // 更新栈顶指针 ▐
2.5.4 顺序栈与链式栈的比较
在空间复杂性上，顺序栈在创建时就申请了数组空间，若栈经常处于不满状态将造成存储空间的浪费；链式栈所需空间是根据需要随时申请的，比之顺序栈仅仅是其每个结点需要额外的的空间以存储其next指针域。在时间复杂性上，对于针对栈顶的基本操作（压入、弹出和栈顶元素存取），容易看出，顺序栈和链式栈的时间复杂性均为O(1) .
要说明的是，在堆栈的实际应用中，有时还需对非栈顶元素进行存取，对于这类存取操作，用数组实现的顺序栈可以快速定位，其时间复杂性为O(1) . 而链式栈则需要从表头开始遍历，最好情况下，需要存取的是次栈顶元素，即链式栈中表头结点的后继结点，时间复杂度为O(1)；最坏情况下，需要存取的是栈底元素，此时需要遍历整个链式栈，时间复杂度为O(n)；平均情况下，其时间复杂度亦为O(n) .
§2.6 队 列
2.6.1 队列的定义和基本操作
定义2.3 队列是一个操作受限的线性表，对于它的所有插入都在表的一端进行，所有的删除（以至几乎所有的存取）都在表的另一端进行，且这些操作又都是按着先进先出（FIFO）的原则进行的。进行删除的一端称为队头（front），进行插入的一端称为队尾（rear）。没有元素的队列称为空队列（简称空队）。
队列就像生活中排队购物，新来的人只能加入队尾（假设不允许插队），购物结束后离开的总是队头（假设无人中途离队）。也就是说，先加入队列的成员总是先离开队列，因此队列被称为先进先出(First In First Out)的线性表，简称为FIFO表。如图2.13，在空队列中依次加入元素a1，a2，a3，a4，a5，出队次序仍然是a1，a2，a3，a4，a5 .
入队
出队
图2.13 队列示意图
a1
a2
a3
a4
a5
队尾
队头

作为受限的线性表，队列的基本操作包括：
Ÿ 向队尾添加元素（入队）；
Ÿ 删除队首元素（出队）；
Ÿ 获取队首的元素值（存取）；
Ÿ 判断队列是否为满；
Ÿ 判断队列是否为空；
下面分别介绍顺序和链式两种存储方式所实现的队列——顺序队列和链式队列。
2.6.2 顺序队列
用顺序存储方式存储的队列被称为顺序队列。关于顺序队列，删除队头元素有两种方式：
（1）不要求队头元素必须存放在下标为零的数组元素中。每次删除队头元素，只需修改队头指针的位置（即队头元素在数组中的下标），令front=front+1 . 该方式的优点是无须改变诸队列元素的地址，缺点是front值随着队头元素的删除而不断增加，整个队列向数组的后端位置移动，随着队尾元素的不断加入，必然出现数组后端没有可用空间的情况，而数组前端的大量空间却被闲置。
（2）要求队头元素必须存放在下标为零的数组元素中。每次删除队头元素，令所有元素都向前移动一个位置。该方式的优点是不浪费空间，缺点是所有元素的地址都必须改变，效率低下。
为了克服上述缺点，可以假定数组是循环的，即采用环状模型来实现顺序队列。这种模型将队列在逻辑上置于一个圆环上，如图2.14所示，用整型变量front存放队头位置，每删除一个队头元素，就将front顺时针移动一个位置；整型变量rear存放新元素要插入的位置（下标），每插入一个元素，rear将顺时针移动一个位置；整型变量count存放队列中元素的个数，当count等于数组规模Size时，说明队列已满，当count等于0时，说明队列为空。
图2.14 队列的环状模型
Size = 4
Count = 3
Size = 4
Count = 2
front
删除A
rear
A
B
C
front
rear
B
C
插入D
D
B
C
front
rear
Size = 4
Count = 3
B
C
front
rear
Size = 4
Count = 3
D
B
C
front
rear
Size = 4
Count = 3
插入E
front
D
B
C
rear
Size = 4
Count = 3
E

环状队列的实现要用到求余运算：
rear顺时针移动1位： rear=(rear+1) MOD %Size ;
front顺时针移动1位：front=( front +1) MOD % Size ;
显然，环状队列解决了运算效率与空间利用率之间矛盾的问题。

【顺序队列——入队】：在A的队尾插入一个新元素item。因为队列用数组存放，所以在插入之前要确定队列是否已满。插入操作除了要把新元素存入队尾，还应更新队尾下标和队列长度。
算法QInsert (A, item) // 在队列A中将元素item插入队尾
QI1. [队列满？]
IF count=size THEN (PRINT“队列已满无法插入”. RETURN. )
QI2. [申请空间]
A[rear] ¬item. // 将新元素插入队尾
QI3. [更新]
rear¬MOD(rear+1, size). // 更新队尾下标
count¬count+1. // 更新队列长度 ▐
【顺序队列——出队】：删除A的队首元素。删除之前需要确定队列是否为空，删除操作实际就是更新队首元素下标，因为队列中元素减少，所以还要更新队列长度。
算法QDelete (A.item) // 删除队列A的队首元素，并将其元素值赋给变量item
QD1. [队列空？]
IF count=0 THEN (PRINT “队列空无法删除”. RETURN. )
QD2. [出队]
item ¬A[front]. // 将队首元素保存至item
QD3. [更新]
front¬MOD(front+1, size). // 更新队首元素下标
count¬count -1. // 更新队列长度 ▐
【顺序队列——存取队首】：存取A队首元素值。本操作与出队操作类似，但无需修改队首元素下标和队列长度。
算法QFront (A. item) // 读取队列A的队首元素值，并将其赋给变量item
QF1. [队列空？]
IF count=0 THEN (PRINT “队列空无法读取”. RETURN. )
QF2. [存取]
item ¬A[front]. // 将队首元素保存至item ▐
2.6.3 链式队列
用链接存储方式实现的队列称为链式队列。队列的主要操作都在队首和队尾进行，所以链式队列的私有数据成员包含两个指针：队首指针front和队尾指针rear，分别存放队首和队尾结点的地址信息。链式队列中没有哨位结点。

【链式队列——入队】：在队尾插入一个新元素。该算法需要为新元素申请一个结点空间，然后修改原表尾结点的next指针和表尾指针，令它们均保存新结点的地址信息；要注意的是，如果插入新元素之前队列为空，则还需要修改表头指针，令其指向新结点。
算法QInsert (item) // 将元素item插入队尾
QI1. [创建新结点]
sÜ AVAIL. data(s)¬item. next(s)¬NULL. // 为新结点申请空间，令其字段值为item，指针域为空
QI2. [队空？]
IF front=NULL THEN front¬s. // 若队列为空，令队首指针指向s
ELSE next(rear)¬s. // 若队列非空，令表尾结点的next指针指向s
QI3. [更新]
rear¬s. // 更新表尾指针▐
【链式队列——出队】：删除队首元素。该算法首先要判断队列是否为空