1. 隊列的介紹

隊列 (Queue)是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊列具有先進先出(Fist In Fist Out， 縮寫為FIFO)的特性。在隊列中，允許插入的一端叫做隊尾(rear)，允許刪除的一端則稱為隊頭(front)。 在隊列中插入一個新元素的操作簡稱為進隊或入隊，新元素進隊后就成為新的隊尾元素；從隊列中刪除一個元素的操作簡稱為出隊或離隊，當元素出隊后，其后繼元素就成為新的隊頭元素

假設隊列為q=(a1，a2，…，an)，那么a1就是隊頭元素，an則是隊尾元素。隊列中的元素是按照a1，a2，…，an的順序進入的， 退出隊列也必須按照同樣的次序依次出隊，也就是說，只有在a1，a2，…，an-1都離開隊列之后，an才能退出隊列。

隊列（Queue），是一種線性存儲結構。它有以下幾個特點：

• 隊列中數據是按照”先進先出（FIFO, First-In-First-Out）”方式進出隊列的。
• 隊列只允許在”隊首”進行刪除操作，而在”隊尾”進行插入操作。

隊列通常包括的兩種操作：入隊列 和 出隊列。

1.1 隊列的示意圖

隊列中有10，20，30共3個數據。

1.2 出隊列

出隊列前：隊首是10，隊尾是30。
出隊列后：出隊列(隊首)之后。隊首是20，隊尾是30。

1.3 入隊列

入隊列前：隊首是20，隊尾是30。
入隊列后：40入隊列(隊尾)之后。隊首是20，隊尾是40。

2. 隊列的順序存儲結構

隊列的順序存儲結構稱為順序隊列。順序隊列可以利用一個一維數組和兩個指針來實現。一維數組用來存儲當前隊列中的所有元素，兩個指針front和rear分別指向當前隊列的隊首元素和隊尾元素，分別稱為隊首指針和隊尾指針。

3. 隊列的鏈接存儲結構

隊列的鏈接存儲結構是用一個單鏈表存放隊列元素的。隊列的鏈接存儲結構稱為鏈隊列。由于隊列只允許在表尾進行插入操作、在表頭進行刪除操作，因此，鏈隊需設置兩個指針：隊頭指針front和隊尾指針rear，分別指向單鏈表的第一個結點(表的頭結點)和最后一個結點(隊尾結點)。

4. 隊列的Java實現

JDK包Queue中的也提供了”隊列”的實現。JDK中的Queue接口就是”隊列”，它的實現類也都是隊列，用的最多的是LinkedList

4.1 Java實現一

數組實現的隊列，能存儲任意類型的數據

