数据结构（C语言版）程海英-上机3.docVIP

上机3 栈与队列的应用 1.问题描述 栈是限制为仅仅能在表的一端插人和删除的线性表，是生活中某些过程的抽象。 插人删除的一端称为栈顶(top)，插人操作通常称为进栈或者人栈( push)。不能插人删除的一端称为栈底(bottom) ，删除操作通常称为出栈或者退栈( pop )。栈有着后进先出(List In First Out-LIFO)的特性，也称为后进先出表。使用顺序来表示一个栈。 2.数据结构设计 define MaxSize 100 //最大元素个数 typedef struct { //顺序栈的类型定义 ElemType data[MaxSize]; //栈元素存储空间 int top; //栈顶指针 }SeqStack; 顺序循环队列的数据类型： #define MaxSize 100 //最大元素个数 typedef struct { //循环顺序队的类型定义 ElemType data[MaxSize]; //队列元素存储空间 int front; //队头指针 int rear; //队尾指针 }CircSeqQueue; 3.函数说明 顺序的基本操作 Stackinitial(SeqStack *pS) //创建一个由指针pS所指向的空顺序栈 isEmpty(SeqStack *pS) //顺序栈为空时返回 isFull(SeqStack *pS) //栈满时返回 Push(SeqStack *pS,ElemType e) //若栈不满，则元素e进栈 Pop(SeqStack *pS) //若栈不为空，则删除找顶元素，并返回它的值 GetTop(SeqStack *pS) //若栈不为空，则返回栈顶元素的值 MakeEmpty(SeqStack *pS) //将由指针pS所指向的栈置空 循环顺序队基本操作： QueueInitial(CircSeqQueue *pQ) //创建一个由指针pQ所指向的空队列 isEmpty(CircSeqQueue *pQ) //循环顺序队为空时返回1，否则返回0 isFull(CircSeqQueue *pQ) //循环队列为满时返回1，否则返回0 EnQueue(CircSeqQueue*pQ,ElemType e) //若队列不满，则元素e进队 DeQueue(CircSeqQueue *pQ) //若循环队列不空，删除队头元素，返回它的值 GetFront(CircSeqQueue *pQ) //若队列不为空，则返回队头元素的值 MakeEmpty(CircSeqQueue *pQ) //将由指针pQ所指向的队列变为空队 4.编码实现 #include stdio.h #include iostream.h include malloc.h #includeprocess.h #define MaxSize 100 //最大元素个数 typedef int ElemType; typedef struct { //顺序栈的类型定义 ElemType data[MaxSize]; //栈元素存储空间 int top; //栈顶指针 }SeqStack; typedef struct { //循环顺序队的类型定义 ElemType data[MaxSize]; //队列元素存储空间 int front; //队头指针 int rear; //队尾指针 }CircSeqQueue; void StackInitial(SeqStack *pS){ //创建一个由指针pS所指向的空栈 pS-top= -1; } int isEmpty(SeqStack *pS){ //顺序栈为空时返回1，否则返回。 return pS-top== -1; } int isFull (SeqStack * pS){ //栈为满时返回1，否则返回0 return pS-top =MaxSize-1; } void Push(SeqStack *pS, ElemType e){ //若栈不满，则元素e进栈 if (isFull (pS)) { //栈已满，退出 printf(栈满溢出！\n); return; } pS-data[++pS-top]=e; } ElemType Pop(SeqStack *pS){ //若栈不为空，则删除栈顶元素，并返回它的值 if(isEmpty(p