堆栈和队列 课件.ppt
第三章 堆栈和队列,堆栈,堆栈的应用,队列,队列的应用,1,2,3,4,3.1 栈(Stack),1.栈的概念与基本运算,2.顺序栈,3.链栈,1.栈的定义 栈是限制在表的一端进行插入和删除运算的线性表 允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)2.栈的特性 后进先出(LIFO)，或先进后出,一、栈的概念与基本运算,3.栈的图示,一、栈的概念与基本运算,4.生活中的例子,进栈示例,退栈示例,5.栈的基本操作,(1)置栈空：建立一个空栈，准备存放数据(2)判栈是否非空(3)进栈(Push)：在栈顶插入一个新的元素(4)退栈(Pop)：从栈中删除栈顶元素(5)取栈顶：取栈顶元素的值，栈顶不变,6.栈的接口,public interface ICStack/接口 bool IsEmpty();/判栈空 bool IsFull();/判栈满 void MakeEmpty();/清空 bool Push(Type item);/入栈 Type Pop();/出栈 Type Gettop();/取栈顶 string GetStackALLDate(string sname);,1.顺序栈的定义 顺序栈是栈的顺序存储结构，它是运算受限的顺序表。因为栈的插入和删除运算只在栈顶进行，不需要对其它数据进行移动，因此用顺序表作为栈的存储表示比一般的线性表更有利。,二、顺序栈,2.顺序栈的类定义,public class CSeqStack:ICStack private int top;private Type elems;private int Maxsize=100;,2.顺序栈的创建,public CSeqStack()elems=new TypeMaxsize;top=-1;public CSeqStack(int max)Maxsize=max;elems=new TypeMaxsize;top=-1;,3.顺序栈的运算,(1)置栈空public void MakeEmpty()top=-1;(2)判栈是否非空public bool IsEmpty()return top=-1;,(3)进栈(Push)public bool Push(Type item)/入栈 if(!IsFull()elems+top=item;return(true);else return(false);,(4)退栈(Pop)public Type Pop()/出栈 return elemstop-;,(5)取栈顶public Type Gettop()/取栈顶 return elemstop;,(6)判栈满 public bool IsFull()return top=Maxsize-1;,3.多栈操作,0,maxsize-1,lefttop,righttop,两个堆栈共享空间,链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作,三、链栈,链栈的结点类定义,class CStacknode/链栈结点类 private Type data;private CStacknode next;public CStacknode()next=null;public CStacknode(Type data)this.data=data;next=null;public CStacknode(Type data,CStacknodenext)this.data=data;this.next=next;public Type Data get return data;set data=value;public CStacknode Next get return next;set next=value;,1.链栈的类定义,class CLinkStack:ICStack private CStacknode top;,2.链栈的创建,public CLinkStack()top=null;,3.顺序栈的运算,(1)置栈空public void MakeEmpty()top=null;(2)判栈是否非空public bool IsEmpty()return top=null;,(3)进栈(Push)public bool Push(Type item)/入栈 top=new CStacknode(item,top);return(true);,(4)退栈(Pop)public Type Pop()/出栈 Type dt=top.Data;top=top.Next;return dt;,(5)取栈顶 public Type Gettop()/取栈顶 return top.Data;,(6)判栈满 public bool IsFull()return false;,例：对于一个栈，给出输入项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,第三章 堆栈和队列,堆栈,堆栈的应用,队列,队列的应用,1,2,3,4,栈是计算机软件中用得最广泛的数据结构，凡是逻辑上需要“后进先出”的操作都可以用栈来实现。,3.2 栈的应用,一、用栈实现递归函数,递归是程序设计中常用的方法之一，栈的一个重要的应用是可以用来实现递归函数。实现递归调用的关键是建立一个栈，即在内存中开辟一个存储区域，称为递归工作栈，用来存放整个程序运行时所需的信息。,例1.阶乘int Fact(int n)if(n=1)return(1);else return(n*Fact(n-1);,例2.排列组合,问题1：可否用多层的循环语句？问题2：使用什么方法解决？问题3：如何使用递归的方法解决？问题4：如何使用栈的方法解决？,1、递归算法,public void Fun_Permute_Recursion(int n,int m,int k)for(int i=1;i=n;i+)bool tag=false;for(int j=1;j=k-1;j+)if(i=m_percom_tempj)tag=true;break;if(tag=false)m_percom_tempk=i;if(k m)Fun_Permute_Recursion(n,m,k+1);else m_strout+=Getstr_percom_temp(m);,2、用栈实现,public void Fun_Permute_Stack(int n,int m)int s_no=new intm+1;/存放栈顶次数的栈 bool s_tag=new booln+1;/存放下标是否在栈中的标记 int top=0;/第一个进栈 top+;m_percom_temptop=1;s_notop=1;s_tag1=true;/在栈中 rTB_strout.Text=;/栈不空时循环 while(top 0),2、用栈实现,while(top 0)if(s_notop=1)/查看栈顶标记 s_notop=2;/修改栈顶标记 if(top m)/继续进栈 for(int i=1;i=n;i+)if(s_tagi=false)top+;m_percom_temptop=i;s_notop=1;s_tagi=true;/在栈中 break;else m_strout+=Getstr_percom_temp(m);,2、用栈实现,while(top 0)else if(s_notop=2)/查看栈顶标记 s_tagm_percom_temptop=false;/不在栈中了 top-;/出栈/下一个进栈 for(int i=m_percom_temptop+1+1;i=n;i+)if(s_tagi=false)top+;m_percom_temptop=i;s_notop=1;s_tagi=true;/在栈中 break;,
