基于Java數組實現循環(huán)隊列的兩種方法小結

更新時間：2017年12月18日 14:46:15 作者：yjbjingcha

下面小編就為大家分享一篇基于Java數組實現循環(huán)隊列的兩種方法小結，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧

用java實現循環(huán)隊列的方法：

1、添加一個屬性size用來記錄眼下的元素個數。

目的是當head=rear的時候。通過size=0還是size=數組長度。來區(qū)分隊列為空，或者隊列已滿。

2、數組中僅僅存儲數組大小-1個元素，保證rear轉一圈之后不會和head相等。也就是隊列滿的時候。rear+1=head，中間剛好空一個元素。

當rear=head的時候。一定是隊列空了。

隊列(Queue)兩端同意操作的類型不一樣：

能夠進行刪除的一端稱為隊頭，這樣的操作也叫出隊dequeue；

能夠進行插入的一端稱為隊尾，這樣的操作也叫入隊enqueue。

隊列的示意圖

實現隊列時，要注意的是假溢出現象。如上圖的最后一幅圖。

如圖所看到的的假溢出現象

解決的方法：使用鏈式存儲，這顯然能夠。在順序存儲時。我們常見的解決的方法是把它首尾相接，構成循環(huán)隊列。這能夠充分利用隊列的存儲空間。

循環(huán)隊列示意圖：

在上圖中。front指向隊列中第一個元素。rear指向隊列隊尾的下一個位置。

但依舊存在一個問題：當front和rear指向同一個位置時，這代表的是隊空還是隊滿呢？大家能夠想象下這樣的情景。

解決這種問題的常見做法是這種：

使用一標記，用以區(qū)分這樣的易混淆的情形。

犧牲一個元素空間。當front和rear相等時，為空。當rear的下一個位置是front時。為滿。

例如以下圖：

以下我們給出循環(huán)隊列，并採用另外一種方式，即犧牲一個元素空間來區(qū)分隊空和隊滿的代碼.

幾個重點：

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數組實現循環(huán)隊列的兩種方法小結就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: