数据结构(Java版) 模块3 栈和队列

上课啦THEPOWERPOINTTEMPALTE模块3栈和队列实例引入1栈2队列3应用举例4小结5学习目的与要求重点：栈和队列的特点栈和队列的进出运算循环队列的特点及基本运算难点：栈和队列的相关运算使用栈和队列解决实际应用问题3.1实例引入【实例1】栈的实例

栈是用来保存一些尚未处理而又等待处理的数据项，这些数据项的使用顺序与保存数据相反。

栈在日常生活中几乎到处可见，如枪支上的子弹匣，后压入的子弹总是先射出；餐馆中餐盘的堆叠和使用；浏览器中后退功能的实现；各种应用软件中撤销操作的实现；在程序设计中，经常会需要栈这样的数据结构，例如，在for循环嵌套执行过程中，开始执行时，外层循环先开始，内层循环后开始，在结束时，内层循环先结束，外层循环后结束，这就形成了一个栈；函数和过程调用都是栈的具体应用。3.1实例引入【实例2】队列实例

队列在现实生活中无处不在，例如，去火车站、银行、医院等服务行业办理业务都存在排队问题；甚至在生产管理中，也存在生产任务的排队计划和管理问题。队列在计算机系统中的应用也非常广泛，例如，操作系统中的作业排队；在允许多道程序运行的计算机系统中，同时有几个作业运行，如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队，每当通道传输完毕可以接受新的输出任务时，排在前面的作业先从队列中退出作输出操作，凡是申请输出的作业都是从队尾进入队列。3.2.1栈的概念及基本运算1．基本概念栈（Stack）是限制在表的一端进行插入和删除的线性表。允许插入、删除的一端称为栈顶（top）。无法进行数据操作的固定端称为栈底（bottom）。当表中没有元素时称为空栈。栈上溢（Full）是指在栈内空间已存满数据时，如果仍希望能做进栈动作，就会产生“上溢出”，这是一种空间不足的出错状态。栈下溢（Empty）是指在栈内空间已无数据时，如果仍然希望能做出栈操作，就会产生“下溢出”，这是一种数据不足的出错状态。3.2.1栈的概念及基本运算2．栈的特点

由于栈的插入和删除操作都是在栈顶进行，所以先进栈的元素后出栈，最后进栈的元素先出栈，基于这个特点，栈又称为后进先出（LastInFirstOut）的线性表，简称为LIFO表。如图3.1所示，元素是以a1，a2，…，an的顺序进栈，出栈的次序却是an，…，a2，a1。3.2.1栈的概念及基本运算3．进栈出栈变化形式思考：最先进栈的元素，就只能最后出栈呢？答案是不一定。栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。例如：现有a1，a2，a3三个元素依次进栈，会有哪些出栈次序呢？第一种：a1，a2，a3进，a3，a2，a1出，出栈序列为a3，a2，a1。第二种：a1进，a1出，a2进，a2出，a3进，a3出，出栈序列为a1，a2，a3。第三种：a1，a2进，a2，a1出，a3进，a3出，出栈序列为a2，a1，a3。第四种：a1进，a1出，a2，a3进，a3，a2出，出栈序列为a1，a3，a2。第五种：a1，a2进，a2出，a3进，a3出，a1出，出栈序列为a2，a3，a1。3.2.1栈的概念及基本运算4．栈的基本运算（1）initStack（S）初始化。构造一个空栈S。（2）stackEmpty（S）判栈空。若S为空栈，则返回true，否则返回false。（3）stackFull（S）判栈满。若S为满栈，则返回true，否则返回false。注意：该运算只适用于栈的顺序存储结构。（4）push（S，e）进栈。若栈S不满，则将元素e插入S的栈顶。（5）pop（S）出栈。若栈S非空，则将S的栈顶元素删去。3.2.2栈的顺序存储结构及其算法实现1．顺序栈的基本概念

顺序栈，即栈的顺序存储结构，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。

通常用一维数组stack[0..stackSize-1]来实现栈的顺序存储，大小stackSize预先定义。stack[0]端表示栈底，设一个整型指针top指向栈顶元素，top=-1时为空栈；每进栈一个元素，指针top加1；每出栈一个元素，指针top减1；top=stackSize-1时表示栈满。图3.2表示了顺序栈中数据元素和栈顶指针之间的对应关系。3.2.2栈的顺序存储结构及其算法实现2．顺序栈的类定义public

