《数据结构》课件1第3章 栈和队列.pptx
《《数据结构》课件1第3章 栈和队列.pptx》由会员分享,可在线阅读,更多相关《《数据结构》课件1第3章 栈和队列.pptx(24页珍藏版)》请在文库网上搜索。
1、第3章 栈和队列n栈 栈的定义 顺序栈的表示和实现 链栈的表示和实现n队列 队列的定义 循环队列 链队列 3.1 栈1.栈的定义2栈是限定仅在表的一端进行插入和删除操作的线性表,允许插入和删除的一端称为栈顶,另一端称为栈底。栈的插入操作称为入栈,栈的删除操作称为出栈。不含任何数据元素的栈称为空栈。设有栈S=(a1,a2,a3,,an),则一般称a1为栈底元素,an为栈顶元素。入栈:按a1,a2,a3,,an的顺序出栈:按an,an-1,a2,a1的顺序栈称为后进先出的线性表(LIFO:Last In First Out)a2a1an.栈底栈顶入栈出栈栈的基本操作的基本操作操作操作结果果int
2、Length()返回栈元素个数bool Empty()如栈为空,则返回true,否则返回falsevoid Clear()清空栈bool Push(T e)插入元素e为新的栈顶元素bool Top(T&e)用e返回栈顶元素bool Pop(T&e)删除栈顶元素,并用e返回栈顶元素3.1 栈2.顺序栈的表示和实现3顺序序栈是指利用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。顺序栈可以用一维数组来实现。通常把数组中下标为0的一端作为栈底,同时附设变量top指示栈顶元素在数组中的位置。设存储栈的数组长度为maxSize,则栈空时栈顶位置top=-1,栈满时栈顶位
3、置top=maxSize-1。入栈时,栈顶位置top加1;出栈时,栈顶位置top-1。3.1 栈2.顺序栈的表示和实现4template class SqStackprivate:int top;/栈顶元素在数组中的下标int maxSize;/栈可用的最大容量T*elem;/存储空间的基地址public:SqStack(int size=DEFAULT_SIZE);/构造函数SqStack(SqStack&st);/复制构造函数SqStack();/析构函数int Length();/返回栈中元素个数bool Empty();/判断栈是否为空void Clear();/清空栈bool Pus
4、h(T e);/入栈bool Pop(T&e);/出栈bool GetTop(T&e);/返回栈顶元素;3.1 栈2.顺序栈的表示和实现5/返回栈中元素个数template int SqStack:Length()return top+1;/判断栈是否为空template bool SqStack:Empty()return top=-1;/清空顺序表template void SqStack:Clear()top=-1;/入栈template bool SqStack:Push(T e)if(top=maxSize-1)return false;elem+top=e;return true;
5、/返回栈顶元素template bool SqStack:GetTop(T&e)if(top=-1)return false;e=elemtop;return true;/出栈template bool SqStack:Pop(T&e)if(top=-1)return false;e=elemtop-;return true;3.1 栈3.链栈的表示和实现6链栈是指采用链式存储结构实现的栈,通常用单链表来表示。由于栈的插入和删除操作只能在栈顶执行,因此以单链表的头部作为栈顶是最方便的,而且没有必要像单链表那样为了运算方便附加一个头结点。链栈的结点结构与单链表的结点结构相同template st
6、ruct StNodeT data;StNode *next;3.1 栈3.链栈的表示和实现7template class LinkStackprivate:StNode*top;/栈顶指针public:LinkStack();/构造函数LinkStack(LinkStack&lst);/复制构造函数LinkStack();/析构函数int Length();/返回栈中元素个数bool Empty();/判断栈是否为空void Clear();/清空栈bool Push(T e);/入栈 bool Pop(T&e);/出栈bool GetTop(T&e);/返回栈顶元素;3.1 栈3.链栈的表
7、示和实现8/返回栈中元素个数template int LinkStack:Length()int len=0;StNode*p=top;while(p!=NULL)len+;p=p-next;return len;/判断栈是否为空template bool LinkStack:Empty()return top=NULL;/清空顺序表template void LinkStack:Clear()StNode*p;while(top!=NULL)p=top;top=p-next;delete p;/返回栈顶元素template bool LinkStack:GetTop(T&e)if(top=N
8、ULL)return false;e=top-data;return true;3.1 栈3.链栈的表示和实现9template bool LinkStack:Push(T e)StNode*p=new StNode;/生成新结点if(p=NULL)/动态内存耗尽return false;p-data=e;/将新结点数据域置为ep-next=top;/将新结点插入栈顶top=p;/修改栈顶指针return true;3.1 栈3.链栈的表示和实现10template bool LinkStack:Pop(T&e)if(top=NULL)/栈空return false;StNode*old_to
9、p=top;e=old_top-data;/用e保存栈顶元素的值top=old_top-next;/修改栈顶指针delete old_top;/释放原栈顶元素的空间return true;3.1 栈4.栈的应用进制转换问题11将十进制数转换为二进制数的方法很多,其中一个常用的算法是“除2取余法”。上述计算过程是从低位到高位顺序产生二进制数的各个数位,而输出过程应从高位到低位进行,恰好和计算过程相反,因此可以使用栈来解决这个问题。在计算过程中依次将得到的余数压入栈中,计算完毕后,将栈中的余数依次出栈输出,输出结果就是转换后的二进制数。(1)当n0时重复执行以下操作:计算n除以2的余数并将其压入栈
10、中;用n/2代替n。(2)重复执行以下操作直到栈为空:弹出栈顶元素,并输出被弹出元素的值。3.1 栈4.栈的应用括号匹配问题12给定一个算数表达式,目测怎么判断括号是否匹配呢?可以从左向右看这个表达式中的括号,看到一个“(”就记住它,如果下一个括号是“)”,则划掉这两个括号,如果下一个括号还是“(”,则暂时不管前一个“(”,先把它放在那里,等后面的“(”处理完再来处理它,这正好符合栈的后进先出特性,因此可以使用栈来解决这个问题。从左向右依次扫描表达式字符串中的各字符,若读入的是“(”,则进栈;若读入的是“)”,且栈不为空则出栈,如果栈空则说明没有与之匹配的左括号,匹配失败。当表达式扫描结束时,
11、若栈为空则匹配成功,否则,说明没有与栈中的“(”相匹配的“)”,匹配失败。(1)初始化一个空栈。(2)扫描表达式,依次读入字符,直到表达式扫描完毕。如果读入的字符是(,则将其压入栈;如果读入的字符是),且栈非空,则弹出栈顶元素;如果栈为空,则括号不匹配,返回false。(3)如果栈为空,则左右括号匹配,返回true;否则括号不匹配,返回false。3.2 队列1.队列的定义13队列的基本操作列的基本操作队列是限定只允许在一端进行插入操作,在另一端进行删除操作的线性表。u允许删除(出队)的一端叫做队头u允许插入(入队)的一端叫做队尾u入队和出队的顺序相同u先进先出(FIFO)a1 a2 a3 a
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 数据结构课件1第3章 栈和队列 课件 队列