利用佇列結構實現業務辦理自動叫號

文章導讀

【佇列結構和棧結構一樣，也是一種特殊的線性表。佇列結構只允許在表的一端插入元素，而在另一端刪除元素，佇列結構的這種特性非常類似於現實生活中的排隊，後來的人在隊尾入隊，辦完業務的人在隊首出隊。本文主要討論用佇列結構解決業務辦理自動叫號問題】

1、認識佇列結構

在現實生活中，當人們去銀行、行政大廳等企業和辦事機構辦理業務時，都需要從排隊機領取排隊號碼，等待叫號。類似排隊機這樣的程式，其內部資料結構一般都會用到佇列結構。

佇列結構和棧結構一樣，都是特殊的線性表，但也有不同之處。棧結構只允許在表的一端插入和刪除資料，而佇列結構只允許在表的一端插入元素，而在另一端刪除元素。允許插入元素的一端稱為隊尾，允許刪除元素的一端稱為隊頭。若給定一佇列：

S = （a1，a2，……，an）

則稱a1是隊頭元素，an是隊尾元素，表中元素按an，……a2，a1的次序入隊，出隊的順序是a1，a2，……，an。也就是說，佇列結構的元素訪問原則是先進先出，因此佇列結構也稱為先進先出的線性表，如下圖所示。

圖 1 佇列結構

佇列結構運算有入隊、出隊、訪問隊頭元素、置隊空四種基本運算。

（1）入隊運算

該運算在長度為n的佇列中，將元素置入隊尾。若佇列已滿，返回出錯資訊。

（2）出隊運算

該運算在長度為n的佇列中，取出隊首元素，並從隊首刪除該元素。若佇列為空，返回出錯資訊。

（3）訪問隊首元素

該運算在長度為n的佇列中，取出隊首元素。若佇列為空，返回出錯資訊。

（4）置隊空

該運算將佇列設定為空佇列。

在程式中要實現佇列結構，採用線性連結串列儲存結構最為合適。每次的入隊和出隊運算無需移動佇列元素，佇列長度也可以動態變化。在Java語言中，可以使用LinkedList類構建佇列結構。LinkedList類每個結點用內部類Node表示，LinkedList透過first和last引用分別指向連結串列的第一個和最後一個元素，當連結串列為空時，first和last都為NULL值。

例1：使用Java語言建立一個佇列

Queue佇列類使用泛型定義，可以儲存不同型別的佇列元素。使用LinkedList線性連結串列作為佇列結構，實現了出隊、入隊、置空佇列、訪問佇列頭部、遍歷佇列運算。出隊運算在返回佇列頭部元素的同時，需要從佇列中刪除該元素，入隊運算需要把元素加入到隊尾。出隊和入隊演算法的時間複雜度都為O（1）。

Queue佇列類的測試程式程式碼如下。

2、用佇列結構實現業務辦理自動叫號

前面討論了佇列結構的實現及運算，接下來探討一下如何用佇列實現業務辦理的自動叫號。

業務辦理自動叫號有兩個關鍵事件。一個事件是取號，當新的客戶辦理業務時，需要在排隊機取號；一個事件是叫號，當業務辦理視窗開始辦理新業務時，需要叫號。取號事件是入隊操作，叫號事件是出隊操作。

取號事件和叫號事件處理方法中的queue物件是前面介紹的佇列Queue類，length是當天辦理業務總客戶數。inQueue是取號事件處理方法，傳入引數為排隊號，queue將傳入的排隊號加入佇列，length做加1操作，並返回length。outQueue是叫號事件處理方法，出隊之前需要判斷佇列是否為空，如佇列為空，則返回-1，若佇列不為空，queue做出隊操作，並返回排隊號。

業務辦理自動叫號類程式碼如下。

QueueOffer類為程式主要處理類，類的主要方法為取號和叫號事件處理，並內建了佇列queue類，用於內部的佇列結構。QueueOffer類主要完成取號和叫號事件的處理，程式還需要模擬取號和叫號事件的隨機發生，模擬取號和叫號事件的隨機發生，可以採用鍵盤輸入模擬。假定使用者輸入“add”表示新客戶到達取號，使用者輸入數字1至6表示辦理業務的工作視窗叫號，使用者輸入“exit”表示停止業務辦理。模擬程式程式碼如下。

文章小結

（1）佇列結構是一種運算受限的線性表，插入運算和刪除運算只能在表頭和表尾進行。允許插入的一端稱為隊尾，允許刪除的一端稱為隊首，插入稱為入隊操作，刪除稱為出隊操作。現實生活中的排隊非常類似於佇列結構，後來的人要加入排隊序列得需要從隊尾加入，業務辦理完畢得需要從隊首出隊。因此，佇列結構也稱為先進先出表。

（2）取號和叫號是業務辦理自動叫號程式的兩個主要事件，取號是入隊操作，叫號是出隊操作。在Java語言中，一般使用LinkedList來實現佇列結構，LinkedList類是線性連結串列結構，入隊和出隊運算無需移動佇列元素，佇列長度也可以動態變化。