Java数据结构之队列(动力节点Java学院整理)
队列的定义：
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
（1）允许删除的一端称为队头（Front）。
（2）允许插入的一端称为队尾（Rear）。
（3）当队列中没有元素时称为空队列。
（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾，每次离开的成员总是队列头上的（不允许中途离队）。
队列的存储结构及实现
队列的顺序存储结构
（1） 顺序队列的定义：
队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
（2）顺序队列的表示：
和顺序表一样，顺序队列利用内存中一段连续的存储空间来存放当前队列中的元素。
由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素，它们的初值在队列初始化时均应置为0。
（3）顺序队列的基本操作
入队时：将新元素插入rear所指的位置的后一位。
出队时：删去front所指的元素，然后将front加1并返回被删元素。
（4）顺序表的溢出现象
①“下溢”现象
当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
② "真上溢"现象
当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
③ "假上溢"现象
由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于内存中本分配的空间时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。如下图
循环队列：
如上图所示，这种头尾相接的顺序存储结构称为循环队列（circular queue）。
循环队列中需要注意的几个重要问题：
①队空的判定条件，队空的条件是front=rear；
②队满的判定条件，（rear+1）%QueueSize=front。QueueSize为队列初始空间大小。
循环队列的java实现代码
public class Queue {
private int size; //当前队列元素个数
private int[] Array;//存放队列元素的数组
private int MaxSize;//队列最大尺寸
//构造函数
public Queue(int maxsize){
MaxSize = maxsize;
Array = new int[MaxSize];
size = 0;
}
//判断队列是否为空
public int IsEmpty(){
if(size == 0)
return 0;
return -1;
}
//判断队列是否为满
public int IsFull(){
if(size == MaxSize)
return 0;
return -1;
}
//返回队列长度
public int GetLength(){
return this.size;
}
//队列插入
public int EnQueue(int x){
//若队列不满，把x插到队尾，返回0；否则返回-1；
if(IsFull() == -1){
Array[size] = x;
size++;
return 0;
}
return -1;
}
//队列删除
public int DeEmpty(){
//若队列不空，则删除对头元素，返回该元素的值，否则返回-404；
if(IsEmpty() == -1){
int x = Array[0];
for(int j=0; j<MaxSize-1; j++)
Array[j] = Array[j+1];//前移
MaxSize--;
return x;
}
return -404;
}
//读取队列头部元素
public int GetFront(){
//读队头，若队列非空，则返回队列头元素的值，否则返回-404；
if(IsEmpty() == -1){
return Array[0];
}
return -404;
}
}
以上所述是小编给大家介绍的Java数据结构之队列(动力节点Java学院整理)，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！
相关推荐
-
java数据结构与算法之双向循环队列的数组实现方法
本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p
-
Java数据结构之循环队列简单定义与用法示例
本文实例讲述了Java数据结构之循环队列简单定义与用法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 与普通队列的区别在于循环队列添加数据时,如果其有效数据end == maxSize - 1(最大空间)的话,end指针又移动到-1的位置 删除数据时,如果head== maxSize时 head指针移动到0的位置 2.示例图: 二.实现代码: package com.java.queue; /** * @描述 对列 * @项目名称 Java_DataStruct * @包名 com.
-
Java数组模拟优先级队列数据结构的实例
优先级队列 如果我们给每个元素都分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了.这样,我们就引入了优先级队列 这种数据结构. 优先级队列(priority queue) 是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找(2)插入一个新元素 (3)删除 一般情况下,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素 .对于优先权相同的元素,可按先进先出次序处理或按任意优先
-
java 数据结构之栈与队列
java 数据结构之栈与队列 一:对列 队列是一种先进先出的数据结构 实现代码: package Queue; /* * 使用java构建队列,并模拟实现队列的入队和出对方法 */ public class Queue { //队列类 private int maxSize; //定义队列的长度 private int[] arrQueue; //队列 private int rear; //定义队列的尾指针 private int front; //定义队列的头指针 private int e
-
java 数据结构中栈和队列的实例详解
java 数据结构中栈和队列的实例详解 栈和队列是两种重要的线性数据结构,都是在一个特定的范围的存储单元中的存储数据.与线性表相比,它们的插入和删除操作收到更多的约束和限定,又被称为限定性的线性表结构.栈是先进后出FILO,队列是先进先出FIFO,但是有的数据结构按照一定的条件排队数据的队列,这时候的队列属于特殊队列,不一定按照上面的原则. 实现栈:采用数组和链表两种方法来实现栈 链表方法: package com.cl.content01; /* * 使用链表来实现栈 */ public cl
-
Java模拟栈和队列数据结构的基本示例讲解
栈和队列: 一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建: 访问受限,在特定时刻,只有一个数据可被读取或删除: 是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组.链表来实现栈. 模拟栈结构 同时,只允许一个数据被访问,后进先出 对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数,操作比较快 例,使用数组作为栈的存储结构 public class StackS<T> { private int max; private T[] ary; priv
-
Java数据结构之队列的简单定义与使用方法
本文实例讲述了Java数据结构之队列的简单定义与使用方法.分享给大家供大家参考,具体如下: 一.概述: 1.说明: 队列的原则时先进先出,就像生活中排队取票一样,谁排在前面谁先得到 2.有五个属性: 1)数组元素 2)最大空间 3)长度 4)队头 5)队尾 3.示例图: 二.代码实现 /** * @描述 对列 * @项目名称 Java_DataStruct * @包名 com.java.stack * @类名 Queue * @author chenlin * @version 1.0 * @S
-
Java数据结构之有效队列定义与用法示例
本文实例讲述了Java数据结构之有效队列定义与用法.分享给大家供大家参考,具体如下: /** * @描述 有序对列 * 从任何位置插入数据都是有序的 * @项目名称 Java_DataStruct * @包名 com.java.stack * @类名 Queue * @author chenlin */ public class SequeQueue { private long[] arr; private int maxSize;// 最大空间 private int len;// 有效长度
-
Java数据结构之队列(动力节点Java学院整理)
队列的定义: 队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表. (1)允许删除的一端称为队头(Front). (2)允许插入的一端称为队尾(Rear). (3)当队列中没有元素时称为空队列. (4)队列亦称作先进先出(First In First Out)的线性表,简称为FIFO表. 队列的修改是依先进先出的原则进行的.新来的成员总是加入队尾,每次离开的成员总是队列头上的(不允许中途离队). 队列的存储结构及实现 队列的顺序存储结构 (1) 顺序队列的定义: 队列
-
Java数据结构之图(动力节点Java学院整理)
1,摘要: 本文章主要讲解学习如何使用JAVA语言以邻接表的方式实现了数据结构---图(Graph).从数据的表示方法来说,有二种表示图的方式:一种是邻接矩阵,其实是一个二维数组:一种是邻接表,其实是一个顶点表,每个顶点又拥有一个边列表.下图是图的邻接表表示. 从图中可以看出,图的实现需要能够表示顶点表,能够表示边表.邻接表指是的哪部分呢?每个顶点都有一个邻接表,一个指定顶点的邻接表中,起始顶点表示边的起点,其他顶点表示边的终点.这样,就可以用邻接表来实现边的表示了.如顶点V0的邻接表如下: 与
-
Java数据结构之链表(动力节点之Java学院整理)
单链表: insertFirst:在表头插入一个新的链接点,时间复杂度为O(1) deleteFirst:删除表头的链接点,时间复杂度为O(1) find:查找包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) remove:删除包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) public class LinkedList { private class Data{ private Object obj; private Data next =
-
Java数据结构之数组(动力节点之Java学院整理)
数组的用处是什么呢?--当你需要将30个数进行大小排列的时候,用数组这样的数据结构存储是个很好的选择,当你是一个班的班主任的时候,每次要记录那些学生的缺勤次数的时候,数组也是很有用.数组可以进行插入,删除,查找等. 1)创建和内存分配 Java中有两种数据类型,基本类型和对象类型,也有人称为引用类型,Java中把数组当成对象,创建数组时使用new操作符. int array[] = new int[10]; 既然是对象,那么array便是数组的一个引用,根据Java编程思想(一) -- 一切都是
-
Java Iterator迭代器_动力节点Java学院整理
迭代器是一种模式,它可以使得对于序列类型的数据结构的遍历行为与被遍历的对象分离,即我们无需关心该序列的底层结构是什么样子的.只要拿到这个对象,使用迭代器就可以遍历这个对象的内部. 1.Iterator Java提供一个专门的迭代器<<interface>>Iterator,我们可以对某个序列实现该interface,来提供标准的Java迭代器.Iterator接口实现后的功能是"使用"一个迭代器. 文档定义: Package java.util; publici
-
Java List简介_动力节点Java学院整理
Java中可变数组的原理就是不断的创建新的数组,将原数组加到新的数组中,下文对Java List用法做了详解. List:元素是有序的(怎么存的就怎么取出来,顺序不会乱),元素可以重复(角标1上有个3,角标2上也可以有个3)因为该集合体系有索引 ArrayList:底层的数据结构使用的是数组结构(数组长度是可变的百分之五十延长)(特点是查询很快,但增删较慢)线程不同步 LinkedList:底层的数据结构是链表结构(特点是查询较慢,增删较快) Vector:底层是数组数据结构 线
-
十大常见Java String问题_动力节点Java学院整理
本文介绍Java中关于String最常见的10个问题: 1. 字符串比较,使用 "==" 还是 equals() ? 简单来说, "==" 判断两个引用的是不是同一个内存地址(同一个物理对象). 而 equals 判断两个字符串的值是否相等. 除非你想判断两个string引用是否同一个对象,否则应该总是使用 equals()方法. 如果你了解 字符串的驻留 ( String Interning ) 则会更好地理解这个问题 2. 对于敏感信息,为何使用char[]要比
-
Java二进制操作（动力节点Java学院整理）
移位 位运算中大多数操作都是向左移位和向右移位.在Java中,这对应着<<和>>这两个操作符,示例如下: /* 00000001 << 1 = 00000010 */ 1 << 1 == 2 /* 00000001 << 3 = 00001000 */ 1 << 3 == 8 /* 11111111 11111111 11111111 11110000 >> 4 = 11111111 11111111 11111111 1
-
Java数组优点和缺点_动力节点Java学院整理
数组是Java语言的基本知识之一,在深入学习Java基础后,我们都知道那些容器,在之后,在我们学习.工作的过程中基本就是使用容器了,很少很使用数组,那么为什么还要有数组呢,我也是今天才遇到这个问题,专门的找资料学习了一下. 数组与其他种类的容器之间的区别有三方面:效率.类型和保存基本类型的能力,当然现在有泛型,保存类型的区别已经不大了. 数组较容器,最大的优点就是效率.在Java中,数组是一种效率最高的存储和随机访问对象引用序列的方式,数组就是一个简单的线性序列,这使得元素访问非常快速,无论使用
-
Java Map简介_动力节点Java学院整理
Map简介 将键映射到值的对象.一个映射不能包含重复的键:每个键最多只能映射到一个值.此接口取代 Dictionary 类,后者完全是一个抽象类,而不是一个接口. Map 接口提供三种collection 视图,允许以键集.值集或键-值映射关系集的形式查看某个映射的内容.映射顺序 定义为迭代器在映射的 collection 视图上返回其元素的顺序.某些映射实现可明确保证其顺序,如 TreeMap 类:另一些映射实现则不保证顺序,如HashMap 类. 注:将可变对象用作映射键时必须格外小心.当对