基于Java数组实现循环队列的两种方法小结

发布时间：2020-09-09 08:09:29 作者：yjbjingcha
来源：脚本之家阅读：217

用java实现循环队列的方法：

1、添加一个属性size用来记录眼下的元素个数。

目的是当head=rear的时候。通过size=0还是size=数组长度。来区分队列为空，或者队列已满。

2、数组中仅仅存储数组大小-1个元素，保证rear转一圈之后不会和head相等。也就是队列满的时候。rear+1=head，中间刚好空一个元素。

当rear=head的时候。一定是队列空了。

队列(Queue)两端同意操作的类型不一样：

能够进行删除的一端称为队头，这样的操作也叫出队dequeue；

能够进行插入的一端称为队尾，这样的操作也叫入队enqueue。

队列的示意图

基于Java数组实现循环队列的两种方法小结

实现队列时，要注意的是假溢出现象。如上图的最后一幅图。

如图所看到的的假溢出现象

基于Java数组实现循环队列的两种方法小结

解决的方法：使用链式存储，这显然能够。在顺序存储时。我们常见的解决的方法是把它首尾相接，构成循环队列。这能够充分利用队列的存储空间。

循环队列示意图：

基于Java数组实现循环队列的两种方法小结

在上图中。front指向队列中第一个元素。rear指向队列队尾的下一个位置。

但依旧存在一个问题：当front和rear指向同一个位置时，这代表的是队空还是队满呢？大家能够想象下这样的情景。

解决这种问题的常见做法是这种：

使用一标记，用以区分这样的易混淆的情形。

牺牲一个元素空间。当front和rear相等时，为空。当rear的下一个位置是front时。为满。

例如以下图：

基于Java数组实现循环队列的两种方法小结

以下我们给出循环队列，并採用另外一种方式，即牺牲一个元素空间来区分队空和队满的代码.

几个重点：

1、front指向队头。rear指向队尾的下一个位置。

2、队为空的推断：front==rear；队为满的推断：(rear+1)%MAXSIZE==front。

import java.io.*;
  public class QueueArray {  
  Object[] a; //对象数组，队列最多存储a.length-1个对象  
  int front; //队首下标  
  int rear;  //队尾下标  
  public QueueArray(){  
    this(10); //调用其他构造方法  
  }  
  public QueueArray(int size){  
    a = new Object[size];  
    front = 0;  
    rear =0;  
  }  
  /** 
   * 将一个对象追加到队列尾部 
   * @param obj 对象 
   * @return 队列满时返回false,否则返回true 
   */ 
  public boolean enqueue(Object obj){  
    if((rear+1)%a.length==front){  
      return false;  
    }  
    a[rear]=obj;  
    rear = (rear+1)%a.length;  
    return true;  
  }  
  /** 
   * 队列头部的第一个对象出队 
   * @return 出队的对象，队列空时返回null 
   */ 
  public Object dequeue(){  
    if(rear==front){  
      return null;  
    }  
    Object obj = a[front];  
    front = (front+1)%a.length;  
    return obj;  
  }  
  public static void main(String[] args) {  
    QueueArray q = new QueueArray(4);  
    System.out.println(q.enqueue("张三"));  
    System.out.println(q.enqueue("李斯"));  
    System.out.println(q.enqueue("赵五"));  
    System.out.println(q.enqueue("王一"));//无法入队列，队列满  
    for(int i=0;i<4;i++){  
      System.out.println(q.dequeue());  
    }  
  }  
}

以上这篇基于Java数组实现循环队列的两种方法小结就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持亿速云。

基于Java数组实现循环队列的两种方法小结

相关阅读