栈PPT

栈主讲人：栈6栈世上电梯有哪几种？先进先出分为：先进先出和先进后出两种电梯。先进后出栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除栈一、栈的定义栈的图示栈的特点先进后出(FILO)第1个进栈的元素在栈底，最后一个进栈的元素在栈顶，第1个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素栈栈的示意图a1a2…an栈底栈顶顺序栈栈1、定义栈的顺序存贮结构也称为顺序栈。栈的顺序存储结构，就是利用一组连续的内存单元依次存放自栈底到栈顶的数据元素，栈顶元素的位置，由一个称为栈顶指针的变量指示。栈图示栈顶栈底ana2a1顺序栈栈#defineMaxsize100/*设顺序栈的最大长度为100/typedefstruct{datatypedata[Maxsize];inttop；/*栈顶指针*/}SeqStack；/*顺序栈类型定义*/2、顺序栈存储结构的描述栈栈（1）初始化操作InitStack(S)（2）入栈操作PUSH(S，x)（3）出栈操作POP(S)3、顺序栈的基本操作（5）判空操作StackEmpty(S)（4）取栈顶元素GetTop(S)42103a4a3a2a1a2a1a5a4a3a2a1toptoptoptop（a）top=-1栈空顺序栈操作示意图（b）a1a2a3a4依次入栈（c）a4a3依次出栈42103（d）top=Maxsize-1栈满栈栈链栈1、定义栈的链接存贮结构也称为链栈。栈的链式存储结构，就是用链表作为栈的存储结构，即用指针来实现栈。用这种方式实现的栈也称为链栈。图示链栈栈顶栈底topanan-1a1∧firsta1a2an∧ai两种示意图在内存中对应同一种状态topa1an-1an∧栈顶栈底栈有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有哪些种？栈底栈顶ab栈顶c栈顶情况1：栈有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有哪些种？栈底栈顶ab栈顶c栈顶出栈序列：c出栈序列：c、b出栈序列：c、b、a情况1：栈有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有哪些种？栈底栈顶a情况2：出栈序列：a栈有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有哪些种？栈底栈顶b情况2：出栈序列：a出栈序列：a、b栈有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有哪些种？栈底栈顶c情况2：出栈序列：a出栈序列：a、b出栈序列：a、b、c上面的题目，除了课堂上讲过的几种出栈序列，还有哪种出栈方式？本堂小结：一、回顾栈的特性三、入栈和出栈的算法二、栈的定义