数据结构栈.ppt
数数 据据 结结 构构 测测 绘绘 学学 院院数数 据据 结结 构构 测测 绘绘 学学 院院二、教学要求：二、教学要求：1 1、掌握栈和队列的定义、特性，并能正确应用它、掌握栈和队列的定义、特性，并能正确应用它们解决实际问题；们解决实际问题；2 2、熟练掌握栈的顺序表示、链表表示以及相应操、熟练掌握栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件；作的实现。特别注意栈空和栈满的条件；3 3、熟练掌握队列的顺序表示、链表表示以及相应、熟练掌握队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针操作的实现。特别是循环队列中队头与队尾指针的变化情况的变化情况数数 据据 结结 构构 测测 绘绘 学学 院院栈和队列是两种特殊的线性表，是栈和队列是两种特殊的线性表，是的线性表，称限定性数据结构。的线性表，称限定性数据结构。 队列的应用队列的应用数数 据据 结结 构构 测测 绘绘 学学 院院3.1 栈（栈（stack）一、一、 栈的定义：限定仅在栈的定义：限定仅在表尾表尾进行插入或删除操进行插入或删除操作的线性表，表尾作的线性表，表尾栈顶栈顶，表头，表头栈底栈底，不含元，不含元素的空表称空栈素的空表称空栈 特点：先进后出（特点：先进后出（FILO）或后进先出（或后进先出（LIFO）ana1a2.栈底栈底栈栈顶顶.出栈出栈进栈进栈栈栈s=(a1,a2,an)数数 据据 结结 构构 测测 绘绘 学学 院院栈的特点栈的特点根据栈的定义可知，最先放入栈中元素在栈底，根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后最后放入的元素最先删除，最先放入的元素最后删除。删除。也就是说，栈是一种也就是说，栈是一种后进先出后进先出(Last In First Out)的线性表，简称为的线性表，简称为LIFO表。表。 stack数数 据据 结结 构构 测测 绘绘 学学 院院栈的基本操作栈的基本操作1.初始化栈：初始化栈：INISTACK(&S)将栈将栈S置为一个空栈置为一个空栈(不含任何元素不含任何元素)。2.进栈：进栈：PUSH(&S,X)将元素将元素X插入到栈插入到栈S中，也称为中，也称为 “入栈入栈”、 “插入插入”、 “压入压入”。3.出栈：出栈： POP(&S) 删除栈删除栈S中的栈顶元素，也称为中的栈顶元素，也称为”退栈退栈”、 “删除删除”、 “弹出弹出”。4.取栈顶元素：取栈顶元素： GETTOP(S,&e)取栈取栈S中栈顶元素。中栈顶元素。5.判栈空：判栈空： StackEmpty(S)判断栈判断栈S是否为空，若为空，返回值为是否为空，若为空，返回值为true，否则返回值为，否则返回值为false。数数 据据 结结 构构 测测 绘绘 学学 院院例例1：对于一个栈，给出输入项对于一个栈，给出输入项A、B、C，如果输入项序列，如果输入项序列由由ABC组成，试给出所有可能的输出序列。组成，试给出所有可能的输出序列。A进进 A出出 B进进 B出出 C进进 C出出 ABCA进进 A出出 B进进 C进进 C出出 B出出 ACBA进进 B进进 B出出 A出出 C进进 C出出 BACA进进 B进进 B出出 C进进 C出出 A出出 BCAA进进 B进进 C进进 C出出 B出出 A出出 CBA不可能产生输出序列不可能产生输出序列CAB数数 据据 结结 构构 测测 绘绘 学学 院院 43512不可能实现，主要是其中的不可能实现，主要是其中的12顺序不能顺序不能实现；实现； 12345的输出可以实现，只需压入一个立即弹的输出可以实现，只需压入一个立即弹出一个即可。出一个即可。 435612中到了中到了12顺序不能实现；顺序不能实现； 135426可以实现。可以实现。例例3：如果一个栈的输入序列为：如果一个栈的输入序列为123456，能否得，能否得到到435612和和135426的出栈序列？的出栈序列？答：答：答：答：数数 据据 结结 构构 测测 绘绘 学学 院院设依次进入一个栈的元素序列为设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：则可得到出栈的元素序列是： A、D可以（可以（ B、C不行）。不行）。答：答：数数 据据 结结 构构 测测 绘绘 学学 院院二、二、 顺序栈顺序栈 由于栈是运算受限的线性表，因此线性表的存储由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量操作而变化的，故需用一个整型变量top来指示当前来指示当前栈顶的位置，通常称栈顶的位置，通常称top为栈顶指针。为栈顶指针。数数 据据 结结 构构 测测 绘绘 学学 院院因此，顺序栈的类型定义只需将顺序表的类因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为型定义中的长度属性改为top即可。顺序栈即可。顺序栈的类型定义如下（的类型定义如下（静态）静态） # define StackSize 100 typedef struct ElemType dataStackSize; int top; SeqStack; 数数 据据 结结 构构 测测 绘绘 学学 院院/- 栈的顺序存储表示栈的顺序存储表示 -（动态） #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;数数 据据 结结 构构 测测 绘绘 学学 院院top=0123450栈空栈空栈顶指针栈顶指针top,指向实际栈顶指向实际栈顶后的空位置，初值为后的空位置，初值为0top123450进栈进栈Atop出栈出栈栈满栈满BCDEF设数组维数为设数组维数为Mtop=0,栈空，此时出栈，则栈空，此时出栈，则下溢下溢（underflow)top=M,栈满，此时入栈，则栈满，此时入栈，则上溢上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈空栈顶栈顶top 的值为下一个将要进栈的元素下标。的值为下一个将要进栈的元素下标。数数 据据 结结 构构 测测 绘绘 学学 院院 设设S S是是SeqStackSeqStack类型的指针变量。若栈底位置在向类型的指针变量。若栈底位置在向量的低端，即量的低端，即s sdata0data0是栈底元素，那么栈顶指针是栈底元素，那么栈顶指针s stoptop是正向增加的，即进栈时需将是正向增加的，即进栈时需将s stoptop加加1 1，退，退栈时需将栈时需将s stop top 减减1 1。 因此，因此，s stop=0top=0表示空栈，表示空栈， s stop =stacksizetop =stacksize表示栈满。当栈满时再做进栈运算必定产生空间溢出表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称，简称“上溢上溢”; ;当栈空时再做退栈运算也将产生溢当栈空时再做退栈运算也将产生溢出，简称出，简称“下溢下溢”。上溢是一种出错状态，应该设法。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。为程序控制转移的条件。数数 据据 结结 构构 测测 绘绘 学学 院院1 1、置空栈、置空栈 void initstack(seqstack void initstack(seqstack * *s)s) s stop=0;top=0; 2 2、判断栈空、判断栈空 int stackempty(seqstack int stackempty(seqstack * *s)s) return(s return(stop=0);top=0); 数数 据据 结结 构构 测测 绘绘 学学 院院3、判断栈满、判断栈满 int stackfull(seqstack *s) return(stop=stacksize); 4、进栈、进栈 void push(seqstack *s，ElemType x) if (stackfull(s) error(“stack overflow”); sdatastop+=x; 数数 据据 结结 构构 测测 绘绘 学学 院院5 5、退栈、退栈 void pop(seqstack void pop(seqstack * *s,ElemType s,ElemType * *x)x) if(stackempty(s) if(stackempty(s) error( error(“stack underflowstack underflow”);); s stop-;top-; * *x=sx=sdatatop;datatop; 数数 据据 结结 构构 测测 绘绘 学学 院院6 6、取栈顶元素、取栈顶元素 ElemType stacktop(seqstack *s) if(stackempty(s) error(“stack is empty”); return sdatastop-1; 数数 据据 结结 构构 测测 绘绘 学学 院院3.1.3 链栈链栈 栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表可以没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 链栈的类型说明如下： 数数 据据 结结 构构 测测 绘绘 学学 院院栈的链接存储结构链栈的结点定义链栈的结点定义typedef struct node ElemType data; struct node *next; LinkStack; 数数 据据 结结 构构 测测 绘绘 学学 院院栈的链接表示 链式栈 链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作数数 据据 结结 构构 测测 绘绘 学学 院院在链栈中在链栈中,栈的基本运算算法如下栈的基本运算算法如下: (1)初始化栈初始化栈initStack(&L) 建立一个空栈建立一个空栈L。实际上是创建链栈的头结点。实际上是创建链栈的头结点,并将其并将其next域置为域置为NULL。对应算法如下。对应算法如下: void InitStack(ListStack *&L) L=(ListStack *)malloc(sizeof(ListStack);L-next=NULL; 数数 据据 结结 构构 测测 绘绘 学学 院院 (2)销毁栈销毁栈ClearStack(&L) 释放栈释放栈L L占用的全部存储空间。对应算法如下占用的全部存储空间。对应算法如下: : void ClearStack(ListStack *&L) ListStack *p=L-next;while (p!=NULL)free(L);L=p;p=p-next; 数数 据据 结结 构构 测测 绘绘 学学 院院 ( (3)求栈的长度求栈的长度StackLength(L) 从第一个数据结点开始扫描单链表从第一个数据结点开始扫描单链表,用用i记录访问的记录访问的数据结点个数数据结点个数,最后返回最后返回i值。对应算法如下值。对应算法如下: int StackLength(ListSta