/*** Java : 數組實現“隊列”，只能存儲int數據*/ public class ArrayQueue {private int[] mArray;private int mCount;public ArrayQueue(int sz) {mArray = new int[sz];mCount = 0;}// 將val添加到隊列的末尾public void add(int val) {mArray[mCount++] = val;}// 返回“隊列開頭元素”public int front() {return mArray[0];}// 返回“棧頂元素值”，并刪除“棧頂元素”public int pop() {int ret = mArray[0];mCount--;for (int i=1; i<=mCount; i++)mArray[i-1] = mArray[i];return ret;}// 返回“棧”的大小public int size() {return mCount;}// 返回“棧”是否為空public boolean isEmpty() {return size()==0;}public static void main(String[] args) {int tmp=0;ArrayQueue astack = new ArrayQueue(12);// 將10, 20, 30 依次推入棧中astack.add(10);astack.add(20);astack.add(30);// 將“棧頂元素”賦值給tmp，并刪除“棧頂元素”tmp = astack.pop();System.out.printf("tmp=%d\n", tmp);// 只將“棧頂”賦值給tmp，不刪除該元素.tmp = astack.front();System.out.printf("tmp=%d\n", tmp);astack.add(40);System.out.printf("isEmpty()=%b\n", astack.isEmpty());System.out.printf("size()=%d\n", astack.size());while (!astack.isEmpty()) {System.out.printf("size()=%d\n", astack.pop());}} }

運行結果

tmp=10 tmp=20 isEmpty()=false size()=3 size()=20 size()=30 size()=40

結果說明：ArrayQueue是通過數組實現的隊列，而且ArrayQueue中使用到了泛型，因此它支持任意類型的數據。

4.2 Java實現二

Java的 Collection集合 中自帶的”隊列”(LinkedList)的示例

import java.util.Stack;/*** 用“棧”實現隊列*/ public class StackList<T> {// 向隊列添加數據時：(01) 將“已有的全部數據”都移到mIn中。 (02) 將“新添加的數據”添加到mIn中。private Stack<T> mIn = null;// 從隊列獲取元素時：(01) 將“已有的全部數據”都移到mOut中。(02) 返回并刪除mOut棧頂元素。private Stack<T> mOut = null;// 統計計數private int mCount = 0;public StackList() {mIn = new Stack<T>();mOut = new Stack<T>();mCount = 0;}private void add(T t) {// 將“已有的全部數據”都移到mIn中while (!mOut.empty())mIn.push(mOut.pop());// 將“新添加的數據”添加到mIn中mIn.push(t);// 統計數+1mCount++;}private T get() {// 將“已有的全部數據”都移到mOut中while (!mIn.empty())mOut.push(mIn.pop());// 統計數-1mCount--;// 返回并刪除mOut棧頂元素return mOut.pop();}private int size() {return mCount;}private boolean isEmpty() {return mCount==0;}public static void main(String[] args) {StackList slist = new StackList();// 將10, 20, 30 依次推入棧中slist.add(10);slist.add(20);slist.add(30);System.out.printf("isEmpty()=%b\n", slist.isEmpty());System.out.printf("size()=%d\n", slist.size());while(!slist.isEmpty()) {System.out.printf("%d\n", slist.get());}} }

運行結果

tmp=10 tmp=20 isEmpty()=false size()=3 tmp=20 tmp=30 tmp=40

4.3 隊列的數組實現

// Queue.java // demonstrates queue // to run this program: C>java QueueApp class Queue{private int maxSize;private long[] queArray;private int front;private int rear;private int nItems; //--------------------------------------------------------------public Queue(int s) // constructor{maxSize = s;queArray = new long[maxSize];front = 0;rear = -1;nItems = 0;} //--------------------------------------------------------------public void insert(long j) // put item at rear of queue{if(rear == maxSize-1) // deal with wraparoundrear = -1;queArray[++rear] = j; // increment rear and insertnItems++; // one more item} //--------------------------------------------------------------public long remove() // take item from front of queue{long temp = queArray[front++]; // get value and incr frontif(front == maxSize) // deal with wraparoundfront = 0;nItems--; // one less itemreturn temp;} //--------------------------------------------------------------public long peekFront() // peek at front of queue{return queArray[front];} //--------------------------------------------------------------public boolean isEmpty() // true if queue is empty{return (nItems==0);} //--------------------------------------------------------------public boolean isFull() // true if queue is full{return (nItems==maxSize);} //--------------------------------------------------------------public int size() // number of items in queue{return nItems;} //--------------------------------------------------------------} // end class Queue class QueueApp{public static void main(String[] args){Queue theQueue = new Queue(5); // queue holds 5 itemstheQueue.insert(10); // insert 4 itemstheQueue.insert(20);theQueue.insert(30);theQueue.insert(40);theQueue.remove(); // remove 3 itemstheQueue.remove(); // (10, 20, 30)theQueue.remove();theQueue.insert(50); // insert 4 more itemstheQueue.insert(60); // (wraps around)theQueue.insert(70);theQueue.insert(80);while( !theQueue.isEmpty() ) // remove and display{ // all itemslong n = theQueue.remove(); // (40, 50, 60, 70, 80)System.out.print(n);System.out.print(" ");}System.out.println("");} // end main()} // end class QueueApp

4.4 隊列的鏈表實現

// linkQueue.java // demonstrates queue implemented as double-ended list // to run this program: C>java LinkQueueApp class Link{public long dData; // data itempublic Link next; // next link in list // -------------------------------------------------------------public Link(long d) // constructor{ dData = d; } // -------------------------------------------------------------public void displayLink() // display this link{ System.out.print(dData + " "); } // -------------------------------------------------------------} // end class Link class FirstLastList{private Link first; // ref to first itemprivate Link last; // ref to last item // -------------------------------------------------------------public FirstLastList() // constructor{first = null; // no items on list yetlast = null;} // -------------------------------------------------------------public boolean isEmpty() // true if no links{ return first==null; } // -------------------------------------------------------------public void insertLast(long dd) // insert at end of list{Link newLink = new Link(dd); // make new linkif( isEmpty() ) // if empty list,first = newLink; // first --> newLinkelselast.next = newLink; // old last --> newLinklast = newLink; // newLink <-- last} // -------------------------------------------------------------public long deleteFirst() // delete first link{ // (assumes non-empty list)long temp = first.dData;if(first.next == null) // if only one itemlast = null; // null <-- lastfirst = first.next; // first --> old nextreturn temp;} // -------------------------------------------------------------public void displayList(){Link current = first; // start at beginningwhile(current != null) // until end of list,{current.displayLink(); // print datacurrent = current.next; // move to next link}System.out.println("");} // -------------------------------------------------------------} // end class FirstLastList class LinkQueue{private FirstLastList theList; //--------------------------------------------------------------public LinkQueue() // constructor{ theList = new FirstLastList(); } // make a 2-ended list //--------------------------------------------------------------public boolean isEmpty() // true if queue is empty{ return theList.isEmpty(); } //--------------------------------------------------------------public void insert(long j) // insert, rear of queue{ theList.insertLast(j); } //--------------------------------------------------------------public long remove() // remove, front of queue{ return theList.deleteFirst(); } //--------------------------------------------------------------public void displayQueue(){System.out.print("Queue (front-->rear): ");theList.displayList();} //--------------------------------------------------------------} // end class LinkQueue class LinkQueueApp{public static void main(String[] args){LinkQueue theQueue = new LinkQueue();theQueue.insert(20); // insert itemstheQueue.insert(40);theQueue.displayQueue(); // display queuetheQueue.insert(60); // insert itemstheQueue.insert(80);theQueue.displayQueue(); // display queuetheQueue.remove(); // remove itemstheQueue.remove();theQueue.displayQueue(); // display queue} // end main()} // end class LinkQueueApp

4.5 優先級隊列

// priorityQ.java // demonstrates priority queue // to run this program: C>java PriorityQApp class PriorityQ{// array in sorted order, from max at 0 to min at size-1private int maxSize;private long[] queArray;private int nItems; //-------------------------------------------------------------public PriorityQ(int s) // constructor{maxSize = s;queArray = new long[maxSize];nItems = 0;} //-------------------------------------------------------------public void insert(long item) // insert item{int j;if(nItems==0) // if no items,queArray[nItems++] = item; // insert at 0else // if items,{for(j=nItems-1; j>=0; j--) // start at end,{if( item > queArray[j] ) // if new item larger,queArray[j+1] = queArray[j]; // shift upwardelse // if smaller,break; // done shifting} // end forqueArray[j+1] = item; // insert itnItems++;} // end else (nItems > 0)} // end insert() //-------------------------------------------------------------public long remove() // remove minimum item{ return queArray[--nItems]; } //-------------------------------------------------------------public long peekMin() // peek at minimum item{ return queArray[nItems-1]; } //-------------------------------------------------------------public boolean isEmpty() // true if queue is empty{ return (nItems==0); } //-------------------------------------------------------------public boolean isFull() // true if queue is full{ return (nItems == maxSize); } //-------------------------------------------------------------} // end class PriorityQ class PriorityQApp{public static void main(String[] args){PriorityQ thePQ = new PriorityQ(5);thePQ.insert(30);thePQ.insert(50);thePQ.insert(10);thePQ.insert(40);thePQ.insert(20);while( !thePQ.isEmpty() ){long item = thePQ.remove();System.out.print(item + " "); // 10, 20, 30, 40, 50} // end whileSystem.out.println("");} // end main() //-------------------------------------------------------------} // end class PriorityQApp

4.6 隊列的應用

6個人圍成圈數數，數到3的人退出，問最后退出的人是誰？

public class MyQueue {private Object datas[];private int pushIndex;//入隊的下標private int popIndex; //出隊的下標private int counts;//記錄數據的個數public MyQueue(int size){datas = new Object[size];}public MyQueue(){this(10);}public boolean isEmpty(){return counts == 0;}public String toString(){StringBuilder mess = new StringBuilder();for (int i = popIndex; i <= counts; i++) {mess.append(datas[i % datas.length] + ",");}return mess + "";}public boolean isFull(){return counts == datas.length;}/*** 入隊列* @param data*/public void push(Object data) {if (isFull()) {return;}datas[pushIndex++ % datas.length] = data;counts++;}public Object popup(){Object data = datas[popIndex++ % datas.length];counts--;return data;} } public class TestApp {public static void main(String[] args) {//初始化隊列MyQueue queue = new MyQueue(6);//六個人入隊for (int i = 0;i < 6; i++) {queue.push(i + 1);}//數數int counts = 0;//計數器while (!queue.isEmpty()) {Object d = queue.popup();counts++;//判斷if (counts % 3 == 0) {System.out.println(d);} else {queue.push(d);//再放進隊列}}} }

4.7 循環隊列

原文出處：http://www.cnblogs.com/skywang12345/p/3562279.html

總結

以上是生活随笔為你收集整理的Java数据结构与算法：队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。