java循环队列判断为空_Java - 可循环队列

迷南。 2022-11-07 05:27 146阅读 0赞

队列是一种特殊的线性表，是一种先进先出的数据结构。只允许在表的前端进行删除操作，在表的后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

简单的循环队列实现比较容易，队头获取数据、队头弹出获取数据，队尾插入数据。下面来研究一下可以无限循环使用的队列。思路如下：

1、数据结构

int\[\] elements：底层采用数组实现，用来存储队列的所有元素；

maxSize：数组最大容量；

first：队头索引属性；

size：队列有效元素的个数；

1，2，3，4，5

2、算法

这里采用最大容量为5的队列来说明，即maxSize设为5。

(1) 第一次使用队列时，依次添加5个元素：1，2，3，4，5，first指向1，size 大小为5，maxSize为5。

1，2，3，4，5

算法很简单：添加1时，各种为空、队列已满的判断条件暂时省掉；

add(int value) \{

if (size == 0) \{

first = 0；

\}

elements\[size++\] = value;

\}

(2) 调用2次pop()方法弹出获取队列元素，此时队列数据结构如下：

1，2，3，4，5

size为3，first指向3，maxSize始终为5。

pop() \{

size--;

return elements\[first++\];

\}

(3) 此时我们再向队列添加元素6、7，此时队列数据结构如下：

1，2，3，4，5

6，7，3，4，5

访问的顺序应该为：3, 4, 5, 6, 7，其中size为5，first指向3。此时步骤1、2的算法明显不支持数组的循环使用，我们需要利用取模来循环添加数据到数组，具体算法如下：

public classMyQueue \{/\*\*\* 底层数组\*/

private int\[\] elements;/\*\*\* 队列最大容量\*/

private intmaxSize;/\*\*\* 队列头索引\*/

private intfirst;/\*\*\* 队列有效元素的个数\*/

private intsize;public MyQueue(intmaxSize) \{this.maxSize =maxSize;

elements= new int\[maxSize\];

first= -1;

size= 0;

\}/\*\*\* 添加元素

\*

\*@paramvalue\*/

public void add(intvalue) \{if(isFull()) \{throw new RuntimeException("队列已满。");

\}if(isEmpty()) \{

first= 0;

\}//队列未满但是(first + size >= maxSize)时，说明数组elements的first索引之后所有位置已填满，//first索引之前有空位置可以插入元素， 新增元素插入位置算法为：(first + size) % maxSize。

if (first + size >=maxSize) \{

elements\[(first+ size) % maxSize\] =value;

\}else\{

elements\[first+ size\] =value;

\}

size++;

\}/\*\*\* 获取队列元素，只能取队列头，弹出式获取。

\*

\*@return

\*/

public intpop() \{if(isEmpty()) \{throw new RuntimeException("队列为空。");

\}

size--;//first 索引指向maxSize - 1时，即first已到达数组最后的位置，则弹出之后需将first指向第1个元素，//实现数组循环使用

if (first == maxSize -1) \{int tmp =elements\[first\];

first= 0;returntmp;

\}else\{return elements\[first++\];

\}

\}/\*\*\* 获取元素，不弹出

\*

\*@return

\*/

public intpeek() \{if(isEmpty()) \{throw new RuntimeException("队列为空。");

\}returnelements\[first\];

\}public booleanisFull() \{return size ==maxSize;

\}public booleanisEmpty() \{return size <= 0;

\}public voiddisplay() \{if(isEmpty()) \{

System.out.println("Queue is empty.");return;

\}

StringBuilder str= newStringBuilder();for (int i = first; i < first + size; i++) \{if (i >=maxSize) \{

str.append(elements\[i% maxSize\] + ", ");

\}else\{

str.append(elements\[i\]+ ", ");

\}

\}

System.out.println(str.substring(0, str.length() - 2));

\}public intsize() \{returnsize;

\}

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，146人围观）

还没有评论，来说两句吧...

相关阅读

相关循环队列（java）

用数组结构存储的队列 package com.ldm.queue; import java.util.Scanner; /

分手后的思念是犯贱/ 2024年04月08日 08:18/ 0 赞/ 35 阅读

相关 Java实现循环队列

1 public class LoopQueue<E> { 2 3 private E[] data; 4

╰+哭是因爲堅強的太久メ/ 2023年08月17日 16:37/ 0 赞/ 80 阅读

相关循环队列LoopQueue(Java)

循环队列LoopQueue 为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Ci

╰+哭是因爲堅強的太久メ/ 2023年06月30日 15:00/ 0 赞/ 257 阅读

相关 java循环队列判断为空_Java - 可循环队列

队列是一种特殊的线性表，是一种先进先出的数据结构。只允许在表的前端进行删除操作，在表的后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称

迷南。/ 2022年11月07日 05:27/ 0 赞/ 147 阅读

相关循环队列

\define OK 1 \define ERROR 0 \define TRUE 1 \define FALSE 0 \define INFEASIBLE -

朴灿烈づ我的快乐病毒、/ 2022年08月25日 05:28/ 0 赞/ 160 阅读

相关循环队列

![2012_11_22_05.jpg][] 我们来讨论第二种方法，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是

客官°小女子只卖身不卖艺/ 2022年08月04日 14:42/ 0 赞/ 168 阅读

相关循环队列

2016年7月31日15:35:10 队列是一种操作受限的线性表,队列是一种只允许在表头删除,在表尾进行插入的线性表, 允许插入的一端称

港控/mmm°/ 2022年07月16日 13:29/ 0 赞/ 177 阅读

相关循环队列

include<stdio.h> define maxsize 10 typedef int Datatype; typedef struct

ゝ一世哀愁。/ 2022年06月16日 13:08/ 0 赞/ 174 阅读

相关循环队列中判断队满队空（数组实现的循环队列）

转载自：http://blog.csdn.net/u010429311/article/details/51043149 在引用循环队列前，我们需要了解队列是如何线性实现的。

川长思鸟来/ 2022年06月10日 07:58/ 0 赞/ 152 阅读

相关 java队列实现（顺序队列、链式队列、循环队列）

双向顺序队列ArrayDeque和双向链式队列LinkedList，JDK已经包含，在此略。ArrayDeque包括顺序栈和顺序队列，LinkedList包含链式栈和链式队列。

青旅半醒/ 2022年06月09日 13:59/ 0 赞/ 227 阅读