数据结构（Java语言版）课件 第四章 栈和队列

数据结构（Java语言版）第四章栈和队列【知识目标】

掌握栈和队列的相关概念；

掌握栈的“后进先出”的结构特点；

掌握队列的“先进先出”的结构特点；

熟悉栈在顺序存储结构、链式存储结构下的特点及相应算法实现；

熟悉队列在顺序存储结构、链式存储结构下的特点及相应算法实现；

了解栈和队列的实例应用。【能力目标】

具备实现栈和队列算法的能力；

具备利用栈和队列实现操作的能力；

提升运用栈和递归解决实际问题的能力；

提升运用队列解决实际问题能力。栈是限定仅在表尾的一端进行插入或删除操作的线性表。允许进行插入或删除操作的一端称为栈顶(top)而另一端称为栈底(bottom)a1a2an…进栈出栈栈底栈顶栈的相关概念：栈是一个后进先出（LastInFirstOut，LIFO）的线性表。栈的操作全部是在固定端（栈顶）进行的。a1a2an…进栈出栈栈底栈顶栈的常用操作包括建立栈、元素进入栈（入栈）、元素退出栈（出栈）、取栈顶元素等。栈示意图入栈bottom游客1游客2游客3…………游客10top出栈栈的相关操作：栈的存储结构及操作实现

栈是一种操作受限的特殊的线性表。因此，线性表的存储结构同样适用于栈，栈也可以采用顺序存储结构和链式存储结构。顺序栈链栈

1．顺序栈利用连续的存储单元依次存放自栈底到栈顶的数据元素。通常用一维数组来实现栈的顺序存储，数组下标值小的一端做栈底，设一个栈顶的编号top指示栈顶元素。top43210788075栈的存储结构：1．顺序栈0123n-1空栈…top为使top的值与存储栈的数组的下标相对应，约定top=-1时为空栈，每进栈一个元素，编号top加1；每出栈一个元素，编号top减1。栈的存储结构：图(a)是空栈，top=-1；

图(b)是A入栈，top=0；

图(c)是B、C、D、E依次入栈之后，top=4，栈已满，再入栈，则溢出；图(d)是E、D相继出栈，此时栈中还有3个元素，top=2。

top43210(a)空栈43210A(b)入栈43210ABCDE(c)栈满43210ABC(d)出栈toptoptopA、栈是一种“先进先出”数据结构B、栈可以使用链表或顺序表来实现C、栈只能在栈底插入数据D、栈不能删除数据下列关于栈的叙述正确的是（）A、ABCDEB、EDCBAC、DCEBAD、ECDBA一个栈的入栈序列为ABCDE,则不可能的出栈序列为（）classStackX{ //定义栈privateint[]st;privateinttop;//栈顶指针publicStackX(){ //构造方法

st=newint[20];top=-1;//}}顺序栈类的设计：publicvoidpush(intx){ //入栈

if(top==(st.length-1))

System.out.println("栈满");else{++top;

st[top]=x;}}

顺序栈类的设计：top43210(a)空栈43210Atop

publicvoidpop(){ //出栈

if(top==-1)

System.out.println("栈空");elsetop--;}publicintpeek(){//取出栈顶元素if(top==-1)return0;

else

returnst[top];}

publicvoidshow(){//从顶到底形式输出for(int

i=top;i>=0;i--)

System.out.println(st[i]);}

}

publicstaticvoidmain(String[]args){

StackXs=newStackX();

s.push(10);

s.push(9);

s.push(8);

s.show();

System.out.println("************");

s.pop();

s.show();}图(a)是空栈，top=-1；

图(b)是A入栈，top=0；

图(c)是B、C、D、E依次入栈之后，top=4，栈已满，再入栈，则溢出；图(d)是E、D相继出栈，此时栈中还有3个元素，top=2。

top43210(a)空栈43210A(b)入栈43210ABCDE(c)栈满43210ABC(d)出栈toptoptop对于顺序栈，应注意：入栈时，应首先判断栈是否已满。若栈满，则需要先扩展空间。出栈和取栈顶元素时，必须保证栈不空。若栈空，则不能进行相应操作，否则会导致异常错误。在上述顺序栈的基本操作中，它们的时间复杂度均为O(1)。顺序栈2．链式栈栈也可以以单链表的形式存储。其所有的操作都限制在表头位置上进行，一个链栈由它的栈顶指针唯一确定。

71Topdatanext

84

86∧

（H）

4topdatanext

3

2

（H）

1

∧

链栈类设计1.定义链栈结点类：classStackNode{//链栈中的结点

intdata;

StackNodenext;}

71topdatanext

84

86∧

