salesforce零基礎學習（七十七）隊列的實現以及應用

隊列和棧簡單的區別為棧是後進先出，隊列是先進先出。隊列也是特殊的線性表，所以隊列也分為順序存儲結構和鏈式存儲結構。本篇主要描述順序存儲結構。

我們先假定一個隊列里有5個元素，當我們添加新元素時，添加到隊列的最後一個位置，所以時間複雜度為O(1)，當我們彈出元素時，需要將隊列頭部的元素彈出，並將後面的元素整體向前面平移，所以時間複雜度為O(n)。如果頻繁的彈出，並且後面的元素向前面平移，這樣對於性能還是影響挺大的，所以我們可以增加頭指針，尾指針，不要求第一個元素必須在index為0的位置，只需要用頭指針記錄當前的頭在哪裡就好。

一.環形隊列：

使用兩個指針操作步驟為：

1.當在隊尾添加元素情況下，隊尾的指針+1，如下圖，隊列中添加a1,a2,a3,a4四個元素。此時隊首front指針指向0，隊尾rear指針指向4；

2.將隊首元素進行彈出，此時隊首指針front指向1，隊尾指向4；

3.將元素a5添加到隊尾，此時隊尾指針指向到了內存長度的外面，但是下標為0還是有空缺的地方，這種情況稱為假溢出。

為了避免假溢出這種情況，我們的做法為當隊列滿了以後，從頭開始繼續存儲隊列，直到隊列滿，即上圖的情況下，a5進入隊列以後，隊尾rear指針指向下標0.

此時針對隊列的空或者滿的判斷，可以通過隊首指針和隊尾指針來判斷：

1.判斷隊列為空的條件為：front = rear，即首指針等於尾指針；

2.因為隊尾可以從頭開始，所以rear可以大於front，也有可能rear小於front。當隊列滿時，我們修改其條件，保留一個元素空間。也就是說，隊列滿時，數組中還有一個空閑單元。這樣我們可以通過下面的表達式來判斷隊列已滿：(rear+1) % QueueSize = front.上圖中當添加完a5以後，隊列中只剩下一個空閑單元我們就假定此隊列已滿。

3.獲取當前隊列的元素個數：（rear - front + QueueSize）% QueueSize

二.代碼實現

代碼中封裝了實現隊列的基本方法，判斷隊列是否為空，是否是滿的隊列，添加元素，彈出元素等。其中針對添加元素，需要考慮隊列是否已經滿的情況，對於彈出元素，需要考慮隊列是否為空隊列的情況。

1 public with sharing class Queue {
2 //數據集
3 private Object datas{get;set;}
4 //棧最大容量
5 private Integer maxSize{get;set;}
6 //隊頭的位置指針
7 private Integer front{get;set;}
8 //隊尾的位置指針
9 private Integer rear{get;set;}
10
11 public Queue {
12 this(10);
13 }
14
15 public Queue(Integer queueSize) {
16 datas = new Object[queueSize];
17 maxSize = queueSize;
18 front = 0;
19 rear = 0;
20 }
21
22 //添加元素到隊列尾部，如果添加成功返回true，添加失敗返回false
23 public Boolean add(Object obj) {
24 if(datas == null) {
25 throw new QueueException("隊列未初始化");
26 }
27 if(full) {
28 throw new QueueException("隊列已滿");
29 }
30 datas[rear] = obj;
31 rear = Math.mod(rear + 1, maxSize);
32 //隊列
33 return true;
34 }
35
36 //返回隊列頭的元素，不彈出頭元素
37 public Object peek {
38 if(datas == null) {
39 throw new QueueException("隊列未初始化");
40 }
41 return datas[front];
42 }
43
44 //彈出頭元素
45 public Object poll {
46 if(datas == null) {
47 throw new QueueException("隊列未初始化");
48 }
49
50 if(empty) {
51 throw new QueueException("隊列為空！");
52 }
53
54 Object returnObj = datas[front];
55 datas[front] = null;
56 front = Math.mod((front + 1),maxSize);
57 return returnObj;
58 }
59
60 public Boolean empty {
61 return front == rear;
62 }
63
64 public Boolean full {
65 return front == Math.mod(rear + 1, maxSize);
66 }
67
68 public Integer size {
69 return Math.mod(rear - front + maxSize ,maxSize);
70 }
71
72 override public String toString {
73 List<Object> objList = new List<Object>;
74 Integer tempRear;
75 if(rear < front) {
76 tempRear = rear + maxSize;
77 } else {
78 tempRear = rear;
79 }
80 for(Integer i = front;i<=tempRear;i++) {
81 if(datas[Math.mod(i, maxSize)] != null) {
82 objList.add(datas[Math.mod(i, maxSize)]);
83 }
84 }
85 return String.join(objList, ",");
86 }
87
88
89 public class QueueException extends Exception{
90
91 }
92 }

三.測試舉例：

1.隊列超出內存情況：初始化一個長度為5的隊列，因為隊列滿的時候，會空出一個元素空間，所以說實際可以添加進隊列的長度為4，當添加eee的時候會報錯，因為隊列已滿。

Queue q = new Queue(5);
q.add("aaa");
q.add("bbb");
q.add("ccc");
q.add("ddd");
q.add("eee");
System.debug(LoggingLevel.INFO, "*** q: " + q);

2.正常使用添加彈出效果，每次彈出是彈出隊首指針對應的元素

Queue q = new Queue(5);
q.add("aaa");
q.add("bbb");
q.add("ccc");
q.add("ddd");
String result = (String)q.poll;
System.debug(LoggingLevel.INFO, "*** result: " + result);
System.debug(LoggingLevel.INFO, "*** : " + "aaa".equals(result));
q.add("eee");
System.debug(LoggingLevel.INFO, "*** q: " + q);

總結：環形隊列適用於已經知道需要分配多大內存的情況，如果不知道需要分配多少內存的情況，可以使用隊列的鏈形結構。隊列在程序中經常使用，比如場景為排隊等的場景，如果有此種先進先出的場景，優先選擇隊列來實現。此篇只是簡單的構造一下隊列的模型，很多地方需要完善，有需要或者感興趣的自行完善一下。篇中有錯誤的地方歡迎指出，有問題歡迎留言。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！