classArrStack{//定义顺序栈

private

int[]stack;

private

inttop;

publicArrStack(intsize){//构造方法 stack=new

int[size]; top=-1; } //成员方法

public

final

int[]getStack(){

returnstack; }

public

final

voidsetStack(int[]stack){

this.stack=stack; }

public

final

intgetTop(){

returntop; }

public

final

voidsetTop(inttop){

this.top=top; }}3.2.2栈的顺序存储结构及其算法实现3．顺序栈的基本运算（1）初始化public

voidinitStack(){ //将顺序栈置空 top=-1;}（2）判栈空public

booleanstackEmpty(){ //判断一个栈是否为空，若空，返回true，否则返回false

return(top==-1);}（3）判栈满public

booleanstackFull(){ //判断一个栈是否已满，若满，返回true，否则返回false

if(top==stack.length-1)

return

true;

else

return

false;}3.2.2栈的顺序存储结构及其算法实现3．顺序栈的基本运算（4）进栈publicvoidpush(inte){ //入栈操作

if(stackFull()){//判栈满 System.out.println("栈满");//返回出错信息，退出运行

return; } stack[++top]=e;//栈顶指针加1后将e入栈}（5）出栈public

voidpop(){ //出栈操作

if(stackEmpty())//判栈空 System.out.println("空栈");//返回出错信息，退出运行 else

intstackTop=stack[top--];//栈顶元素放到变量stackTop，栈顶指针减1}以上运算都没有涉及任何循环语句，因此，时间复杂度均是O（1）。3.2.2栈的顺序存储结构及其算法实现4．共享同一数组空间的双栈结构

当程序中同时使用两个栈时，可以将两个栈的栈底设在数组空间的两端，两个栈顶指针分别向中间延伸，如图3.3所示。当一个栈里的元素较多，超过数组空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。3.2.3栈的链式存储结构及其算法实现1．链栈的基本概念

链栈，即栈的链式存储结构。通常用不带头结点的单链表表示一个栈，设置一个栈顶指针top，进栈和出栈都在top端进行，如图3.4所示。栈顶指针就是链表的头指针。链栈是动态存储结构，元素个数动态变化，预先不需要指定。3.2.3栈的链式存储结构及其算法实现2．链栈的类型定义public

classLinkedStack{

private

intdata;//数据域，可根据实际情况修改

privateLinkedStacknext;//指针域，存放当前元素直接后继元素的地址

privateLinkedStacktop;//栈顶指针

privateintcount;//进栈元素计数器

publicLinkedStack(){//构造方法,创建一个空栈top=null;}//成员方法

public

intgetData(){

returndata;}

public

voidsetData(intdata){

this.data=data;}

publicLinkedStackgetNext(){

returnnext;}

public

voidsetNext(LinkedStacknext){

this.next=next;}}3.2.3栈的链式存储结构及其算法实现3．链栈的基本运算（1）初始化public

voidinitStack(){//将链栈置空top=null;}（2）判栈空public

booleanstackEmpty(){//判断一个栈是否为空，若空，返回true，否则返回false

return(top==null);}（3）进栈public

voidpush(LinkedStacknewNode){//入栈操作newNode.setNext(top);top=newNode;count++;}3.2.3栈的链式存储结构及其算法实现3．链栈的基本运算（4）出栈public

voidpop(){//出栈操作LinkedStackq;

if(stackEmpty())//判栈空System.out.println("栈空");//返回出错信息，退出运行

else{q=top;top=top.next;count--;}}注意：链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义stackFull运算。以上运算都没有涉及任何循环语句，因此，时间复杂度均是O(1)。3.2.4栈在Java类库中的实现Java类库中的java.util.Stack类实现了栈的功能，其直接父类是Vector类，其常用的构造方法和成员方法如下：1）构造方法publicStack()//创建一个空栈2）常用成员方法publicObjectpush(Objectitem)//进栈一个元素publicObjectpop()//出栈一个元素publicbooleanempty()//判断栈是否为空publicintsize()//获取栈中元素的个数publicObjectpeek()//返回栈顶元素publicintsearch(Objecto)//返回对象在栈中的位置，以1为基数3.3.1队列的概念及基本运算1．基本概念队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。允许删除的一端称为队头（front）。允许插入的一端称为队尾（rear）。当队列中没有元素时称为空队列。2．队列的特点队列的修改是依据先进先出的原则进行的。新来的成员总是加入队尾，每次离开的成员总是队列头上的。因此，队列亦称作先进先出（FirstInFirstOut）的线性表，简称为FIFO表。如图3.5所示，在队列中依次加入元素a1，a2，…，an之后，a1是队头元素，an是队尾元素。退出队列的次序只能是a1，a2，…，an。3.3.1队列的概念及基本运算3．队列的基本运算（1）initQueue（Q）初始化。构造一个空队列Q。（2）queueEmpty（Q）判队空。若队列Q为空，则返回true，否则返回false。（3）queueFull（Q）判队满。若队列Q为满，则返回true，否则返回false。注意：此操作只适用于队列的顺序存储结构。（4）enQueue（Q，e）入队。若队列Q非满，则将元素e插入到Q的队尾。（5）deQueue（Q）出队。若队列Q非空，则删去Q的队头元素。3.3.2队列的顺序存储结构及其算法实现1．顺序队列的基本概念顺序队列，即队列的顺序存储结构，是利用一组地址连续的存储单元依次存储从队头到队尾的数据元素。通常用一维数组queue[0..queueSize-1]来实现队列的顺序存储，设置两个指针front和rear分别指示队头元素和队尾元素在数组中的位置，并约定队头指针指示队列中的第一个元素，队尾指针指示队尾元素位置的后一个位置。如图3.6表示了顺序队列中数据元素和队头、队尾指针之间的对应关系，归纳如下：（1）队头队尾指针在队列初始化时均应置为0。（2）入队时：将新元素插入rear所指的位置，然后将rear加1。（3）出队时：删去front所指的元素，然后将front加1。（4）假上溢：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。如图3.6（d）所示，front=2，rear=queueSize时再有元素入队就会发生溢出，但队头前面还有单元是空的。3.3.2队列的顺序存储结构及其算法实现

当队列中实际的元素个数远远小于数组空间的规模时，也可能由于尾指针已超越数组空间的上界而不能做入队操作。该现象称为“假上溢”现象。注意：①当头尾指针相等时，队列为空。②在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。3.3.2队列的顺序存储结构及其算法实现2．循环队列

为充分利用数组空间，克服“假上溢”现象，将存放队列元素的数组空间想象为一个首尾相接的圆环，这种形式的顺序队列称为循环队列（CircularQueue）。如图3.7所示。3.3.2队列的顺序存储结构及其算法实现（1）循环队列的基本操作循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向数组上界（queueSize-1）时，其加1操作的结果是指向数组的下界0。这种循环意义下的加1操作可以描述为：①方法一：if(i+1==queueSize)//i表示front或reari=0;elsei++;②方法二：利用"模运算"i=(i+1)%queueSize;3.3.2队列的顺序存储结构及其算法实现（2）循环队列边界条件处理

如图3.8所示，在循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是"空"还是"满"。3.3.2队列的顺序存储结构及其算法实现解决这个问题的方法至少有三种：①另设一布尔变量以区别队列的空和满。②少用一个元素存储空间。当队尾指针所指向的空单元的后继单元是队头元素所在的单元时，则停止入队。这样一来，队尾指针永远追不上队头指针，所以队满时不会有front=rear。这时队满的条件为(rear+1)%queueSize=front。判队空的条件不变，仍为front=rear。③使用一个存储队列中元素个数的变量如count，当count=0时为队空，当count=queueSize时为队满。以下关于循环队列及其操作算法都基于第3种方法实现。注意：循环队列中元素的个数为(rear-front+queueSize)%queueSize3.3.2队列的顺序存储结构及其算法实现（3）循环队列的类型定义public

classArrQueue{//定义循环队列

private

int[]queue;

private

intfront;

private

intrear;

private

intcount;

publicArrQueue(intqueueSize){//构造方法 queue=new

int[queueSize]; front=0; count=0; rear=0; } //成员方法

public

final

intgetFront(){

returnfront; }

public

final

voidsetFront(intfront){

this.front=front; }

public

final

int[]getQueue(){

returnqueue; }

public

final

voidsetQueue(int[]queue){

this.queue=queue; }

public

final

intgetRear(){

returnrear; }

public

final

voidsetRear(intrear){

this.rear=rear; }}3.3.2队列的顺序存储结构及其算法实现（4）循环队列的基本运算①初始化public

voidinitQueue(){ //将循环队列置空 front=0; count=0; rear=0;}②判断队列是否为空public

boolean

queueEmpty(){ //判断一个循环队列是否为空，若空，返回true，否则返回false

return(count==0);}③判断队列是否为满public

booleanqueueFull(){ //判断一个循环队列是否已满，若满，返回true，否则返回false。

return(count==queue.length);}3.3.2队列的顺序存储结构及其算法实现（4）循环队列的基本运算④入队public

voidenQueue(inte){ //入队操作

if(queueFull())//判循环队列是否已满 System.out.println("队列已满");//返回出错信息，退出运行

else{ queue[rear]=e; rear=(rear+1)%queue.length; count++; }}⑤出队public

voiddeQueue(){ //出队操作

if(queueEmpty())//判队列是否为空 System.out.println("队列为空");//返回出错信息，退出运行 else{

inttemp=queue[front];//队头元素放到变量temp，队头指针加1 front=(front+1)%queue.length; count--;

}}以上运算都没有涉及任何循环语句，因此，时间复杂度均是O（1）。3.3.3队列的链式存储结构及其算法实现1．链队列的基本概念

链队列，即队列的链式存储结构。它是限制仅在表头删除和表尾插入的单链表。对于使用中数据元素变动较大的队列，采用链队列比顺序队列更有利。

为了操作方便，通常用带头结点的单链表来实现链队列，如图3.9所示，当一个队列为空时（即front=rear=null），其头指针和尾指针都指向头结点；当队列非空时，队头指针指向头结点，队尾指针指向最后一个结点。3.3.3队列的链式存储结构及其算法实现2．链队列的类型定义public

classLinkedQueue{

private

intdata;//数据域，可根据实际情况修改

privateLinkedQueuenext;//指针域，存放当前元素直接后继元素的地址

privateLinkedQueuefront;//队头指针

privateLinkedQueuerear;//队尾指针

private

intcount;//进队列元素计数器

publicLinkedQueue(){//构造方法,创建一个空队列 front=rear=null; count=0; } //成员方法public

intgetData(){

returndata; }

public

voidsetData(intdata){

this.data=data; }publicLinkedQueuegetNext(){

returnnext; }

public

voidsetNext(LinkedQueuenext){

this.next=next; }}3.3.3队列的链式存储结构及其算法实现3．链队列的基本运算（1）初始化public

voidinitQueue(){ //将链队列置空

front=rear=null;}（2）判队空public

booleanqueueEmpty(){ //判断一个队列是否为空，若空，返回true，否则返回false

return(count==0);}（3）入队public

voidenQueue(LinkedQueuenewNode){ //入队操作 rear.setNext(newNode); rear=newNode; count++;}3.3.3队列的链式存储结构及其算法实现3．链队列的基本运算（4）出队public

voiddeQueue(){ //出队操作 LinkedQueueq;

if(queueEmpty())//判队空 System.out.println("队列为空");//返回出错信息，退出运行 else{ q=front; front=front.getNext();

if(front==rear)rear=front; count--;

}}以上运算都没有涉及任何循环语句，因此，时间复杂度均是O（1）。注意：①和链栈类似，无须考虑判队满的运算及上溢。②在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既就是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。3.3.4队列在Java类库中的实现在JAVA5以后的版本中，新增了java.util.Queue接口。该接口扩展了java.util.Collection接口，用于支持队列的常见操作。另外，java.util.LinkedList类实现了Queue接口，因此，可以把LinkedList类当成队列结构来使用。常用成员方法如下：publicbooleanadd(Objectobj) //在队尾添加一个元素，成功返回true,否则返回falsepublicbooleanoffer(Objectobj) //在队尾添加一个元素，成功返回true,否则返回falsepublicbooleanaddLast(Objectobj) //在队尾添加一个元素，无返回值publicObjectremoveFisrt() //删除并返回表头元素publicObjectremove() //删除并返回队头元素publicObjectpoll() //删除并返回队头元素publicObjectelement() //返回队头元素，不删除publicObjectpeek() //返回队头元素，不删除3.4.1栈的应用实例【例3.1】利用