2.定义链栈类：classLinkStack{//链栈类

StackNodetop=null;……链栈类设计//判断栈是否有为空：publicbooleanempty(){returntop==null;}

71topdatanext

84

86∧

//入栈publicvoidpush(intx){}

topdatanext

84

86∧

S90

StackNodes=newStackNode();

s.data=x;if(empty())top=s;else{

s.next=top;top=s;}

//出栈publicvoidpop(){if(empty())System.out.println(“栈为空");elsetop=top.next;}

Ctop

B

A∧

//取栈顶元素publicStackNode

StackTop(){if(empty()){

System.out.println(“栈为空");returnnull;}else{returntop;}}

Ctop

B

A∧

输出栈元素

publicvoidshow(){

StackNode

top1=top;if(empty())

System.out.println("栈为空");elsewhile(top1!=null){

System.out.println(top1.data);top1=top1.next;}}

Ctop

B

A∧

publicstaticvoidmain(String[]args){ LinkStacks=newLinkStack(); s.push(10); s.push(9); s.push(8); s.show(); System.out.println("************"); s.pop(); s.show(); }

}A、最后进栈的元素总会最先出栈B、同时进行进栈和出栈操作时，总是进栈优先C、每当有出栈操作时，总是进栈优先D、每次出栈的元素总是最先进栈的元素栈的“先进后出”特性是指（）A、top++;data[top]=x;B、top--;data[top]=x;C、data[top]=x;top++;D、data[top]=x;top--;一个栈用数组data[1...n]存储，初始栈顶指针top为0，则以下元素x进栈的正确操作是（）1、栈“后进先出”的特点2、顺序栈的特点及算法实现3、链栈的特点及算法实现总结队列定义：一种操作受限制的线性表，它只允许在表的一端进行插入，通常称为入队，而在另一端进行删除，通常称为出队。允许入队的一端称为队尾，允许出队的一端称为队头。56896592出队入队队尾(rear)队头(front)出队入队队列具有先进先出(FirstInFirstOut,简称FIFO)的特性。排队购物，Windows中的消息队列都是典型的队列的例子。56896592出队入队队列队列与线性表一样，也有顺序存储与链式存储两种方式，分别称为顺序队列与链队列。队列队列与线性表一样，也有顺序存储与链式存储两种方式

顺序队列

链队列注意：front标志队头的位置，rear标志队尾后边的空闲位置。顺序队列由于队列的队头和队尾的位置是变化的，设置两个标志front和rear分别指示队头元素和队尾元素的位置，它们的初值在队列初始化时均应置为0。

顺序队列顺序队列中的溢出现象

①"下溢"现象

当队列为空时，做出队运算产生的溢出现象出队顺序队列

②“上溢”现象

当队列满时，做入队操作产生空间溢出的现象。“上溢”是一种出错状态，应设法避免。

D入队frontrearD入队frontrearA、B出队顺序队列

③“假上溢”现象

随着元素的进进出出，rear与front会一直增大，只增加不减小，导致前面的空间一直闲置，无法重新利用。表尾已越过存储界限，无入队位置，但前面空间却空闲，该现象称为"假上溢"。

D入队frontrear假上溢front

345012rear为了能让front、rear增长到一定程度就返回到编号为零的位置，可以将队列首尾相接，构成一个闭环。顺序队列将顺序队列臆造成一个环状空间，称之为循环队列。把data[0]接在data[5]之后，并非物理存储单元构成这样的环状，而是通过算法实现编号5的下一个编号0，分析时想象成环的存储空间。rearfront

345012A,B,入队(a)AB循环队列中进行出队、入队操作时，头尾编号仍要加1，朝前移动。只不过当头尾编号达到上界（length-1）时，其加1操作的结果是0。思考如何实现这种循环意义加1操作？循环队列①方法一：

if(i==length-1)//i表示front或rear

i=0;

else

i++;

②方法二--利用"模运算"

i=(i+1)%length；

rearfront

345012A,B,入队AB循环加1操作实现：

循环队列front==rear可能是队满，也可能是队空。rearfront

345012AB345012CDEFA345012Bfrontrearfrontrear循环队列判断队满，队空的条件？

队空条件：front==rear不断入队，rear不断加1，最终必将从后面追赶上front，这时front==rear，队列满。循环队列判断队满，队空的条件？

队空条件：front==rear，另设计队满的条件front

345012rear345012FDEGrearHfront为了区分队空条件，损失一个元素空间,让队满条件为：rear再加1就赶上队头（注意rear指示的位置始终为空）循环队列判断队满，队空的条件？front

345012rear345012FDEGrearHfront因为是环状空间，5的下一个位置是0，所以为了实现5+1==0，队满条件为（rear+1）%length==frontfront

345012rear345012FDEGrearHfront队满条件：（rear+1）%length==front

队空条件：front==rear

顺序队列类classQueue{//定义队列类

int[]queArray;

intfront;

intrear;

publicQueue(){//构造方法

queArray=newint[20];front=0;rear=0;}publicvoidinsert(intx){//入队列

if((rear+1)%queArray.length==front)

System.out.println(“队列满“);

else{queArray[rear]=x;rear=(rear+1)%queArray.length;}}

publicintremove(){//出队列

if(front==rear){

System.out.println(“队列为空“);return-1;}

else{

inttemp=queArray[front];front=(front+1)%queArray.length;returntemp;}}

}publicvoidshow(){//从头到尾输出队列元素

intf=front;

if(f==rear)

System.out.println("队列为空");else{whi