数据结构与算法第三章 预习检查 预习内容 栈和队列 本章任务 队列一、什么是栈 一、什么是栈 栈：限定仅在限定仅在一端 一端进行插入或删除操作的线性表 进行插入或删除操作的线性表 aann a1 a1 a2 a2 栈底元素元素 栈顶元素元素 不含元素的不含元素的栈栈称称空栈 二、栈的特点二、栈的特点 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈 顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元 顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元 素最后删除。 素最后删除。 特点特点 ：后进先出 ：后进先出 也就是说，栈是一种后进先出的线性表，简称为也就是说，栈是一种后进先出的线性表，简称为 LIFO LIFO ((Last Last ))表。 什么是顺序栈什么是顺序栈 栈的顺序存储结构简称为 栈的顺序存储结构简称为顺序栈 顺序栈。 可用可用数组 数组来实现顺序栈。 来实现顺序栈。 数组表示顺序栈 数组表示顺序栈 顺序栈操作演示 顺序栈操作演示 参考代码 参考代码 //入栈操作 void Push(T elem) .("栈满!");; //出栈操作 .("栈空!"); tmp; data[top];--top; tmp; 什么是链栈什么是链栈 栈的链式存储结构简称为 栈的链式存储结构简称为链栈 注意链表中指针的注意链表中指针的方向 方向是从栈顶到栈底 栈顶指针栈顶指针SS a1a1 //入栈操作 void Push(T item) (item); top;top //出栈操作 .("栈空!"); (T); top;top top.Next;--size; p.Data; 顺序栈和链式栈的比较顺序栈和链式栈的比较 实现链式栈和顺序栈的操作数据结构实践教程(c#语言描述)，都是需要常数时间 实现链式栈和顺序栈的操作，都是需要常数时间.. 初始时，顺序堆栈必须说明一个固定的长度，当堆栈 初始时，顺序堆栈必须说明一个固定的长度，当堆栈 不够满时，造成一些空间的浪费，而链式堆栈的长度 不够满时，造成一些空间的浪费，而链式堆栈的长度 可变则是长度不需要预先设定，相对比较节省空间， 可变则是长度不需要预先设定，相对比较节省空间， 但是在每个结点中，设置了一个指针域，从而产生了 但是在每个结点中，设置了一个指针域，从而产生了 结构开销。
结构开销。 栈的应用举例 【例】数制转换问题。数制转换问题是将任意一个非负的十进制数转换 为其它进制的数，这是计算机实现计算的基本问题。其一般的解决方 法的利用辗转相除法。以将一个十进制数N转换为八进制数为例进行 说明。 基本思想： 假设N=5142 算法思想如下：当N＞0时，重复步骤1和步骤2。 步骤1：若N0，则将N%8压入栈中，执行步骤2；若N=0。则将栈的 内容依次出栈，算法结束。 步骤2：用N/8代替N，返回步骤1。 用链栈存储转换得到的数位。 算法实现如下： void (int (); while(n s.Pop();.(“{0}”, 队列定义队列定义 队列的操作是在两端进行，其中一端只能进行插入， 队列的操作是在两端进行，其中一端只能进行插入， 该端称为队列的队尾，而另一端只能进行删除，该端 该端称为队列的队尾，而另一端只能进行删除，该端 称为队列的队首。队列的运算规则是 称为队列的队首。队列的运算规则是FIFO FIFO（（First First Out），或者叫做先进先出规则。
），或者叫做先进先出规则。 顺序队列 顺序队列 队列的顺序存储结构称为顺序队列数据结构实践教程(c#语言描述)-数据结构（C#语言描述）第三章，顺序队列实际上 队列的顺序存储结构称为顺序队列数据结构实践教程(c#语言描述)，顺序队列实际上 是运算受限的顺序表。 是运算受限的顺序表。 顺序队列演示 顺序队列演示 请大家自己实现一个顺序队列 请大家自己实现一个顺序队列 链式队列 链式队列 定义链队列的存储结构基本和线性表的定义相同， 定义链队列的存储结构基本和线性表的定义相同， 不过是在单链表的基础上加上一个指针 不过是在单链表的基础上加上一个指针 链式队列演示 链式队列演示 链式队列的插入 链式队列的插入 链式队列的删除 链式队列的删除 参考代码 参考代码 习题 （A）edcba（B）decba（C）dceab（D）abcde 习题 2.栈结构通常采用的两种存储结构是（） 线性存储结构和链表存储结构B散列方式和索引方式 C链表存储结构和数组 D线性存储结构和非线性存储结构 习题 ３.一个队列的入列序列是1,2,3,4,则队列的输出序列（） 习题4.栈和队列的共同点是（） 都是先进后出（B）都是先进先出 （C）只允许在端点处插入和删除元素 （D）没有共同点 总结 栈的特点：先进后出 队列的特点：先进先出 作业 实现顺序队列
文章来源:https://m.docin.com/touch_new/preview_new.do?id=188250039