实验一：队列的应用、栈的应用
一． 实验目的
1、掌握队列的特点(先进先出 FIFO)及基本操作，如入队、出队等。
2、利用循环队列的特点解决实际问题，提高编程能力。
3、掌握栈的特点(先进后出 FILO)及基本操作，如入栈、出栈等。
4、利用栈的特点解决实际问题，提高编程能力。
二． 实验内容
1、编写一个程序实现循环队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
(1)初始化循环队列；
(2)给定一个元素，将此元素插入此队列中；
(3)将队头一个元素出队。
2、编程实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
(1)初始化顺序栈；
(2)给定一个元素，将此元素压入此栈中；
(3)将栈顶一个元素弹出此栈。
三． 数据结构及算法设计描述
循环队列和栈都是线性结构，是逻辑结构的一种。而存储结构是数据在计算机中的表示，循环队列在计算机内是顺序存储结构，栈在计算机内可是以顺序也可以是链式。所以循环队列和栈都是线性逻辑结构，不能说循环队列和栈是存储结构，只能说它们在计算机内的存储结构。
1：顺序队列
采用顺序存储结构的队列称为顺序队列，要用一片连续的空间来存储队列的元素。
1.1 顺序队列中各元素的逻辑及存储关系
顺序队列可以采用顺序表作为其存储表示，因此，可以在顺序队列的声明中用顺序表定义它的存储空间。
顺序队列可以使用一维数组作为队列的存储空间，存放队列元素的数组的头指针为*elements，该数组的最大允许存放元素个数为maxSize，当前队列的队头位置由数组下标指针front指示，队尾位置由数组下标指针rear指示，如果队列不为空时elements[0]是队列中第一个元素。
1.2 代码实现
#include <stdio.h>
#include <stdlib.h>
#define
#define
#define
#define
#define
typedef int ElemType;
typedef int Status;
//----- 队列的顺序存储表示 -----
#define// 存储空间的初始分配量
typedef struct {
ElemType *base;
int front;
int rear;
int maxSize;
} SqQueue;
// 构造一个空队列 Q
Status InitQueue(SqQueue &Q) {
Q.base = (ElemType*)malloc(MAXQSIZE * sizeof(ElemType));
if(!Q.base) exit(OVERFLOW);
Q.front = Q.rear=0;
Q.maxSize = MAXQSIZE;
return OK;
}
//判队列是否为空
Status QueueEmpty(SqQueue Q) {
if(Q.rear==Q.front) return TRUE;
else return FALSE;
}
//入队函数
Status EnQueue(SqQueue &Q, ElemType e) {
//请在此填写代码，将该算法补充完整，参见书本和课件相关章节
if((Q.rear+1) % MAXQSIZE == Q.front)//队列已满
return ERROR;
Q.base[Q.rear] = e;//插入队尾
Q.rear = (Q.rear +1) % MAXQSIZE;//尾部指针后移，如果到最后则转到头部
return OK;
}
//出队函数
Status DeQueue(SqQueue &Q, ElemType &e) {
//请在此填写代码，将该算法补充完整，参见书本和课件相关章节
if(Q.front == Q.rear) //队列空
return ERROR;
//返回队头元素
e = Q.base[Q.front];
//队头指针后移，如到最后转到头部
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
//输出循环队列函数
void OutQueue(SqQueue Q) {
ElemType e;
if(QueueEmpty(Q)){
printf("这是一个空队列！");
} else {
while(!QueueEmpty(Q)){
DeQueue(Q,e);
printf("%6d", e);
}
printf("\n");
}
}
//主函数
int main() {
SqQueue q;
int cord;
ElemType a;
printf("第一次使用必须初始化！\n");
//调用初始化算法
InitQueue(q);
do{
printf("\n 主菜单 \n");
printf(" 1 初始化循环队列 ");
printf(" 2 进队一个元素 ");
printf(" 3 出队一个元素 ");
printf(" 4 结束程序运行 ");
printf("\n------------------------------------------------------------------\n");
printf("请输入您的选择( 1, 2, 3, 4)");
scanf("%d", &cord);
printf("\n");
switch(cord) {
case 1:
InitQueue(q); //调用初始化算法;
OutQueue(q);
break;
case 2:
printf("请输入要插入的数据元素：a=");
scanf("%d",&a);
EnQueue (q, a); //调用进队算法;
printf("%d 进队之后的队列：",a);
OutQueue(q);
break;
case 3:
DeQueue (q, a); //调用出队算法;
printf("队头元素 %d 出队之后的队列：",a);
OutQueue(q);
break;
case 4:
exit(0);
}
} while(cord<=4);
return 0;
} 2：顺序栈
采用顺序存储的栈成为顺序栈，需要用一片连续的空间来存储栈的元素。
2.1 代码实现
#include <stdio.h>
#include <stdlib.h>
#define
#define
#define
#define
#define
typedef int ElemType;
typedef int Status;
//----- 栈的顺序存储表示 -----
#define// 存储空间的初始分配量
#define// 存储空间的分配增量
typedef struct{
ElemType *base; //存储空间的基址
int top; //栈顶元素的下一个元素，简称栈顶位标
int size; //当前分配的存储容量，作用看入栈操作就可以知道
int increment; //扩容时，增加的存储容量，作用看入栈操作就可以知道
} SqStack; //顺序栈名称
// 构造一个空栈 S
Status InitStack(SqStack &S) {
S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!S.base) exit(OVERFLOW);
S.top = 0;
S.size = STACK_INIT_SIZE;
S.increment = STACKINCREMENT;
return OK;
}
// 判栈 S 是否为空栈
Status StackEmpty(SqStack S){
if(S.top==0)
return TRUE;
else
return FALSE;
}
//入栈函数
Status Push(SqStack &S, ElemType e) {
//定义中间变量
ElemType *newbase;
//S.top如果指向最后一个不存储元素的地址时，即S.top大于
if (S.top>= S.size) {
//等于S.size时，就表示栈满了 //通过realloc动态扩容
newbase = (ElemType*)realloc(S.base,
(S.size + S.increment) * sizeof(ElemType));
//判断扩容是否成功
if (NULL == newbase) return OVERFLOW;
//扩容成功后才将中间变量的值指向S.elem，防止扩容失败时，
S.base = newbase;
//S.elem指向一个不是原来的位置
S.size += S.increment;
}
//将e元素入栈; 使S.top加1，表示指向的是栈顶位标
S.base[S.top++] = e;
//上面操作正常后返回1
return OK;
}
//出栈函数; 栈顶元素出栈，赋给元素e
Status Pop(SqStack &S, ElemType &e) {
//请在此填写代码，将该算法补充完整，参见课本和课件相关章节
if ( 0 == S.top) return ERROR;
//e出栈，并将S.top减1
e = S.base[--S.top];
return OK;
}
//输出顺序栈函数
void OutStack(SqStack S) {
ElemType e;
if(TRUE == StackEmpty(S)) {
printf("这是一个空栈！");
} else
while(FALSE == StackEmpty(S)){
Pop(S, e);
printf("%6d", e);
}
printf("\n");
}
//主函数
int main() {
SqStack s;
int cord; ElemType a;
printf("第一次使用必须初始化！\n");
do {
printf("\n 主菜单 \n");
printf(" 1 初始化顺序栈 ");
printf(" 2 插入一个元素 ");
printf(" 3 删除栈顶元素 ");
printf(" 4 结束程序运行 ");
printf("\n-------------------------------------------------------------------\n");
printf("请输入您的选择( 1, 2, 3, 4)");
scanf("%d",&cord);
printf("\n");
switch(cord) {
case 1:
InitStack(s);
OutStack(s);
break;
case 2:
printf("请输入要插入的数据元素：a=");
scanf("%d",&a);
Push(s, a);
printf("%d 进栈之后的栈：",a);
OutStack(s);
break;
case 3:
Pop(s, a);
printf("栈顶元素 %d 出栈之后的栈：",a);
OutStack(s);
break;
case 4:
exit(0);
}
} while (cord <= 4);
return 0;
} 四． 实验结果及分析
4.1 顺序队列
4.1.1 运行截图
![开源按键组件Multi_Button的使用,含测试工程[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)