棧與隊列之用java實作隊列

隊列

介紹：

隊列是一種特殊的線性表，特殊之處在于它隻允許在表的前端(front)進行删除操作，而在表的後端(rear)進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行删除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。

隊列的資料元素又稱為隊列元素。在隊列中插入一個隊列元素稱為入隊，從隊列中删除一個隊列元素成為出隊。因為隊列隻允許在一段插入，在另一端删除，是以隻有最早進入隊列的元素才能最先從隊列中删除，故隊列又稱為先進先出(FIFO-first in first out)線性表。

順序隊列中的溢出現象:

(1) "下溢"現象:當隊列為空時，做出隊運算産生的溢出現象。"下溢"是正常現象，常用作程式控制轉移的條件。

(2)"真上溢"現象:當隊列滿時，做進棧運算産生空間溢出的現象。"真上溢"是一種出錯狀态，應設法避免。

(3)"假上溢"現象:由于入隊和出隊操作中，頭尾指針隻增加不減小，緻使被删元素的空間永遠無法重新利用。當隊列中實際的元素個數遠遠小于向量空間的規模時，也可能由于尾指針已超越向量空間的上界而不能做入隊操作。該現象稱為"假上溢"現象。

用java代碼實作：

package com.chenyu.zuo.stackAndQueue;
 
public class QueueQ<T> {
      public int max;//隊列的長度
      public T[] array;//隊列實體
      public int rear;//隊尾指針
      public int front;// 隊頭指針
      public int nItems;//元素的個數
      public QueueQ(int size){
          this.max=size;
          array=(T[])new Object[max];
          front=0;
          rear=-1;
          nItems=0;
      }
      public void insert(T t){  //插入隊尾
          if(rear==max-1){ //已經實際隊尾，從頭開始
              rear=-1;
          }
          array[++rear]=t;
          nItems++;
      }
      public T delete(){//删除隊頭
          T t=array[front++];
          if(front==max){//隊列到尾了
              front=0;
          }
          nItems--;
          return t;
      }
      public T peek(){ //檢視對頭
          return array[front];
      }
      public boolean IsEmpty(){ //是否為空
          return nItems==0;
      }
      public boolean isFull(){  //是否滿了
          return nItems==max;
      }
      public int size(){ //隊列的大小
          return nItems;
      }
      public  void showAll(){//列印出所有
          while(!IsEmpty()){
              System.out.println(delete());
          }
      }
    public static void main(String[] args) {
          QueueQ theQueue = new QueueQ(5);   // 隊列有5個元素
 
           theQueue.insert(10);             // 添加4個元素
           theQueue.insert(20);
           theQueue.insert(30);
           theQueue.insert(40);
           theQueue.delete();               // 移除3個元素
           theQueue.delete();               // (10, 20, 30)
           theQueue.delete();
           theQueue.insert(50);             // 添加4個元素
           theQueue.insert(60);           
           theQueue.insert(70);
           theQueue.insert(80);
           theQueue.showAll();
    }
}      

結果：

40
    50
    60
    70
    80