Java数据结构(三)
——队列
队列(简称为队)也是一种特殊的线性表,队列的数据元素以及数据元素之间的操作与线性表完全相同,差别是线性表允许在任意位置插入和删除,而队列只允许在一端进行插入操作而在另一端进行删除操作。队列允许插入操作的一端称为队尾,允许进行删除操作的一端称为对头。队列的插入操作通常称为入队列,队列的删除操作通常称为出队列。
因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,因此队列也被称为先进先出表。比方说,大家在食堂排队买饭时,只有最早来排队的,即最先入队列的,才能最先买到饭,即最先出队列。
顺序队列
使用顺序存储结构的队列称为顺序队列。
如图所示,这是一个有4个存储空间的顺序队列的动态示意图,图中front表示队头,rear表示队尾,图(a)表示一个空队列,此时front=rear=0;图(b)表示数据元素A、B、C入队列后的状态。此时front=0,rear=3;图(c)表示A已经退出队列,此时front=1,rear=3;图(d)表示B、C都已经出队列,此时队列已空。但是front=rear=3。那么,假如我们一开始设置的队列长度仅为3个时,即maxSize=3,那么如果还有数据元素想要进入队列,顺序队列将因为越出数组下界而“溢出”。但实际上数组中还有3个位置可以存储,此时的“溢出”并是不是由于数组空间不够而产生的溢出。顺序队列因多次入队列和出队列的操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出。
假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上届值而产生的。因此,解决该问题的方法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到maxSize-1后,在加1就自动到0,这样就不会出现假溢出的问题,例如rear=(rear+1)%6。
不过顺序循环队列还存在一个问题,即当队列空时和队列满时,front=rear=0,即无法区分队列为空还是为满的状态,这样最好的解决无疑是设置一个计数器count,初始时设置count=0(队列空时为0),每入列一次count加一,每出列一次count就减一,因此,这样判断队列为空的条件为count==0,队列满的判断条件为count!=0&&front == rear。下面为具体实现代码:
package pzw.Queue; /** * 使用顺序存储结构实现的队列 * @author pzw * */ public class SeqQueue implements queue{ public final int defaultSize = 10;//默认构造队列的大小 public Object[] queue;//队列数组 public int top;//队列头部位置 public int end;//队列尾部位置 public int count;//队列中现有元素的个数 public int maxSize;//队列中最大元素的个数 //无参构造函数 public SeqQueue(){ initiate(defaultSize); } //构造函数 public SeqQueue(int size){ initiate(size); } //队列初始化 private void initiate(int size){ maxSize = size; queue = new Object[size]; top = 0; end = 0; count = 0; } public void insert(Object elm) throws Exception{ if(top == end&&count != 0){ throw new Exception("该队列已满,请先清空该队列"); } queue[end] = elm; end = (end + 1) % maxSize;//加一后求模,解决顺序存储结构假溢出 count++; } public Object delete() throws Exception{ if(top == end&&count == 0){ throw new Exception("该队列已空,请添加数据"); } top = (top + 1) % maxSize; count--; return queue[top]; } public Object getData() throws Exception{ if(top == end&&count == 0){ throw new Exception("该队列已空,请添加数据"); } return queue[top]; } public boolean notEmpty() { return count > 0; } }
链式队列
package pzw.Queue; /** * 队列的链式存储结构的实现 * @author pzw * */ public class LinQueue implements queue{ private Node top;//队列的头部 private Node end;//队列的尾部 private int count;//队列中元素的个数 //构造函数 public LinQueue(){ initiate(); } //初始化队列 private void initiate(){ top = null; end = null; count = 0; } public void insert(Object elm) throws Exception { Node newNode = new Node(elm,null); if(end != null){ end.next = newNode;//插入新结点 } end = newNode;//重置尾结点 if(top == null){ top = newNode; } count++; } public Object delete() throws Exception { if(count == 0){ throw new Exception("该队列已空,请添加数据"); } Node temp = top; top = top.next;//重置头结点 count--; return temp.elm; } public Object getData() throws Exception { if(count == 0){ throw new Exception("该队列已空,请添加数据"); } return top.elm; } public boolean notEmpty() { // TODO Auto-generated method stub return count != 0; } }
相关推荐
Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法
java数据结构总结java数据结构总结java数据结构总结java数据结构总结java数据结构总结
JavaJava 数据结构详细教程Java 数据结构详细教程Java 数据结构详细教程Java 数据结构详细教程Java 数据结构详细教程Java 数据结构详细教程Java 数据结构详细教程Java 数据结构详细教程Java 数据结构详细教程Java ...
java数据结构经典例题java数据结构经典例题java数据结构经典例题java数据结构经典例题java数据结构经典例题java数据结构经典例题java数据结构经典例题java数据结构经典例题java数据结构经典例题java数据结构经典例题...
java数据结构java数据结构java数据结构java数据结构java数据结构java数据结构java数据结构java数据结构java数据结构java数据结构
java 数据结构总结的思维导图笔记,个人做的非常全,需要的自行下载
中软国际培训的学习笔记,很值得参考。学习java数据结构很有必要看看
Java 数据结构 applet演示 Java 数据结构 applet演示 Java 数据结构 applet演示 Java 数据结构 applet演示
Java数据结构和算法第三十一讲.avi Java数据结构和算法第三十七讲.avi Java数据结构和算法第三十三讲.avi Java数据结构和算法第三十九讲.avi Java数据结构和算法第三十二讲.avi Java数据结构和算法第三十五讲.avi ...
全套详细Java数据结构PPT!Java数据结构课件
Java数据结构和算法.pdf
java数据结构全套
Java数据结构与算法Java数据结构与算法Java数据结构与算法Java数据结构与算法Java数据结构与算法Java数据结构与算法Java数据结构与算法
Java数据结构题
数据结构JAVA版,是本入门级的教材,可以借鉴下,里面有些例子还不错~
很全面的java数据结构的习题,帮助大家学习java的数据结构,比一般的只懂得java API的程序员更胜一筹
《Java数据结构与算法》中的示例applet,很完整很全面,方便大家交流学习
Java数据结构 线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构
Java数据结构学习笔记