2024年4月11日发(作者：)

实验三栈与队列

一实验任务

1)

栈的应用

2)

队列的表示与实现二实验目的

1

)

了解栈与队列的特性

2)

掌握栈的顺序、链式存储表示及实现

3)

掌握队列的顺序、链式存储表示及实现

4)

掌握栈与队列在实际问题中的应用三实验原理

1 .

栈的特性

栈

(

Stack)

又称堆栈，是一种特殊的线性表，可定义为插入、删除和访问 只能在

某一端进行的线性数据结构。堆栈允许插入、删除和访问的一端称为栈顶

(Top),

另一

端称为栈底

(

Bottom)

。栈顶的第一个元素被称为栈顶元素。

堆栈的性质决定它的数据是按''先进后出〃的顺序被访问，即最先存储的元素 最

后被访问、删除，最后存储的元素最先被访问、删除，所以栈也称为、'

LIFO"

(Last_In, First_Out)

。

栈济抽象数鬼类型定义如下：

ADT Stack{

数据对象:

数据对象:

D={ai | a

；

E ElemSet, i = 1,2,…,n, n>0}R = { v an, ai > |

数据关系:

ai-i, ai eD, i = 2,…

，

n }

约定

dn

端为栈顶，

dl

端为栈底。

基本操作：

InitStack(&S)操作结果：构造一个空栈S。

Push(&S, e)初始条件：栈S已存在。

操作结果：插入元素

e

为新的栈顶元素。

Pop(&S, &e)初始条件：栈S已存在且非空。

操作结果：删除

S

的栈顶元素，并用

e

返回其值。

GetTop(S, &e)初始条件：栈S已存在且非空。

操作结果：用

e

返回

S

的栈顶元素。

StackEmpty(S)初始条件：栈S已存在。

操作结果：假设

S

为空栈，那么返回

TRUE,

否那么返回

FALSE

。

StackLength(S)初始条件：栈S已存在。

操作结果：返回

S

的元素个数，即栈的长度。

StackTraverse(S, visit())初始条件：栈S已存在且非空。

操作结果：从栈底到栈顶依次对

S

的每个数据元素调用函数

visit ()o

一

旦

visit

。失败，那么操作失败。

ClearStack(&S)初始条件：栈S已存在。

操作结果：将

S

清为空栈。

DestroyStack(&S)初始条件：栈S已存在。

操作结果：栈

S

被销毁。

} ADT Stack

2

.栈的顺序表示

栈的顺序存储结构，即顺序栈，是利用一组连续的存储单元依次存放自栈底 到栈顶

的数据元素，同时通过指针

top

指示栈顶元素在顺序栈中的位置。由于很 难估计栈在使

用过程中所需要的最大空间的大小，所以通常利用

C

语言中动态分 配的一组连续的存

储单元作为顺序栈所需要的存储空间。

顺序栈所需要的具体数据类型描述如下：

#define STACKJNCREASE 10

#define MAXLEN 100

#define STACKJNCREASE 10

〃顺序栈存储空间的动态分配增量

〃栈的存储空间的基地址，即栈底指针

〃栈顶指针〃栈当前分配的存储容量

typedef struct{

ElemType *base;

}SqStack;

Elemlype *top; int

其中，

maxsize

指示栈当前可使用的最大容量；

base

为栈底指针，在顺序栈 中，它始终指向栈底的位

maxsize;

置，假设

base=NULL,

那么说明栈结构不存在；

top

为栈

顶 指针，起初值为栈底指针值，即

top=base,

这也可作为栈空的标记。栈插入新 元素

时，将新元素插入到栈顶指针所指向的位置，同时指针

top

增

1,

删除栈顶 元素时，指

针

top

减

1

。

3 .

栈的链式存储表示

栈的链式存储结构，即链栈，与线性表的链式存储结构类似，是通过由结点 构成

的单链表实现的，但每个结点的指针指向其前驱结点(在其之前进栈的结点)。

此时，表头指针称为栈顶指针，其指向的结点即为栈顶结点。所需要的具体数据 类型描

述如下：

typedef struct SNode{ElemType data;

struct SNode *prior;"prior

将指向其前一次入栈的元素

}SNode, *SLink;

4 .

队列的特性

队列

(

Queue)

简称队，也是一种特殊的线性表，可定义为只允许在表的一 端进行插

入，而在表的另一端进行删除的线性结构。队列允许插入的一端称为队 尾

(Rear),

允许

删除的一端称为队首

(Front)

o

由于队列的插入和删除分别在不同的两端进行，因而先插入者自然先从另一 端删

除，所以队列具有''先进先出〃的特点,简称为

FIFO (First-In, First-Out)

。

队列的抽象数据类型定义如下：

