栈的定义及顺序存储

1、栈的定义、顺序存储栈的定义、顺序存储第七节段第七节段数据结构1一一【创设情境创设情境】 压入子弹，射出子弹的特点？ 羽毛球筒取放羽毛球特点？2一一【引入新课引入新课】操作受限：只可在一端进行；最后放进去的子弹最先射出来。栈栈3进制转化问题进制转化问题(14)10=( ？ )21110一一【任务驱动、学习知识任务驱动、学习知识】思考思考：1.转化方法？2.数据存储、输出实现？41 12 23 3栈的栈的定义定义栈的栈的存储存储栈的应用栈的应用目目 录录5一一一一. .栈的定义栈的定义思考思考：1.进栈、出栈相当于顺序表？2.时间复杂度？(1)回答：回答：顺序表表尾操作FlashFlash演示演示

2、6一一一一. .栈的定义栈的定义栈栈是一种限制仅在一端进行插入和删除的线性表栈顶栈顶进行插入、删除栈顶top栈底bottoma2a1an出栈 进栈n-1107一一一一. .栈的定义栈的定义先进后出先进后出(FILO)(FILO)后进先出后进先出(LIFO)(LIFO)1. 若进栈序列为1,2,3,4,进栈过程中可以出栈，则不可能是一个出栈序列（ ）。A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4特点特点【随堂练习随堂练习】C8一一二二. .栈的存储栈的存储 思考：思考：线性表的存储方式？ 栈的存储：栈的存储：链栈顺序栈9(1)(1)顺序栈类定义（顺序栈类

3、定义（p41p41）：）： privateprivate： int stacklistMaxStackSize;int stacklistMaxStackSize; int top; int top; public public： 各种运算的成员函数各种运算的成员函数；讨论讨论1 1：1.哪些运算？一一二二. .栈的存储栈的存储10栈空时栈满时栈顶元素栈空时，执行pop栈满时，执行push一一二二. .栈的存储栈的存储【顺序栈顺序栈】讨论讨论2 2：top=-1top=MaxStackSize-1Stop产生“下溢”产生“上溢”如何解决？如何解决？11定义足够大空间的顺序栈“共享共享栈栈”思想

4、思想一一二二. .栈的存储栈的存储0M-1Top0Top1可能浪费链式存储FlashFlash演示演示12一一三三. .栈的应用栈的应用【解决任务解决任务】(14)10=( ？ )2进制转换进制转换算法思想：算法思想：当N0时，重复（1），（2）(1) (1) 若若Num0Num0，则将，则将Num%RNum%R压入栈压入栈s s中，执行中，执行(2)(2)； 若若Num=0Num=0，将栈，将栈s s的内容依次出栈，算法结束。的内容依次出栈，算法结束。(2) (2) 用用Num/RNum/R代替代替NumNum。 13#include “seqstack.h”Void Multibaseou

5、tput(long num,int R) Seqstack s; do s.push(num%R); num/=R; while(num!=0); while(!s. StackEmpty() couts.Pop(); /主函数主函数Void main() long num; int R;coutnumR;coutnum“的”R“进制是:”;Multibaseoutput(num,R);Coutendl;14一一【作业布置作业布置】数制转换括号匹配的检验行编辑程序1.请用C/C+写出进制转换算法，并运行十进制数1348的八进制，截屏保存。【课外扩充课外扩充】栈的应用栈的应用迷宫问题表达式求值递归