java編程隊列數據結構代碼示例

更新時間：2017年11月15日 15:22:04 作者：Hubbert01

這篇文章主要介紹了java編程隊列數據結構代碼示例，簡單介紹了隊列的相關基礎知識，然后通過實例向大家展示其實現方法，具有一定參考價值，需要的朋友可以了解下。

隊列是一種特殊的線性表，只允許在表的前端進行刪除，在表的后端進行插入，表的前端稱為（front）隊頭，表的后端稱為（rear）隊尾。

所以隊列跟生活的場景很是相似，在電影院買電影票，人們排成一排，第一個人進入隊尾最先到達隊頭后買票進入影院，后面排隊的人按照排隊的次序買到票后進入影院。

所以隊列是一種先進先出的數據結構（FIFO）。

編程實現對循環(huán)鏈隊列的入隊和出隊操作。

⑴根據輸入的隊列長度n和各元素值建立一個帶頭結點的循環(huán)鏈表表示的隊列（循環(huán)鏈隊列），并且只設一個尾指針來指向尾結點，然后輸出隊列中各元素值。

⑵將數據元素e入隊，并輸出入隊后的隊列中各元素值。

⑶將循環(huán)鏈隊列的隊首元素出隊，并輸出出隊元素的值和出隊后隊列中各元素值。

當隊列的插入數據時，Rear箭頭一直往上走，插入到表的最大下標的位置后停止。在移除數據的時候，front箭頭也會一直往上走。

這可能跟現實中的人們在電影院買電影票的情況有點不符合，一般是買完票，人就往前走，繼續(xù)買票，隊伍總是向前移動的。

在計算機中，隊列每刪除一個數據項后，其他數據也可以繼續(xù)往移動，但如此一來，處理很大的數據的時候，這樣做的效率很低下，因為每次刪除一個數據就要將剩余的所有數據往前移動。

在刪除數據的時候，隊頭（Front）前面的位置就會留空，但由于隊尾（Rear）和隊頭（Front）這兩個箭頭都一直往上走，所以沒能繼續(xù)利用到前面空單元的存儲空間。

為了避免隊列不滿卻不能繼續(xù)插入新數據的情況，解決隊列能循環(huán)利用的方法就是，當Rear箭頭和Front箭頭到達最大下標的位置后，重新將它的位置移動到，表的最初始的位置。

這個就是------循環(huán)隊列：

package DataStructure;
 
/**
 * Created by Hubbert on 2017/11/11.
 */
public class Queue {
 
  private int [] arr ;
  private int front ; //隊頭指針
  private int rear ; //隊尾指針
  private int nItems ;//隊列中的個數
  private int maxSize;//隊列長度
 
  //使用構造函數進行初始化
  public Queue( int maxSize ){
    this.maxSize = maxSize ;
    this.arr = new int [this.maxSize];
    this.nItems = 0 ;
    this.front = 0;
    this.rear = -1 ;
  }
 
  public boolean isFull(){
    return (nItems == maxSize);//判斷隊列是否已滿
  }
 
  public boolean isEmpty(){
    return (nItems == 0);//判斷隊列是否為空
  }
 
  //插入
  public void insert( int number ){
    if(!isFull()){
      //處理循環(huán)隊列
      if( rear == (maxSize -1)){
        rear = -1;
      }
      arr[++rear] = number ;
      nItems++;
    }else{
      System.out.println("The Queue is full!!");
    }
  }
 
  //刪除
  public int remove(){
    if(!isEmpty()){
      //處理循環(huán)隊列
      if( front == maxSize ){
        front = 0;
      }
      nItems--;
      return arr[front++];
 
    } else {
      System.err.println ("The Queue is Empty!!");
      return -1;
    }
  }
 
  public static void main(String [] args){
    Queue queue = new Queue(5);
    queue.insert(22);
    queue.insert(33);
    queue.insert(44);
    queue.insert(55);
    queue.insert(66);
 
    System.out.println("-----------先刪除隊列中前兩個數據------------");
    System.out.println("Front--->Rear:");
    for( int i =0 ; i < 2 ; i++ ){
      System.out.print(queue.remove() + " ");
    }
 
    System.out.println("");
    System.out.println("-----------繼續(xù)使用隊列------------");
    System.out.println("Front--->Rear:");
    queue.insert(1);
    queue.insert(2);
    while (!queue.isEmpty()){
      System.out.print(queue.remove() + " ");
    }
  }
}

結果如下：