一、实验目的和要求
(1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。
(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。
(3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。
(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。
二、实验环境和方法
实验方法：
（一）综合运用课本所学的知识，用不同的算法实现在不同的程序功能。
（二）结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。
（三）根据实验内容，编译程序。
实验环境：Windows xp Visual C++6.0
三、实验内容及过程描述
实验步骤：
① 进入Visual C++ 6.0集成环境。
② 输入自己编好的程序。
③ 检查一遍已输入的程序是否有错（包括输入时输错的和编程中的错误），如发现有
错，及时改正。
④ 进行编译和连接。如果在编译和连接过程中发现错误，频幕上会出现“报错信息”，
根据提示找到出错位置和原因，加以改正。再进行编译，如此反复直到不出错为止。 ⑤ 运行程序并分析运行结果是否合理。在运行是要注意当输入不同的数据时所得结果
是否正确，应运行多次，分别检查在不同情况下结果是否正确。
实验内容：编译以下题目的程序并调试运行。
1）、编写一个程序algo3-1.cpp，实现顺
的各种基本运算，并在此基础上设计一
程序并完成如下功能：
（1）初始化栈s；
（2）判断栈s是否非空； 序栈个主
（3）依次进栈元素a,b,c,d,e；
（4）判断栈s是否非空；
（5）输出出栈序列；
（6）判断栈s是否非空；
（7）释放栈。 图3.1 Proj3_1 工程组成
本工程Proj3_1的组成结构如图3.1所示。本工程的模块结构如图3.2所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。
图3.2 Proj3_1工程的程序结构图
其中包含如下函数：
InitStack(SqStack *&s) //初始化栈S
DestroyStack(SqStack *&s) //销毁栈s
StackEmpty(SqStack *s) //判断栈空
Push(SqStack *&s,ElemType e) //进栈
Pop(SqStack *&s,ElemType &e) //出栈
GetTop(SqStack *s,ElemType &e) //取栈顶元素
对应的程序如下：
//文件名:algo3-1.cpp
#include
#include
#define MaxSize 100
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int top; //栈顶指针
} SqStack;
void InitStack(SqStack *&s) //初始化栈S
{ s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1; //栈顶指针置为-1
}
void DestroyStack(SqStack *&s) //销毁栈s
{
free(s);
}
bool StackEmpty(SqStack *s) //判断栈空
{
return(s->top==-1);
}
bool Push(SqStack *&s,ElemType e) //进栈
{ if (s->top==MaxSize-1) //栈满的情况，即栈上溢出
return false;
s->top++; //栈顶指针增1
s->data[s->top]=e; //元素e放在栈顶指针处
return true;
}
bool Pop(SqStack *&s,ElemType &e) //出栈
{ if (s->top==-1) //栈为空的情况，即栈下溢出
return false;
e=s->data[s->top]; //取栈顶指针元素的元素
s->top--; //栈顶指针减1
return true;
}
bool GetTop(SqStack *s,ElemType &e) //取栈顶元素
{ if (s->top==-1) //栈为空的情况，即栈下溢出
return false;
e=s->data[s->top]; //取栈顶指针元素的元素
return true;
}
设计exp3-1.cpp程序如下 //文件名:exp3-1.cpp
#include
#include
#define MaxSize 100
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int top; //栈顶指针
} SqStack;
extern void InitStack(SqStack *&s);
extern void DestroyStack(SqStack *&s);
extern bool StackEmpty(SqStack *s);
extern bool Push(SqStack *&s,ElemType e);
extern bool Pop(SqStack *&s,ElemType &e);
extern bool GetTop(SqStack *s,ElemType &e);
void main()
{
ElemType e;
SqStack *s;
printf("栈s的基本运算如下:\n");
printf(" (1)初始化栈s\n");
InitStack(s);
printf(" (2)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (3)依次进栈元素a,b,c,d,e\n");
Push(s,'a');
Push(s,'b');
Push(s,'c');
Push(s,'d');
Push(s,'e');
printf(" (4)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (5)出栈序列:");
while (!StackEmpty(s))
{
Pop(s,e);
printf("%c ",e);
}
printf("\n");
printf(" (6)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (7)释放栈\n");
DestroyStack(s);
}
运行结果如下：
2）、编写一个程序algo3-2.cpp，实现链栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：
（1）初始化链栈s；
（2）判断链栈s是否非空；
（3）依次进栈a，b，c，d，e；
（4）判断链栈s是否非空；
（5）输出链栈长度；
（6）输出从栈底到栈顶元素；
（7）输出出队序列；
（8）判断链栈s是否非空； 图3.3 Proj3_2工程组成
（9）释放队列。
本工程Proj3_2的组成结构如图3.3所示。本工程的模块结构如图3.4所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。
图3.4 Proj3_2工程的程序结构图
其中包含如下函数：
InitStack(LiStack *&s) //初始化栈s
DestroyStack(LiStack *&s) //销毁栈
StackEmpty(LiStack *s) //判断栈是否为空
Push(LiStack *&s,ElemType e) //进栈
Pop(LiStack *&s,ElemType &e) //出栈
GetTop(LiStack *s,ElemType &e) //取栈顶元素
对应的程序如下：
//文件名:algo3-2.cpp
#include
#include
typedef char ElemType;
typedef struct linknode
{
ElemType data; //数据域
2）、编写一个程序algo3-2.cpp，实现链栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：
（1）初始化链栈s；
（2）判断链栈s是否非空；
（3）依次进栈a，b，c，d，e；
（4）判断链栈s是否非空；
（5）输出链栈长度；
（6）输出从栈底到栈顶元素；
（7）输出出队序列；
（8）判断链栈s是否非空； 图3.3 Proj3_2工程组成
（9）释放队列。
本工程Proj3_2的组成结构如图3.3所示。本工程的模块结构如图3.4所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。
图3.4 Proj3_2工程的程序结构图
其中包含如下函数：
InitStack(LiStack *&s) //初始化栈s
DestroyStack(LiStack *&s) //销毁栈
StackEmpty(LiStack *s) //判断栈是否为空
Push(LiStack *&s,ElemType e) //进栈
Pop(LiStack *&s,ElemType &e) //出栈
GetTop(LiStack *s,ElemType &e) //取栈顶元素
对应的程序如下：
//文件名:algo3-2.cpp
#include
#include
typedef char ElemType;
typedef struct linknode
{
ElemType data; //数据域
ElemType data; //数据域
struct linknode *next; //指针域
} LiStack;
void InitStack(LiStack *&s) //初始化栈s
{ s=(LiStack *)malloc(sizeof(LiStack));
s->next=NULL;
}
void DestroyStack(LiStack *&s) //销毁栈
{ LiStack *p=s,*q=s->next;
while (q!=NULL)
{ free(p);
p=q;
q=p->next;
}
free(p); //此时p指向尾节点,释放其空间
}
bool StackEmpty(LiStack *s) //判断栈是否为空
{
return(s->next==NULL);
}
void Push(LiStack *&s,ElemType e) //进栈
{ LiStack *p;
p=(LiStack *)malloc(sizeof(LiStack));
p->data=e; //新建元素e对应的节点*p
p->next=s->next; //插入*p节点作为开始节点
s->next=p;
}
bool Pop(LiStack *&s,ElemType &e) //出栈
{ LiStack *p;
if (s->next==NULL) //栈空的情况
return false;
p=s->next; //p指向开始节点
e=p->data;
s->next=p->next; //删除*p节点
free(p); //释放*p节点
return true;
}
bool GetTop(LiStack *s,ElemType &e) //取栈顶元素
{ if (s->next==NULL) //栈空的情况
return false;
e=s->next->data;
return true;
}
设计 exp3-2.cpp 主程序
//文件名:exp3-2.cpp
#include
#include
typedef char ElemType;
typedef struct linknode
{
ElemType data; //数据域
struct linknode *next; //指针域
} LiStack;
extern void InitStack(LiStack *&s);
extern void DestroyStack(LiStack *&s);
extern bool StackEmpty(LiStack *s);
extern void Push(LiStack *&s,ElemType e);
extern bool Pop(LiStack *&s,ElemType &e);
extern bool GetTop(LiStack *s,ElemType &e);
void main()
{
ElemType e;
LiStack *s;
printf("栈s的基本运算如下:\n");
printf(" (1)初始化栈s\n");
InitStack(s);
printf(" (2)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (3)依次进栈元素a,b,c,d,e\n");
Push(s,'a');
Push(s,'b');
Push(s,'c');
Push(s,'d');
Push(s,'e');
printf(" (4)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (5)出栈序列:");
while (!StackEmpty(s))
{
Pop(s,e);
printf("%c ",e);
}
printf("\n");
printf(" (6)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (7)释放栈\n");
DestroyStack(s);
}
程序运行结果如下：
3）、编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能：
（1）初始化队列q；
（2）判断队列q是否非空；
（3）依次进队列a,b,c；
（4）出队一个元素，输出该元素；
（5）输出队列q的元素个数；
（6）依次进队列元素d,e,f； 图3-5 Proj3_3的工程组成
（7）输出队列q的元素个数；
（8）输出出队序列；
（9）释放队列。
本工程Proj3_3的组成结构如图3.5所示。本工程的模块结构如图3.6所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。
图3.6 Proj3_3工程的程序结构图
其中包含如下函数：
InitQueue(SqQueue *&q) //初始化队列
//销毁队列 DestroyQueue(SqQueue *&q)
QueueEmpty(SqQueue *q) //判断队列空
enQueue(SqQueue *&q,ElemType e) //进队
deQueue(SqQueue *&q,ElemType &e) //出队
对应的程序如下： //文件名:algo3-3.cpp
#include
#include
#define MaxSize 5
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int front,rear; //队首和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q) //初始化队列 { q=(SqQueue *)malloc (sizeof(SqQueue)); q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q) //销毁队列 {
free(q);
}
bool QueueEmpty(SqQueue *q) //判断队列空 {
return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e) //进队 {
if ((q->rear+1)%MaxSize==q->front) //队满上溢出 return false;
q->rear=(q->rear+1)%MaxSize;
q->data[q->rear]=e;
return true;
}
bool deQueue(SqQueue *&q,ElemType &e) //出队 {
if (q->front==q->rear) //队空下溢出 return false;
q->front=(q->front+1)%MaxSize;
e=q->data[q->front];
return true;
}
设计 exp3-3.cpp 主程序
#include
#include
#define MaxSize 5
typedef char ElemType; typedef struct { ElemType elem[MaxSize]; int front,rear; //队首和队尾指针 } SqQueue; extern void InitQueue(SqQueue *&q); extern void DestroyQueue(SqQueue *&q); extern bool QueueEmpty(SqQueue *q); extern bool enQueue(SqQueue *&q,ElemType e); extern bool deQueue(SqQueue *&q,ElemType &e); void main() { ElemType e; SqQueue *q; printf("环形队列基本运算如下:\n"); printf(" (1)初始化队列q\n"); InitQueue(q); printf(" (2)依次进队列元素a,b,c\n"); if (!enQueue(q,'a')) printf("\t提示:队满,不能进队\n"); if (!enQueue(q,'b')) printf("\t提示:队满,不能进队\n"); if (!enQueue(q,'c')) printf("\t提示:队满,不能进队\n"); printf(" (3)队列为%s\n",(QueueEmpty(q)?"空":"非空")); if (deQueue(q,e)==0) printf("队空,不能出队\n"); else printf(" (4)出队一个元素%c\n",e); printf(" (5)依次进队列元素d,e,f\n"); if (!enQueue(q,'d')) printf("\t提示:队满,不能进队\n"); if (!enQueue(q,'e')) printf("\t提示:队满,不能进队\n"); if (!enQueue(q,'f')) printf("\t提示:队满,不能进队\n"); printf(" (6)出队列序列:"); while (!QueueEmpty(q)) { deQueue(q,e); printf("%c ",e); } printf("\n"); printf(" (7)释放队列\n"); DestroyQueue(q); }
程序运行结果如下：
四、总结
从数据结构的定义看，栈和队列也是一种线性表。其与线性表的不同之处在于栈和队列的相关运算具有特殊性，只是线性表相关运算的一个子集。一般线性表的上的插入、删除运算不受限制，而栈和队列上的插入、删除运算受某种特殊限制。因此。栈和队列也称为操作受限的线性表。
一、实验目的和要求
(1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。
(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。
(3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。
(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。
二、实验环境和方法
实验方法：
（一）综合运用课本所学的知识，用不同的算法实现在不同的程序功能。
（二）结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。
（三）根据实验内容，编译程序。
实验环境：Windows xp Visual C++6.0
三、实验内容及过程描述
实验步骤：
① 进入Visual C++ 6.0集成环境。
② 输入自己编好的程序。
③ 检查一遍已输入的程序是否有错（包括输入时输错的和编程中的错误），如发现有
错，及时改正。
④ 进行编译和连接。如果在编译和连接过程中发现错误，频幕上会出现“报错信息”，
根据提示找到出错位置和原因，加以改正。再进行编译，如此反复直到不出错为止。 ⑤ 运行程序并分析运行结果是否合理。在运行是要注意当输入不同的数据时所得结果
是否正确，应运行多次，分别检查在不同情况下结果是否正确。
实验内容：编译以下题目的程序并调试运行。
1）、编写一个程序algo3-1.cpp，实现顺
的各种基本运算，并在此基础上设计一
程序并完成如下功能：
（1）初始化栈s；
（2）判断栈s是否非空； 序栈个主
（3）依次进栈元素a,b,c,d,e；
（4）判断栈s是否非空；
（5）输出出栈序列；
（6）判断栈s是否非空；
（7）释放栈。 图3.1 Proj3_1 工程组成
本工程Proj3_1的组成结构如图3.1所示。本工程的模块结构如图3.2所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。
图3.2 Proj3_1工程的程序结构图
其中包含如下函数：
InitStack(SqStack *&s) //初始化栈S
DestroyStack(SqStack *&s) //销毁栈s
StackEmpty(SqStack *s) //判断栈空
Push(SqStack *&s,ElemType e) //进栈
Pop(SqStack *&s,ElemType &e) //出栈
GetTop(SqStack *s,ElemType &e) //取栈顶元素
对应的程序如下：
//文件名:algo3-1.cpp
#include
#include
#define MaxSize 100
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int top; //栈顶指针
} SqStack;
void InitStack(SqStack *&s) //初始化栈S
{ s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1; //栈顶指针置为-1
}
void DestroyStack(SqStack *&s) //销毁栈s
{
free(s);
}
bool StackEmpty(SqStack *s) //判断栈空
{
return(s->top==-1);
}
bool Push(SqStack *&s,ElemType e) //进栈
{ if (s->top==MaxSize-1) //栈满的情况，即栈上溢出
return false;
s->top++; //栈顶指针增1
s->data[s->top]=e; //元素e放在栈顶指针处
return true;
}
bool Pop(SqStack *&s,ElemType &e) //出栈
{ if (s->top==-1) //栈为空的情况，即栈下溢出
return false;
e=s->data[s->top]; //取栈顶指针元素的元素
s->top--; //栈顶指针减1
return true;
}
bool GetTop(SqStack *s,ElemType &e) //取栈顶元素
{ if (s->top==-1) //栈为空的情况，即栈下溢出
return false;
e=s->data[s->top]; //取栈顶指针元素的元素
return true;
}
设计exp3-1.cpp程序如下 //文件名:exp3-1.cpp
#include
#include
#define MaxSize 100
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int top; //栈顶指针
} SqStack;
extern void InitStack(SqStack *&s);
extern void DestroyStack(SqStack *&s);
extern bool StackEmpty(SqStack *s);
extern bool Push(SqStack *&s,ElemType e);
extern bool Pop(SqStack *&s,ElemType &e);
extern bool GetTop(SqStack *s,ElemType &e);
void main()
{
ElemType e;
SqStack *s;
printf("栈s的基本运算如下:\n");
printf(" (1)初始化栈s\n");
InitStack(s);
printf(" (2)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (3)依次进栈元素a,b,c,d,e\n");
Push(s,'a');
Push(s,'b');
Push(s,'c');
Push(s,'d');
Push(s,'e');
printf(" (4)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (5)出栈序列:");
while (!StackEmpty(s))
{
Pop(s,e);
printf("%c ",e);
}
printf("\n");
printf(" (6)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (7)释放栈\n");
DestroyStack(s);
}
运行结果如下：
2）、编写一个程序algo3-2.cpp，实现链栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：
（1）初始化链栈s；
（2）判断链栈s是否非空；
（3）依次进栈a，b，c，d，e；
（4）判断链栈s是否非空；
（5）输出链栈长度；
（6）输出从栈底到栈顶元素；
（7）输出出队序列；
（8）判断链栈s是否非空； 图3.3 Proj3_2工程组成
（9）释放队列。
本工程Proj3_2的组成结构如图3.3所示。本工程的模块结构如图3.4所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。
图3.4 Proj3_2工程的程序结构图
其中包含如下函数：
InitStack(LiStack *&s) //初始化栈s
DestroyStack(LiStack *&s) //销毁栈
StackEmpty(LiStack *s) //判断栈是否为空
Push(LiStack *&s,ElemType e) //进栈
Pop(LiStack *&s,ElemType &e) //出栈
GetTop(LiStack *s,ElemType &e) //取栈顶元素
对应的程序如下：
//文件名:algo3-2.cpp
#include
#include
typedef char ElemType;
typedef struct linknode
{
ElemType data; //数据域
2）、编写一个程序algo3-2.cpp，实现链栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：
（1）初始化链栈s；
（2）判断链栈s是否非空；
（3）依次进栈a，b，c，d，e；
（4）判断链栈s是否非空；
（5）输出链栈长度；
（6）输出从栈底到栈顶元素；
（7）输出出队序列；
（8）判断链栈s是否非空； 图3.3 Proj3_2工程组成
（9）释放队列。
本工程Proj3_2的组成结构如图3.3所示。本工程的模块结构如图3.4所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。
图3.4 Proj3_2工程的程序结构图
其中包含如下函数：
InitStack(LiStack *&s) //初始化栈s
DestroyStack(LiStack *&s) //销毁栈
StackEmpty(LiStack *s) //判断栈是否为空
Push(LiStack *&s,ElemType e) //进栈
Pop(LiStack *&s,ElemType &e) //出栈
GetTop(LiStack *s,ElemType &e) //取栈顶元素
对应的程序如下：
//文件名:algo3-2.cpp
#include
#include
typedef char ElemType;
typedef struct linknode
{
ElemType data; //数据域
ElemType data; //数据域
struct linknode *next; //指针域
} LiStack;
void InitStack(LiStack *&s) //初始化栈s
{ s=(LiStack *)malloc(sizeof(LiStack));
s->next=NULL;
}
void DestroyStack(LiStack *&s) //销毁栈
{ LiStack *p=s,*q=s->next;
while (q!=NULL)
{ free(p);
p=q;
q=p->next;
}
free(p); //此时p指向尾节点,释放其空间
}
bool StackEmpty(LiStack *s) //判断栈是否为空
{
return(s->next==NULL);
}
void Push(LiStack *&s,ElemType e) //进栈
{ LiStack *p;
p=(LiStack *)malloc(sizeof(LiStack));
p->data=e; //新建元素e对应的节点*p
p->next=s->next; //插入*p节点作为开始节点
s->next=p;
}
bool Pop(LiStack *&s,ElemType &e) //出栈
{ LiStack *p;
if (s->next==NULL) //栈空的情况
return false;
p=s->next; //p指向开始节点
e=p->data;
s->next=p->next; //删除*p节点
free(p); //释放*p节点
return true;
}
bool GetTop(LiStack *s,ElemType &e) //取栈顶元素
{ if (s->next==NULL) //栈空的情况
return false;
e=s->next->data;
return true;
}
设计 exp3-2.cpp 主程序
//文件名:exp3-2.cpp
#include
#include
typedef char ElemType;
typedef struct linknode
{
ElemType data; //数据域
struct linknode *next; //指针域
} LiStack;
extern void InitStack(LiStack *&s);
extern void DestroyStack(LiStack *&s);
extern bool StackEmpty(LiStack *s);
extern void Push(LiStack *&s,ElemType e);
extern bool Pop(LiStack *&s,ElemType &e);
extern bool GetTop(LiStack *s,ElemType &e);
void main()
{
ElemType e;
LiStack *s;
printf("栈s的基本运算如下:\n");
printf(" (1)初始化栈s\n");
InitStack(s);
printf(" (2)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (3)依次进栈元素a,b,c,d,e\n");
Push(s,'a');
Push(s,'b');
Push(s,'c');
Push(s,'d');
Push(s,'e');
printf(" (4)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (5)出栈序列:");
while (!StackEmpty(s))
{
Pop(s,e);
printf("%c ",e);
}
printf("\n");
printf(" (6)栈为%s\n",(StackEmpty(s)?"空":"非空"));
printf(" (7)释放栈\n");
DestroyStack(s);
}
程序运行结果如下：
3）、编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能：
（1）初始化队列q；
（2）判断队列q是否非空；
（3）依次进队列a,b,c；
（4）出队一个元素，输出该元素；
（5）输出队列q的元素个数；
（6）依次进队列元素d,e,f； 图3-5 Proj3_3的工程组成
（7）输出队列q的元素个数；
（8）输出出队序列；
（9）释放队列。
本工程Proj3_3的组成结构如图3.5所示。本工程的模块结构如图3.6所示。图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系。
图3.6 Proj3_3工程的程序结构图
其中包含如下函数：
InitQueue(SqQueue *&q) //初始化队列
//销毁队列 DestroyQueue(SqQueue *&q)
QueueEmpty(SqQueue *q) //判断队列空
enQueue(SqQueue *&q,ElemType e) //进队
deQueue(SqQueue *&q,ElemType &e) //出队
对应的程序如下： //文件名:algo3-3.cpp
#include
#include
#define MaxSize 5
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int front,rear; //队首和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q) //初始化队列 { q=(SqQueue *)malloc (sizeof(SqQueue)); q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q) //销毁队列 {
free(q);
}
bool QueueEmpty(SqQueue *q) //判断队列空 {
return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e) //进队 {
if ((q->rear+1)%MaxSize==q->front) //队满上溢出 return false;
q->rear=(q->rear+1)%MaxSize;
q->data[q->rear]=e;
return true;
}
bool deQueue(SqQueue *&q,ElemType &e) //出队 {
if (q->front==q->rear) //队空下溢出 return false;
q->front=(q->front+1)%MaxSize;
e=q->data[q->front];
return true;
}
设计 exp3-3.cpp 主程序
#include
#include
#define MaxSize 5
typedef char ElemType; typedef struct { ElemType elem[MaxSize]; int front,rear; //队首和队尾指针 } SqQueue; extern void InitQueue(SqQueue *&q); extern void DestroyQueue(SqQueue *&q); extern bool QueueEmpty(SqQueue *q); extern bool enQueue(SqQueue *&q,ElemType e); extern bool deQueue(SqQueue *&q,ElemType &e); void main() { ElemType e; SqQueue *q; printf("环形队列基本运算如下:\n"); printf(" (1)初始化队列q\n"); InitQueue(q); printf(" (2)依次进队列元素a,b,c\n"); if (!enQueue(q,'a')) printf("\t提示:队满,不能进队\n"); if (!enQueue(q,'b')) printf("\t提示:队满,不能进队\n"); if (!enQueue(q,'c')) printf("\t提示:队满,不能进队\n"); printf(" (3)队列为%s\n",(QueueEmpty(q)?"空":"非空")); if (deQueue(q,e)==0) printf("队空,不能出队\n"); else printf(" (4)出队一个元素%c\n",e); printf(" (5)依次进队列元素d,e,f\n"); if (!enQueue(q,'d')) printf("\t提示:队满,不能进队\n"); if (!enQueue(q,'e')) printf("\t提示:队满,不能进队\n"); if (!enQueue(q,'f')) printf("\t提示:队满,不能进队\n"); printf(" (6)出队列序列:"); while (!QueueEmpty(q)) { deQueue(q,e); printf("%c ",e); } printf("\n"); printf(" (7)释放队列\n"); DestroyQueue(q); }
程序运行结果如下：
四、总结
从数据结构的定义看，栈和队列也是一种线性表。其与线性表的不同之处在于栈和队列的相关运算具有特殊性，只是线性表相关运算的一个子集。一般线性表的上的插入、删除运算不受限制，而栈和队列上的插入、删除运算受某种特殊限制。因此。栈和队列也称为操作受限的线性表。