实验二栈、队列的实现及应用讲解

实验二 栈、队列的实现及应用

实验课程名：数据结构与算法

专业班级： 学号： 姓名：

实验时间： 实验地点： 指导教师： 冯珊 一、实验目的 1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。 二、实验内容 一、实验目的及要求 1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。 二、实验学时 2学时 三、实验任务 任务一：（1）实现栈的顺序存储（2）实现栈的链式存储。 任务二：实现顺序存储的循环队列，完成键盘缓冲区的功能。 四、实验重点、难点 1. 进栈、出栈栈顶指针都要改变。 2. 队空、队满的条件及入队、出队时指针的变更。 五、操作内容与要求 1.任务一（1）：完成下列程序，该程序实现栈的顺序存储结构，构建顺序栈（栈中的元素依次为R，S，Y，F，C，T），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。要求生成顺序栈时，从键盘上读取数据元素。 （1）源代码：#include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 # define OK 1 # define ERROR 0 typedef char SElemType; /* 顺序栈的存储类型 */ typedef struct { SElemType *base; SElemType *top; int stacksize; //define structure SqStack() }SqStack;

/*构造空顺序栈*/

int InitStack(SqStack *S) //InitStack() sub-function {

/*取顺序栈顶元素*/

int GetTop(SqStack *S, SElemType *e) {

/*将元素压入顺序栈*/

int Push(SqStack *S) //Push() sub-function {

SElemType e;

if (S->top - S->base>S->stacksize) { }

fflush(stdin);//清除输入缓冲区，否则原来的输入会默认送给变量x

S->base = (SElemType *)realloc(S->base, (S->stacksize + { }

S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT;

printf(\存储空间分配失败!\\n\); return (ERROR);

STACKINCREMENT*sizeof(SElemType))); if (!S->base) if (S->top == S->base) { }

*e = *(S->top - 1); return (OK);

printf(\栈为空!\\n\); //if empty SqStack return (ERROR);

//GetTop() sub-function

S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if (!S->base) { }

S->top = S->base;

S->stacksize = STACK_INIT_SIZE; printf(\栈初始化成功！\\n\); return (OK);

printf(\分配空间失败!\\n\); return (ERROR);

} //InitStack() end

} //GetTop() end

printf(\请输入要入栈的元素的值:\); e = getchar(); *S->top++ = e; return (OK);

} //Push() end /* 将元素弹出顺序栈*/

int Pop(SqStack *S, SElemType *e) //Pop() sub-function {

if (S->top == S->base) { }

*e = *--S->top; return (OK);

printf(\栈为空!\\n\); return (ERROR);

} //Pop() end

void display(SqStack *s) { }

int main() {

int choice; SElemType e; SqStack s; do {

printf(\); printf(\退出\\n\); printf(\初始化栈\\n\); printf(\入栈\\n\); printf(\出栈\\n\);

printf(\读取栈顶元素\\n\); printf(\显示栈中元素\\n\); if (s->top == s->base) }

printf(\);

printf(\栈为空!\\n\); while (s->top != s->base) { }

s->top = s->top - 1; printf(\, *(s->top));

else{