隊列的基本概念
隊列（簡稱隊）也是一種特殊的線性表，隊列的數據元素以及數據元素間的邏輯關系和線性表完全相同。差別是線性表允許在任意位置插入和刪除，而隊列只允許在一端進行插入操作而在另一端進行刪除操作。
隊列中允許插入操作的一端稱為隊尾，允許進行刪除操作的一端稱為隊頭。隊列的插入操作通常稱為入隊列，隊列的刪除操作通常稱為出隊列。
根據隊列的定義，每次入隊列的數據元素都放在原來的隊尾之后成為新的隊尾元素，每次出隊列的數據元素都是隊頭元素。這樣，最先入隊列的數據元素總是最先出隊列。最后入隊列的數據元素總是最后出隊列，所以隊列也稱為先進先出表。
隊列的抽象數據類型
1、數據集合：隊列的數據集合可以表示為a1,a2,a3,a4，每個數據元素的數據類型可以是任意類類型
2、操作集合：1、入隊列操作（append()）
2、出隊列操作（delete()）
3、取隊列的頭元素(getFront())
4、判斷隊列是否為空(isEmpty())
源代碼------順序存儲結構
隊列接口代碼
package com.queue; //隊列接口 public interface Queue { //入隊列操作 public void append(Object object); //出隊列操作 public Object delete(); //取隊列頭元素 public Object getFront(); //判斷隊列是否為空 public boolean isEmpty(); } |
隊列接口實例化類
package com.queue; public class SeqQueue implements Queue { //相關屬性和構造方法 //默認大小 static final int defauleSize=10; //隊頭 int front; //隊尾 int rear; //隊列元素個數統計 int count; //隊列初始化大小 int maxSize; //隊列數據信息 Object[] data; public void initiate(int sz){ maxSize=sz; front=rear=0; count=0; data=new Object[sz]; } public SeqQueue(){ initiate(defauleSize); } public SeqQueue(int length){ initiate(length); } @Override public void append(Object object) { // TODO Auto-generated method stub if(count>0&&front==rear){ return; } data[rear]=object; //求模運算 rear=(rear+1)%maxSize; count++; } @Override public Object delete() { // TODO Auto-generated method stub Object object=null; if(count==0){ object="404"; return object; }else{ object=data[front]; //求模運算 front=(front+1)%maxSize; count--; return object; } } @Override public Object getFront() { // TODO Auto-generated method stub Object object=null; if(count==0){ object="404"; return object; }else{ return data[front]; } } @Override public boolean isEmpty() { // TODO Auto-generated method stub return count!=0; } }
|
實驗結果：
package com.queue; public class QueueTest { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub SeqQueue queue=new SeqQueue(); //判斷隊列是否為空 boolean target=queue.isEmpty(); System.out.println("隊列是否為空："+target); //入隊列 queue.append("c"); queue.append("c++"); queue.append("c#"); queue.append("object-c"); queue.append("php"); queue.append("java"); queue.append("ruby"); queue.append("javascript"); queue.append("ext"); queue.append("jquery"); //再次判斷隊列是否為空 boolean targets=queue.isEmpty(); System.out.println("再次判斷隊列是否為空："+targets); //出隊列 Object object=queue.delete(); System.out.println("出隊列的元素是："+object); //取隊列頭元素 Object front=queue.getFront(); System.out.println("隊列頭元素是:"+front); } } |
圖片展示：
源代碼--------鏈式存儲結構