快捷導(dǎo)航

java編程隊(duì)列數(shù)據(jù)結(jié)構(gòu)代碼示例

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

這篇文章主要介紹了java編程隊(duì)列數(shù)據(jù)結(jié)構(gòu)代碼示例，簡單介紹了隊(duì)列的相關(guān)基礎(chǔ)知識(shí)，然后通過實(shí)例向大家展示其實(shí)現(xiàn)方法，具有一定參考價(jià)值，需要的朋友可以了解下。

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

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

所以隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)（FIFO）。

編程實(shí)現(xiàn)對(duì)循環(huán)鏈隊(duì)列的入隊(duì)和出隊(duì)操作。

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

⑵將數(shù)據(jù)元素e入隊(duì)，并輸出入隊(duì)后的隊(duì)列中各元素值。

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

當(dāng)隊(duì)列的插入數(shù)據(jù)時(shí)，Rear箭頭一直往上走，插入到表的最大下標(biāo)的位置后停止。在移除數(shù)據(jù)的時(shí)候，front箭頭也會(huì)一直往上走。

這可能跟現(xiàn)實(shí)中的人們在電影院買電影票的情況有點(diǎn)不符合，一般是買完票，人就往前走，繼續(xù)買票，隊(duì)伍總是向前移動(dòng)的。

在計(jì)算機(jī)中，隊(duì)列每刪除一個(gè)數(shù)據(jù)項(xiàng)后，其他數(shù)據(jù)也可以繼續(xù)往移動(dòng)，但如此一來，處理很大的數(shù)據(jù)的時(shí)候，這樣做的效率很低下，因?yàn)槊看蝿h除一個(gè)數(shù)據(jù)就要將剩余的所有數(shù)據(jù)往前移動(dòng)。

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

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

這個(gè)就是------循環(huán)隊(duì)列：

package DataStructure;
 
/**
 * Created by Hubbert on 2017/11/11.
 */
public class Queue {
 
  private int [] arr ;
  private int front ; //隊(duì)頭指針
  private int rear ; //隊(duì)尾指針
  private int nItems ;//隊(duì)列中的個(gè)數(shù)
  private int maxSize;//隊(duì)列長度
 
  //使用構(gòu)造函數(shù)進(jìn)行初始化
  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);//判斷隊(duì)列是否已滿
  }
 
  public boolean isEmpty(){
    return (nItems == 0);//判斷隊(duì)列是否為空
  }
 
  //插入
  public void insert( int number ){
    if(!isFull()){
      //處理循環(huán)隊(duì)列
      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)隊(duì)列
      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("-----------先刪除隊(duì)列中前兩個(gè)數(shù)據(jù)------------");
    System.out.println("Front--->Rear:");
    for( int i =0 ; i < 2 ; i++ ){
      System.out.print(queue.remove() + " ");
    }
 
    System.out.println("");
    System.out.println("-----------繼續(xù)使用隊(duì)列------------");
    System.out.println("Front--->Rear:");
    queue.insert(1);
    queue.insert(2);
    while (!queue.isEmpty()){
      System.out.print(queue.remove() + " ");
    }
  }
}

結(jié)果如下：