这里有新鲜出炉的 Java 并发编程示例,程序狗速度看过来!
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表。 这篇文章详细给大家介绍了 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 学院整理),希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 PHPERZ 网站的支持!
来源: http://www.phperz.com/article/17/1217/357667.html