《数据结构 第三章栈和队列》由会员分享，可在线阅读，更多相关《数据结构 第三章栈和队列（80页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈和队列n教学目的 n通过本章的学习，要求掌握栈和队列的定义， 熟练掌握顺序和链接存储的栈和队列的算法设 计及其程序实现，了解栈和队的各种应用。 n本章主要介绍以下内容：l 栈的概念、存储结构及其基本操作l 队列的概念、存储结构及其基本操作l 栈与队列的应用举例n重点：栈和队列的定义、特征；顺序栈、链栈 的描述及基本操作实现算法；循环队列和链队 列的基本操作实现算法。 n难点：栈满、栈空的条件及描述方法；队满和 队空的描述方法；循环队列上的插入、删除操 作。 栈（stack）n栈的定义n栈的类型定义n栈的存储方式栈的定义n栈是一种特殊的线性表。其特殊性在于限定插 入和删除数据元素的操作
2、只能在线性表的一端 进行。a1ana2栈的示意图栈顶栈底进栈出栈进行插入和删除的 一端是浮动端，被 称为栈顶固定端一端被 称为栈底假设栈S=(a1，a2，a3，an)，则a1称为栈底 元素，an为栈顶元素。栈中元素按a1，a2，a3 ，an的次序进栈，退栈的第一个元素应为栈 顶元素。换句话说，栈的修改是按后进先出的原则进行 的。因此，栈称为后进先出表（LIFO）Last In First Out。栈的类型定义ADT Stack 数据对象：D=ai| ai ElemSet i=1,2,n n0数据关系：R1= | ai,ai+1ElemSet, i=1,2,n-10 约定an端为栈顶，a1端为栈
3、底基本操作：结构初始化InitStack( / private int maxSize; /顺序栈的容量顺序栈的容量private char data; /private char data; /数组，用于存储顺序栈的数据元素，这里存数组，用于存储顺序栈的数据元素，这里存 储的只有字符型储的只有字符型private int top; /private int top; /指示顺序栈的栈顶指示顺序栈的栈顶 n nmaxSizemaxSize 为栈中元素的最大容量。为栈中元素的最大容量。 n ndatadata域域: :为一个一维数组，用于存储栈中元素。为一个一维数组，用于存储栈中元素。n nto
4、ptop域域: :栈顶指针。取值范围为栈顶指针。取值范围为0 0MaxSize-1MaxSize-1。n ntop=-1top=-1表示栈空，表示栈空，top=MaxSize-1top=MaxSize-1表示栈满。表示栈满。类的实现public class SeqStackprivate int maxSize; /顺序栈的容量private char data; /数组，用于存储顺序栈的数据元素，这 里存储的只有字符型private int top; /指示顺序栈的栈顶public int MaxSize /最大容量属性get return maxSize; set maxSize = va
5、lue; public int Top /栈顶属性get return top; 使用SeqList s = new SeqList()生成一个 SeqList类的对象实例n栈底元素为n栈顶指针为n进栈时需将s.top加1，退栈时需将s.top 减1ns.top| ai,ai+1ElemSet, i=1,2,n-10 约定an端为队列尾，a1端为队列头基本操作：结构初始化InitQueue(elsei+;利用模运算可简化为： i=(i+1)%QueueSize？怎么判断队列已满在循环队列中进行出队、入队操作时，头尾指针仍要 加1，朝前移动。只不过当头尾指针指向向量上界（ QueueSize-1
6、）时，其加1操作的结果是指向向量的下 界0。0 1 2 3 4 5 6 7rear front当头尾指针相等时队列为空。abc0 1 2 3 4 5 6 7defghrear frontrear当头尾指针相等时队列为满。n由于入队时尾指针向前追赶头指针，出队 时头指针向前追赶尾指针，故队空和队满 时头尾指针均相等。因此，我们无法通过 front=rear来判断队列“空”还是“满”。解决此问题的方法至少有三种：其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试 尾指针在循环意义下加1后是否等于头指针，若相 等则认为队满（注意：rear所指的单元始终为空 ）；其三
7、是使用一个计数器记录队列中元素的总数（ 实际上是队列长度）顺序队列的C#语言描述：（利用计数器）class CSqQueueprivate int maxSize;/存储队列的容量private char data;/存储数据private int front; /存储队头指针private int rear; /存储队尾指针private int count; /存储元素个数（1）置空队void InitQueue(CSqQueue q)q.Front=q.Rear=0;q.Count=0; （2）判断队空int QueueEmpty(CSqQueue q) return q.Count=0
8、;（4）入队void GetHead(CSqQueue q,char x)if(q.Count = q.MaxSize) Console.writeLine(“queue overflow”);return;q.Count+;q.Dataq.Rear=x;q.Rear=(q.Rear+1)%q.MaxSize;（5）出队char DeQueue(CSqQueue q)if(QueueEmpty(q) Console.WriteLine(“queue underflow”);return ;char temp=q.Dataq.Front;q.Count-;q.Front=(q.Front+1)%
9、q.MaxSize;return temp;（6）取头指针char QueueFront(CSqQueue q)if(QueueEmpty(q)Console.WriteLine(“queue is empty.”);return ;return q.Dataq.Front;顺序队列的C语言描述：（利用布尔变量） class CirQueueprivate int maxSize;/存储队列的容量private char data;/存储数据private int front; /存储队头指针private int rear; /存储队尾指针private bool empty; /为True
10、时为空，为 False为非空（1）置空队void InitQueue(CirQueue q)q.Front=q.Rear=0;q.Empty=True; （2）判断队空bool QueueEmpty(CirQueue q) if(q.Rear=q.Front（4）入队void GetHead(CirQueue q,char x)if(q.Rear=q.Frontreturn;if(q.Rear=q.Front)q.Empty = False; /如果是第一次插入则更改布尔便量的值q.Dataq.Rear=x;q.Rear=(q.Rear+1)%q.MaxSize; （5）出队char DeQu
11、eue(CirQueue q)char temp;if(q.Rear=q.Frontreturn ;temp=q.Dataq.Front;q.Front=(q.Front+1)%q.MaxSize; if(q.Rear=q.Front)q.Empty = True;return temp;（6）取头指针char QueueFront(CirQueue q)if(q.Rear=q.Frontreturn ;return q.Dataq.Front;队列的链式存储结构n队列的链式存储结构简称为链队列，它是限制仅 在表头删除和表尾插入的单链表。n显然仅有单链表的头指针不便于在表尾做插入操 作，为此再
12、增加一个尾指针，指向链表的最后一 个结点。同样地，一个链队列由一个头指针唯一 确定。a1a2rearfrontfrontrear链式结构的C语言描述 typedef struct queuenodedatatype data;struct queuenode *next;queuenode; typedef structqueuenode *front;queuenode *rear;linkqueue;下面给出链队列上实现的基本运算：void InitQueue(linkqueue *q)qfront=qrear=null;int QueueEmpty(linkqueue *q)return
13、 qfront=null void EnQueue(linkqueue *q,datatype x)queuenode *p;p=(queuenode * )malloc(sizeof(queuenode);pdata=x;pnext=null;if(QueueEmpty(q)qfront=qrear=p;elseqrearnext=p;qrear=p;Datatype Dequeue(linkqueue *q)datatype x;queuenode *p if(queueempty(q)error(“queue underflow”);p=qfront;x=pdata;qfront=pne
14、xt;if(qrear=p)qrear=null;free(p);return x;习题n将1、2、3、4四个数分别按顺序入栈（即必须按照先1 再2再3最后4的顺序入栈），但可以按照任意次序出栈 。 问题1：若入栈次序为push(1)，pop()，push(2)， push(3)，pop()，pop( )，push(4)，pop( )，则出栈 的数字序列为什么？ 问题2：能否得到出栈的数字序列4132和数字序列1342， 并说明问什么不能得到或如何得到 问题3：请分析1、2、3、4的24种排列中，哪些序列可以 通过相应的入出栈得到并分别写出入出栈次序n用第二种方法，即少用一个元素空间的方法来区别循 环队列的队空和队满，试设计置空队、判队空、判队 满、出队、入队及取队头元素等六个基本操作。