ADT Queue {

数据对象：

D={a

(

| a

；

G ElemSet, i = 1,2,…,n, n>0}

数据关系：

Rl= { < ai-i, ai > | ai-i, ai GD, i = 2,…,n )约定其中ai端为队

首，an端为队尾。

基本操作：

InitQueue(&Q)操作结果：构造一个空队列Q。

QueueEmpty(Q)初始条件：队列Q已存在。

操作结果：假设

Q

为空队列，那么返回

TRUE,

否那么

FALSE

。

QueueLength(Q)初始条件：队列Q已存在。

操作结果：返回

Q

的元素个数，即队列的长度。

EnQueue(&Q, e)初始条件：队列Q已存在。

操作结果：插入元素

e

为

Q

的新的队尾元素。

DeQueue(&Q, &e)初始条件：Q为非空队列。

操作结果：删除

Q

的队首元素，并用

e

返回其值。

GetHead(Q, &e)初始条件：Q为非空队列。

操作结果：用

e

返回

Q

的队首元素。

QueueTraverse(Q, visit())初始条件：Q已存在且非空。

操作结果：从队首到队尾，依次对

Q

的每个数据元素调用函数

visit( )o

一旦

visit

。失败，那么操作失败。

ClearQueue(&Q)初始条件：队列Q已存在。

操作结果：将

Q

清为空队列。

DestroyQueue(&Q)初始条件：队列Q已存在。

操作结果：队列

Q

被销毁，不再存在。

}ADT Queue

5

.队列的顺序表示

队列的顺序存储结构，用一组地址连续的存储单元依次存放从队首到队尾的 元素，

同时附设两个指针

front

和

rear

分别指示队首元素及队尾元素的位置。

循环队列所需要的具体数据类型描述如下：

#define MAXQSIZE 100

〃最大队列长度

typedef struct {ElemType * base;

〃初始化的动态分配存储空间

int front;

〃头指针，假设队列不空，指向队首元素

int rear;

〃尾指针，假设队

列不空，指向队尾元素的下一个位置

}SqQueue;

6.

队列的链式存储表示

队列的链接存储结构，简称链队列。链队列所需要的具体数据类型描述如下:

typedef struct QNode {ElemType data;

〃值域

struct QNode * next;

〃链接指针域

}QNode, * QueuePtr;

typedef struct {QueuePtr front;

〃头指针

QueuePtr rear;

〃尾指针

}LinkQueue;四实验设备、仪器、工具与材料

微机、

VC

五实验内容

（1）

实验任务

1

：

栈的应用一迷宫求解

编制

C

程序完成迷宫问题。程序基本要求：用户输入迷宫数据初始化迷宫; 利用

栈的顺序表示以及入栈、出栈等基本操作，实现迷宫路径的求解；输出求解 得到的完

整路径（或提示迷宫无通路）。

（2）

实验任务

2

：

队列的表示与实现

编写一个

C

程序实现顺序队列的各种基本操作，并在此基础上设计一个主程 序，

完成如下功能：

1

）

建立循环队列

2）

入队列

3）

出队列

4）

判断队列是否为空

5）

遍历队列

6）

取队首元素六实验步骤

（1）

实验预习

1

）

预习本实验原理中关于栈与队列的定义、顺序存储表示。

2

）分析掌握教材

48-50

页中的算法

3-1~3-4,

为完成实验任务

1

做好准备。

3）

分析掌握教材

57~60

页中迷宫问题及求解算法

3-13,

为完成实验任务

1

做好准

备。

4）

分析掌握教材

70~73

页中的算法

3-15~3-20,

为完成实验任务

2

做好准 备。

（2）

实验步骤

1）

问题分析。充分地分析和理解此实验任务，弄清要求作什么，限制条件 是什么。

2）

系统的结构设计。按照以数据结构为中心的原那么划分模块。最后写出每 个子

程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用 关系图表示

那么更加清晰，这样便完成了系统结构设计。

3）

详细设计。详细设计的目的是对子程序（过程或函数）的进一步求精。 用

IF

、

WHILE

和赋值语句等，以及自然语言写出算法的框架。利用自然语言的 目的是防止陷

入细节。

4）

编码。在详细设计的基础上，对详细设计的结果进一步求精，用

C

语言 表示出

来。

5）

在

VC

环境下调试程序。

七实验报告要求

实验报告包含程序开发过程所形成的所有文档资料，包括如下内容：

1）

需求分析及规格说明：问题描述，求解的问题是什么。

2）

概要设计：本程序所用的数据类型定义；主程序流程；程序模块及相互 关系。

3）

详细设计：采用

C

语言定义的数据结构；各模块的伪码算法；各函数调 用关系。

4）

调试报告。

5）

本实验任务

1

、

2

的程序清单及运行结果。

八思考题

如果一个程序中用到两个栈，为了不发生溢出错误，就必须给每个栈预先一 个较

大的存储空间。假设每个栈都预先分配过大的存储空间，势必造成系统空间紧 张，如何

解决这个问题？