java中用数组实现环形队列的示例代码

网友投稿 308 2023-01-21

java中用数组实现环形队列的示例代码

本篇文章主要讲述了使用数组实现环形队列的思路以及具体代码

一、队列是什么

我们先来看下百科的解释:

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

总结起来两点:

1.一种线性表

2.添加操作只能在表尾,删除操作在表头(先进先出)

二、实现队列的思路

1.初始化一个空队列

初始化一个大小固定的数组,并将头指针,尾指针都指向下表为0的位置,但其实这种初始化头指针指向的是队首,尾指针指向的是队尾的后一个元素。

2.往队列里添加元素

往队列里添加元素,尾指针后移一位。

一直添加直到队列满

这个时候尾指针已经出现在数组下标外了

3.消费队列元素

每消费一个队列元素,头指针指向的元素出队,并且后移一位

再消费两个

这个时候我们想往队列里继续添加元素,尾指针后移,然后发现出现了假溢出的情况,因为尾指针无法再向后移动,而队列实际上并没有满,我们又无法继续往队列里添加数据。这个时候其实有两种解决方案。

方案一:我们每消费一个元素,其后面的元素都整体往前移动一位,就像我们生活中排队打饭一样,后面的人都往前挪一挪。但这种方案带来的后果是,带来的时间开销太大,因为基本上要操作所有的元素,所以这种方案不可行。

方案二:尾指针在指向下表为最后一个元素时,再添加元素,如果还有空位,就将尾指针重新指向0,头指针在取到下表数组末尾时,如果前面还有元素,头指针也指向0,这就是我们说的环形队列。

三、实现环形队列

1.环形队列示例图

尾指针重新指向零

再添加一个元素

连续消费三个元素,如果前面还有元素,头指针也指向0

这个时候我们发现那个原来熟悉的队列又回来了。

2.代码实现

/**

* description:数组实现环形队列

* author: xiaowang

* */

public class MyQueue {

// 队列最大个数

private int size;

// 元素真实个数

private int number;

// 头指针,指向队列的第一个元素即队头

private int front;

// 尾指针,指向队尾的后一个元素(非队尾)

private int rear;

// 队列具体值

private Object[] values;

// 队列满标记,当队列是满的时候为true

private boolean isFullFlag;

/**构造器*/

public MyQueue(int size){

if (size<0){

throw new RuntimeException("初始化队列时,队列最大元素个数不能为负");

}

this.front = 0;

this.rear = 0;

this.number = 0;

this.isFullFlag = false;

this.size = size;

this.values = new Object[size];

}

/**往队列里添加元素 添加成功返回true 失败返回false*/

public boolean addToQueue(E e){

// 判断队列是否已经满了

if (isFullFlag){

System.out.println("队列已满,无法继续添加元素");

return false;

}

// 添加元素

values[rear] = e;

// 元素个数加一

number++;

// 尾指针后移一位,若已经指向数组最后的下表,则重新指向0

if (rear == size-1){

rear = 0;

}else{

rear++;

}

// 添加完这个元素,判断队列是否已经满了,若满则标记为true

if (rear==front){

isFullFlag = true;

}

return true;

}

/**从队列里取出数据,队头数据*/

public E getFromQueue(){

// 判断队列是否为空

if (number==0||size==0){

System.out.println("队列为空,无法从队列中获取数据");

return null;

}

// 临时变量

E e = (E) values[front];

// 队头置空

values[front] = null;

// 个数减一

number--;

// 头指针后移,若已经指向数组最后的下表,则重新指向0

if (front==size-1){

front = 0;

}else {

front++;

}

// 取队列之前若是满的状态,则更新状态

if (isFullFlag){

isFullFlag = false;

}

return e;

}

/**获取目前有几个元素正在进行排队*/

public int getNumber(){

return number;

}

/**获取队列的最大个数*/

public int getSize(){

return size;

}

/**查看队列在数组里保存的详细情况*/

public String toString(){

StringBuffer valueStr = new StringBuffer();

valueStr.append("[");

for (int i = 0; i < size; i++) {

if (i!=size-1){

valueStr.append(values[i]+",");

}else{

valueStr.append(values[i]+"]");

}

}

return valueStr.toString();

}

}

测试代码

public class TestQueue {

public static void main(String[] args) {

MyQueue queue = new MyQueue(5);

Scanner scanner = new Scanner(System.in);

Scanner scanner2 = new Scanhttp://ner(System.in);

boolean isCan = true;

while (isCan){

System.out.println("欢迎来到小王排队系统,您可以使用以下功能。\n添加:1;取出:2;展示:3;获取排队个数:4;退出:0。");

int flag = scanner.nextInt();

switch (flag){

case 1 :

System.out.println("请输入一个数据:");

String data = scanner2.nextLine();

boolean isSuccess = queue.addToQueue(data);

if (isSuccess){

System.out.println("添加成功~~~");

}

break;

case 2 :

String dataFromQueue = queue.getFromQueue();

if (dataFromQueue!=null){

System.out.println("本次取出的数据为:"+dataFromQueue);

}

break;

case 3 :

System.out.println("队列详情为:\n"+queue.toString());

break;

case 4 :

System.out.println("目前有"+queue.getNumber()+"个元素正在进行排队");

break;

default:

isCan = false;

System.out.println("已退出...");

break;

}

}

}

}

总结

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:短信接口api接口(短信接口api接口是什么)
下一篇:开放api接口事务(开发者api服务)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~