蔡明志数据结构java 版第 3章.ppt

《蔡明志数据结构java 版第 3章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第3章栈与队列3.1栈和队列基本概念3.2栈的入栈与出栈3.3队列的入队与出队3.4栈与队列的应用3.5程序集锦3.6思考题13.1栈和队列基本概念在算法（algorithms）中，栈（stack）与队列（queue）是常用到的数据结构。栈是一个有序列表（orderlist），其插入（insert）和删除（delete）操作都在同一端，这一端通常称为栈顶（top）。队列（queue）也属于线性列表，与栈不同的是加入和删除不在同一端，删除的那一端称为队头（front），而加入的一端称为队尾（rear）。2栈与队列33.1栈和队列基本概念加入一个元素到栈的操作称为入栈（push），

2、与之相反的是从栈中删除一个元素，称为出栈（pop）。栈是一种后进先出（LastInFirstOut，LIFO）线性表。而队列具有先进先出（FirstInFirstOut，FIFO）的特性。43.2栈的入栈与出栈3.2.1入栈3.2.2出栈53.2.1入栈入栈Java程序片断publicstaticvoidpush_f(){//入栈函数DataInputStreamin=newDataInputStream(System.in);if(top>=MAX-1)//当栈已满，则显示错误System.out.print("Stackisfull!");else{top++;Sy

3、stem.out.print("Pleaseenteritemtoinsert:");63.2.1入栈System.out.flush();try{stack[top]=in.readLine();}catch(IOExceptione){}}}73.2.2出栈出栈Java程序片断：publicvoidpop_f(){//出栈函数if(top<0)//当栈没有数据时，则显示错误System.out.print("Noitem,stackisempty!");else{System.out.print("Item"+stack[top]+"deleted!")

4、;top--;}System.out.println("");}83.3队列的入队与出队3.3.1入队3.3.2出队3.3.3循环队列的入队3.3.4循环队列的出队93.3.1入队入队是在队尾，其程序如下：publicvoidenqueue_f(){//入队函数DataInputStreamin=newDataInputStream(System.in);if(rear>=MAX-1)//当队列已满，则显示错误System.out.println("Queueisfull!");else{rear++;103.3.1入队System.out.print("Pleas

5、eenteritemtoinsert:");System.out.flush();try{q[rear]=in.readLine();}catch(IOExceptione){}System.out.println("");}}113.3.2出队出队是在队头，其Java程序片断如下：publicvoiddequeue_f(){//删除函数if(front>rear)//当队列中没有元素存在时，则显示错误System.out.print("Noitem,queueisempty!");else{123.3.2出队System.out.print("Item"+q[fr

6、ont]+"deleted!");front++;}System.out.println("");}133.3.3循环队列的入队循环队列开始的时候，将front与rear的初值均设为MAX–1。其Java程序片断如下：publicvoidenqueue_f(){//入队函数DataInputStreamin=newDataInputStream(System.in);rear=(rear+1)%MAX;if(front==rear){//当队列已满，则显示错误if(rear==0)rear=MAX–1;143.3.3循环队列的入队elserear=rear–1;System

7、.out.print("Queueisfull!");}else{System.out.print("Pleaseenteritemtoinsert:");System.out.flush();try{cq[rear]=in.readLine();}catch(IOExceptione){}}}153.3.4循环队列的出队Java程序片断：循环队列的出队函数。publicvoiddequeue_f(){//出队函数if(front==rear)//当队列中没有元素存在时，则显