实验三栈和队列的算法实现指导书(栈).doc

实验三 栈和队列的算法实现(栈)一、实验目的1.掌握栈这种数据结构特性及其主要存储结构。2.掌握栈的基本操作算法。二实验指导（1）程序的三部分构架：1、常量定义（#define），类型定义(typedef)及函数原型定义(#include)；2、算法函数，即InitStack、StackEmpty、Push和Pop、等3、主函数。（2）栈的顺序存储结构typedef struct ElemType aMAXSIZE; /* 一维数组子域 */ int top; /* 栈顶指针子域 */ SqStack; /* 栈的顺序结构体类型 */（3）栈的特点：后进先出（4）在实例中，判栈空条件：s.top=-1；判栈满条件：s.top=MAXSIZE-1；进栈操作：先加后压；出栈操作：先弹后减。三、实例栈的顺序存储结构及实现（代码）#include #include #define MAXSIZE 20 /* 数组最大界限 */typedef int ElemType; /* 数据元素类型 */typedef struct ElemType aMAXSIZE; /* 一维数组子域 */ int top; /* 栈顶指针子域 */ SqStack; /* 栈的顺序结构体类型 */SqStack s1;/* 函数声明 */void init_s(SqStack *s);void out_s(SqStack s);void push(SqStack *s,ElemType e);/ElemType pop(SqStack *s);/* 主函数 */Void main() int k; ElemType e; char ch; init_s( &s1); /* 初始化一个空栈 */ do printf(nnn); printf(nn 1. 数据元素e进栈 ); printf(nn 2. 出栈一个元素，返回其值)； printf(nn 3. 结束程序运行); printf(n=); printf(n 请输入您的选择 (1,2,3); scanf(%d,&k); switch(k) case 1: printf(n 进栈 e=?); scanf(%d,&e); push( &s1,e); out_s( s1 ); break; / case 2: x= pop( &s1); / printf(n出栈元素 : %d, x); / out_s( s1 ); / break; case 3: exit(0); /* switch */ printf(n -); while(k=1 & ktop=-1; /* init_s */* 输出栈的内容 */void out_s(SqStack s) char ch; int i; /* 千万不能修改栈顶指针top */ if (s.top=-1) printf(“n Stack is NULL. “); else i=s.top; while( i!=-1) printf(“n data=%d”, s.ai); i-; printf(“n 打回车键，继续。“); ch=getchar(); /* out_c */* 进栈函数 */void push(SqStack *s,ElemType e) if(s-top=MAXSIZE-1)printf(“n Sstack is Overflow!”); else s-top+ ; s-as-top=e; /* push */四、实验内容与要求实例中给出了栈的顺序存储结构上的栈初始化、压栈及输出栈元素等基本操作，并给出了测试函数（主函数）。现要求：1.验证以上基本操作；2.设计出栈函数pop(SqSt