实验二 栈和队列
1、实验目的：
（1） 熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作
在栈的顺序存储结构和链式存储结构上的实现；
（2） 熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基
本操作在队列的顺序存储结构和链式存储结构上的实现。
2、实验要求：
（1） 复习课本中有关栈和队列的知识；
（2） 用C语言完成算法和程序设计并上机调试通过；
（3） 撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括
时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。
3、实验内容
[实验1] 栈的顺序表示和实现
实验内容与要求:
编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化顺序栈 （2）插入元素 （3）删除栈顶元素 （4）取栈顶元素 （5）遍历顺序栈 （6）置空顺序栈 分析:
栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。
出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。 注意：
（1）顺序栈中元素用向量存放
（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点 （3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置 #include
typedef int SElemType; typedef int Status;
#define INIT_SIZE 100
1
#define STACKINCREMENT 10 #define Ok 1 #define Error 0 #define True 1 #define False 0 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack;
//初始化栈
Status InitStack(SqStack *s) { s->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType)); if(!s->base) { puts(\存储空间分配失败！\ return Error; } s->top = s->base; s->stacksize = INIT_SIZE; return Ok; }
//清空栈
Status ClearStack(SqStack *s) {
s->top = s->base; return Ok; }
//栈是否为空
Status StackEmpty(SqStack *s) {
if(s->top == s->base) return True; else
return False; }
//销毁栈
Status Destroy(SqStack *s)
2
{ free(s->base); s->base = NULL; s->top = NULL; s->stacksize=0; return Ok; }
//获得栈顶元素
Status GetTop(SqStack *s, SElemType &e) { if(s->top == s->base) return Error; e = *(s->top - 1); return Ok; }
//压栈
Status Push(SqStack *s, SElemType e) { if(s->top - s->base >= s->stacksize) { s->base = (SElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElemType)); if(!s->base) { puts(\存储空间分配失败！\ return Error; } s->top = s->base + s->stacksize; s->stacksize += STACKINCREMENT; } *s->top++ = e; return Ok; }
//弹栈
Status Pop(SqStack *s, SElemType *e) { if(s->top == s->base) return Error; --s->top; *e = *(s->top); return Ok; }
3
//遍历栈
Status StackTraverse(SqStack *s,Status(*visit)(SElemType)) {
SElemType *b = s->base; SElemType *t = s->top; while(t > b) visit(*b++); printf(\ return Ok; }
Status visit(SElemType c) {
printf(\ return Ok; }
int main() { SqStack a; SqStack *s = &a; SElemType e; InitStack(s); int n; puts(\请输入要进栈的个数：\ scanf(\ while(n--) { int m; scanf(\ Push(s, m); } StackTraverse(s, visit); puts(\ Pop(s, &e); printf(\ printf(\ Destroy(s); return 0; }
4
[实验2] 栈的链式表示和实现
实验内容与要求:
编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能： （1）初始化链栈 （2）链栈置空 （3）入栈 （4）出栈
（5）取栈顶元素 （6）遍历链栈
分析:
链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。 注意：
（1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身
（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。 （3）链栈中的结点是动态分配的，所以可以不考虑上溢。 #include
#define ERROR 0 #define OK 1 #define TRUE 1 #define FALSE 0 typedef int ElemType; typedef int Status;
typedef struct node { ElemType data; struct node *next; }StackNode;
typedef struct { StackNode *top; }LinkStack;
//初始化
void InitStack(LinkStack *s) { s->top = NULL; puts(\链栈初始化完成！\}
5