《九江学院《数据结构》第03章 栈与队列》由会员分享，可在线阅读，更多相关《九江学院《数据结构》第03章 栈与队列（74页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈和队列,3.1 栈3.2 栈的应用举例3.3 队列,3.1.1 栈的定义 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom).当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。,3.1 栈,栈：限定只能在表的一端进行插入和删除的特殊的线性表. 设栈s=（a1，a2，. . . ,ai，. . . ，an
2、），其中a1是栈底元素， an是栈顶元素。栈顶（top)：允许插入和删除的一端； 栈顶的当前位置由栈顶指针的位置指示器指示。栈底（bottom):不允许插入和删除的一端。进栈或入栈：栈的插入操作。出栈或退栈：栈的删除操作。,3.1.1 栈的定义,空栈：没有元素的栈栈的特性：先进后出（LIFO），即只能在末端（栈顶）进行插、删的操作,3.1.1 栈的定义,例：一叠书或一叠盘子。,栈顶,栈底,3.1.1 栈的定义,栈中的几种基本操作： 1.设置空栈 初始化：initStack(S); 清空：emptyStack (S); 2.插入一个新的栈顶元素（进栈）:push(S,x); 3.删除栈顶元素（出
3、栈）: pop(S); 4.读取栈顶元素:getTop(S); 5.判空栈:stackEmpty(S); 6.判满栈:stackFull(S); 7.显示栈中元素：stackTraverse(S);,3.1.1 栈的定义,栈的存储结构,顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，一般用一维数组表示必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置链栈采用链表作为存储结构实现的必须设置一个栈顶指针永远指向栈顶,3.1.2 栈的表示和实现,一、顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的
4、线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的,所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的。,3.1.2 栈的表示和实现,需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。,一、顺序栈,顺序栈的结构#define Stack_Size 50typedef structStackElemType elemStack_Size; /*用一维数组存放自栈底到栈顶的数据元素*/ int top; /*附设一个位置指针top*/SeqStack;,一、顺序栈
5、,设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即selem0是栈底元素. 那么： 进栈：stop加1；退栈：stop 减1； 空栈：stoptop =stacksize-1。 上溢：当栈满时再做进栈运算必定产生的空间溢出;下溢：当栈空时再做退栈运算产生的溢出。 上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。,一、顺序栈,设数组S是一个顺序栈栈S的最大容量stacksize=4 ，初始状态top=1,栈空,10进栈,30出栈,栈满,top=stacksize-1,进栈算法#defin
6、e Statck_Size 100int Push(SeqStack *S, int x), if(S-top=Stack_Size1) return 0; S-top+; S-elemS-top=x; return(1);,a2,a3,a4,9,8,7,6,5,4,3,2,1,a1,0,top,一、顺序栈,进栈算法#define Statck_Size 100int Push(SeqStack *S, int x), if(S-top=Stack_Size1) return(0); S-top+; S-elemS-top=x; return(1);,a2,a3,a4,9,8,7,6,5,4,
7、3,2,1,a1,0,top,一、顺序栈,进栈算法#define Statck_Size 100int Push(SeqStack *S, int x), if(S-top=Stack_Size1) return(0); S-top+; S-elemS-top=x; return(1);,a2,a3,a4,9,8,7,6,5,4,3,2,1,a1,0,top,x,一、顺序栈,出栈算法： int pop(SeqStack *S, StackElementType *x), if(S-top= =1) printf(“stack empty”); return(0); else *x=S-elem
8、S-top; /*返回出栈元素*/ S-top- -; return(1); ,通过指针变量x，带回出栈元素,a2,a3,a4,9,8,7,6,5,4,3,2,1,a1,0,top,一、顺序栈,a2,a3,a4,9,8,7,6,5,4,3,2,1,a1,0,top,x,出栈算法： int pop(SeqStack *S, StackElementType *x), if(S-top= =1) printf(“stack empty”); return(0); else *x=S-elemS-top; /*返回出栈元素*/ S-top- -; return(1); ,一、顺序栈,顺序栈的共享,为
9、两个栈申请一个共享的一维数组空间SM将两个栈的栈底分别放在一维数组的两端，分别是0，M1,一、顺序栈,共享栈的结构定义,#define M 100typedef structStackElementType elemM; int top2;DqStack;,一、顺序栈,共享栈的操作,判空：top0=-1;top1=M;判满：top0+1= =top1;,一、顺序栈,共享栈的进栈操作,int Push(DqStack *S,StackElementType x,int i)if(S-top0+1= =S-top1) return(0); switch(i) case 0: S-top0+; S-
10、elemS-top0=x; break; case 1: S-top1+; S-elemS-top1=x; break; default: return(0); return(1);,共享栈的出栈操作,int Pop(DqStack *S,StackElementType *x,int i)switch(i) case 0: if(S-top0= =-1) return(0); *x=S-elemS-top0; S-top0- -; break; case 1: if(S-top1= =M) return(0); *x=S-elemS-top1; S-top1- -; break; defau
11、lt: return(0); return(1);,二、链栈 栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。,3.1.2 栈的表示和实现,top,栈底,用指针来实现的栈叫链栈。栈的容量事先不能估计时采用这种存储结构。,链栈的类型说明如下：typedef struct Lnode int data； struct Lnode next； Lnode，LinkStack；,top头指针永远指向头结点,二、链栈,进栈算法int Push(LinkStack top, S
12、tackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1);,base,top,栈 s,进栈元素e,二、链栈,进栈算法int Push(LinkStack top, StackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1);,base,top,二、链栈,进栈算法i
13、nt Push(LinkStack top, StackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1);,base,top,二、链栈,进栈算法int Push(LinkStack top, StackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1);,base,
14、top,进栈算法int Push(LinkStack top, StackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1);,base,top,二、链栈,出栈算法int Pop(LinkStack top, StackElementType *x)Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=temp-data; free(temp);,
