高中二年级下学期信息科技《用栈组织后进先出数据》教学课件

选择性必修1《数据与数据结构》3.4用栈组织后进先出数据|一、栈Stack|栈Stack|队列对应了生活中的排队现象但还有另一种现象，如对一叠碗的取放：每次把洗净的碗放好时总是放在这叠碗的最上面，而每次取用的时候也总是取最上面的。在这种现象中，事物的进出顺序都有共同的特征，那就是后进先出。|栈(Stack)是限制只能在一端进行插入和删除的特殊线性表。栈中能进行插入和删除的一端称为栈顶(Top)，而另一固定端称为栈底(Bottom)。把一个数据元素放入栈中的操作叫作进栈或压栈(Push)，从栈中取出一个数据元素的操作称为出栈或弹出(Pop)。栈中没有元素时，称为空栈。栈的形式在日常生活中经常出现，如一叠书、一叠盘子，如果规定取书、取盘子或放入书、放入盘子都只能在顶部进行，则它就是一个栈。栈的特性：后放入栈中的数据元素首先取出。故栈又被称为后进先出(LIFO:LastInFirstOut)线性表。栈Stack建立数据模型|栈{

栈元素（一定数量的购物车编号）；

栈顶（即将出栈的购物车的位置）；

栈底（即堆在最底的购物车的位置）；}栈的基本操作；二、栈的基本操作Basicoperationofstack|栈的基本操作|栈的常用基本操作有以下几种：（1）初始化栈：构造一个空栈，初始化栈顶标志。（2）元素入栈：若栈非满，栈顶标志上移一位，插入一个元素到栈顶标志指向的位置，该元素成为新的栈顶元素。（3）元素出栈：删除栈顶标志指向的栈顶元素，栈顶标志下移一位，若此时栈非空，则栈顶标志指向的元素成为新的栈顶元素。（4）栈空判断：判断栈是否为空。（5）栈满判断：判断栈是否为满。（6）栈的长度：求栈的元素个数。栈的基本操作|352栈顶一种“后进先出”的结构加入一个数4取出栈顶元素再取出栈顶元素6入栈：top++;a[top]=x;出栈：x=a[top];top--;三、顺序栈的实现Implementationofsequentialstack|顺序栈的实现栈的存储也可采用顺序存储结构的方法来实现，采用顺序存储结构的栈称为顺序栈利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时设置指针top来动态地指示栈顶元素的当前位置。顺序栈的实现|

初始化栈voidInitStack(Stack&st){q.top=-1;//把栈顶指针置为-1}顺序队列的操作代码|

将元素x进栈，元素进栈成功返回true，否则返回false。入栈操作boolPushStack(Stack&st,stringx){if(st.top==maxsize-1)returnfalse;//栈满不能插入元素，返回falseelse{ st.top++; st.item[st.top]=x; returntrue;//成功将元素入栈，返回true }}顺序队列的操作代码|

将st的栈顶元素出栈，出栈元素存放在x中，出栈成功返回true，否则返回false。出栈操作boolPopStack(Stack&st,stringx){if(st.top==-1)returnfalse;//栈空不能出栈，返回falseelse{x=st.item[st.top];st.top--;returntrue;//成功将元素出栈，返回true }}顺序队列的操作代码|

若栈st为空栈，则返回true，否则返回false。栈空判断boolEmptyStack(Stack&st){if(st.top==-1)returntrue; elsereturnfalse; }顺序队列的操作代码|

若栈st为满栈，则返回true，否则返回false。栈满判断boolFullStack(Stack&st){if(st.top==maxsize-1)returntrue; elsereturnfalse; }顺序队列的操作代码|intStackLength(Stack&st){returnst.top+1; }

返回栈中当前元素的个数。栈的长度练习题目①若已知一个栈的入栈顺序是1,2,3,…,n，其输出序列为p1,p2,…,Pn，若p1是n，则pi是（）A.iB.n-1C.n-i+1D.不确定练习题目②设栈S的初始状态为空，元素a,b,c,d,e,f依次入栈S，出栈的序列为b,d,c,f,e,a，则栈S的容量至少应该是（）A.6B.5C.4D.3E.2练习题目③设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即