簡介
佇列 (Queue) 中文也翻作隊列，顧名思義是一種像排隊一樣的概念，以生活中的情況為例如下圖
人們一個接一個的從隊伍後面加入排隊，而窗口的服務人員則從最前面的民眾一個接一個處理事務；當然現實生活是會有中途離開的人，而在程式世界裡面一般情況是不會有。
在這個模式下我們可以知道他是一種先進先出 (First-In-First-Out, FIFO) 的排程，而在此資料結構中至少會實作兩個操作：
- enqueue：將資料放入佇列尾端。(註：C++ 中用 push、Java 用 offer、也有 add 等不同的用字)
- dequeue：取出佇列前端之資料。(註：C++ 中用 pop、Java 用 poll、也有 remove 等不同的用字)
有時候也會多實作一些額外的操作以方便使用，例如：
- peek：看佇列前端的資料而不取出。(註：也有 front 等不同的用字)
- size：取得佇列的數目。
在實作上一般使用連結串列 (LinkedList) 來實作，使用陣列同樣可以達成，但較為複雜：
連結串列
用指標將資料串起來，將新的東西不斷接在最後面，而取出時則移除最前面的東西即可。由於加入和移除的端點不同，如果只記住第一個節點的話，在加入資料時，必須每次都向後找到最後一個節點會耗費許多時間，為了讓加入和移除都在 O(1) 的時間完成，可以同時記錄最前面和最後面的節點。
陣列
佇列建立時即建立一個陣列，但由於加入和刪除的端點不同，所以我們需要一個索引來記錄開始位址和一個索引來記錄結束位址，如下圖所示：
然而我們會發現，不斷的 enqueue 和 dequeue 之後，佇列的範圍會慢慢往後移，直到陣列的盡頭，為了永續經營，我們必須重新使用前面的部分，所以我們還必須多進行一個轉換的動作。
實作上我只有額外多紀錄開始索引，而利用序列數目、陣列長度和簡單的取餘數方式來算出結束索引，公式如下：
1
| 下一個佇列索引位址 = (開始索引位址 + 序列數目) % 陣列長度
|
以上圖情況為例：
1
2
3
| (0 + 3) % 6 = 3
(3 + 3) % 6 = 0
(4 + 3) % 6 = 1
|
另外，在實作佇列擴充，進行陣列的複製動作時，需將陣列元素重新整理，將開始位址的元素複製到新陣列的起始位置，否則資料會亂掉，如下圖所示：
語法
C#
抽象類別
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| using System;
using System.Collections.Generic;
using System.Text;
namespace Queue
{
abstract class Queue<T>
{
public int Count { get; protected set; }
abstract public void Enqueue(T value);
abstract public T Dequeue();
abstract public T Peek();
}
}
|
連結串列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| using System;
using System.Collections.Generic;
using System.Text;
namespace Queue
{
class Node<T>
{
public Node<T> Next { get; internal set; }
public T Value { get; internal set; }
public Node(T value)
{
Value = value;
}
}
class LinkedListQueue<T> : Queue<T>
{
private Node<T> first;
private Node<T> last;
public override void Enqueue(T value)
{
Node<T> node = new Node<T>(value);
if (Count == 0)
first = node;
else
last.Next = node;
last = node;
++Count;
}
public override T Dequeue()
{
Node<T> node = first;
first = first.Next;
node.Next = null;
--Count;
return node.Value;
}
public override T Peek()
{
return first.Value;
}
}
}
|
陣列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Queue
{
class ArrayQueue<T> : Queue<T>
{
private int capacity;
private int first;
private T[] array;
public ArrayQueue()
: this(10240)
{
}
public ArrayQueue(int capacity)
{
this.capacity = capacity;
array = new T[capacity];
}
public override void Enqueue(T value)
{
if (Count == array.Length)
{
T[] newArray = new T[array.Length + capacity];
Array.Copy(array, first, newArray, 0, array.Length - first);
Array.Copy(array, 0, newArray, array.Length - first, first);
array = newArray;
first = 0;
}
array[(first + Count) % array.Length] = value;
++Count;
}
public override T Dequeue()
{
T value = array[first];
array[first] = default(T);
first = (first + 1) % array.Length;
--Count;
return value;
}
public override T Peek()
{
return array[first];
}
}
}
|
Java
抽象類別
1
2
3
4
5
6
7
8
9
10
11
12
| public abstract class Queue<T> {
protected int count;
abstract public void offer(T value);
abstract public T poll();
abstract public T peek();
public int size()
{
return count;
}
}
|
連結串列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| public class Node<T>
{
private Node<T> next;
private T value;
public Node<T> getNext()
{
return next;
}
void setNext(Node<T> next)
{
this.next = next;
}
public T getValue()
{
return value;
}
void setValue(T value)
{
this.value = value;
}
public Node(T value)
{
this.value = value;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| public class LinkedListQueue<T> extends Queue<T> {
private Node<T> first;
private Node<T> last;
@Override
public void offer(T value) {
Node<T> node = new Node<T>(value);
if (count == 0)
first = node;
else
last.setNext(node);
last = node;
++count;
}
@Override
public T poll() {
Node<T> node = first;
first = first.getNext();
node.setNext(null);
--count;
return node.getValue();
}
@Override
public T peek() {
return first.getValue();
}
}
|
陣列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| public class ArrayQueue<T> extends Queue<T> {
private int capacity;
private int first;
private T[] array;
public ArrayQueue()
{
this(10240);
}
@SuppressWarnings("unchecked")
public ArrayQueue(int capacity)
{
this.capacity = capacity;
array = (T[]) new Object[capacity];
}
@SuppressWarnings("unchecked")
@Override
public void offer(T value) {
if (count == array.length)
{
T[] newArray = (T[]) new Object[array.length + capacity];
System.arraycopy(array, first, newArray, 0, array.length - first);
System.arraycopy(array, 0, newArray, array.length - first, first);
array = newArray;
first = 0;
}
array[(first + count) % array.length] = value;
++count;
}
@Override
public T poll() {
T value = array[first];
array[first] = null;
first = (first + 1) % array.length;
--count;
return value;
}
@Override
public T peek() {
return array[first];
}
}
|
C++
抽象類別
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #ifndef QUEUE_H
#define QUEUE_H
template<typename T>
class Queue
{
public:
Queue()
{
count = 0;
}
int size()
{
return count;
}
virtual void push(T value) = 0;
virtual T pop() = 0;
virtual T front() = 0;
protected:
int count;
private:
};
#endif
|
連結串列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #ifndef LINKEDLISTQUEUE_H
#define LINKEDLISTQUEUE_H
#include "Queue.h"
template<typename T>
class Node
{
public:
Node(T v)
{
value = v;
next = 0;
}
~Node()
{
delete next;
}
Node<T>* next;
T value;
protected:
private:
};
template<typename T>
class LinkedListQueue : public Queue<T>
{
public:
~LinkedListQueue()
{
if(first != last)
delete first;
delete last;
}
void push(T value)
{
Node<T>* node = new Node<T>(value);
if (Queue<T>::count == 0)
first = node;
else
last->next = node;
last = node;
++Queue<T>::count;
}
T pop()
{
Node<T>* node = first;
first = first->next;
node->next = 0;
T value = node->value;
delete node;
--Queue<T>::count;
return value;
}
T front()
{
return first->value;
}
protected:
private:
Node<T>* first;
Node<T>* last;
};
#endif
|
陣列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #ifndef ARRAYQUEUE_H
#define ARRAYQUEUE_H
#include <memory.h>
#include "Queue.h"
template<typename T>
class ArrayQueue : public Queue<T>
{
public:
ArrayQueue(int capacity = 10240)
{
cap = capacity;
arrayLength = capacity;
array = new T[capacity];
}
~ArrayQueue()
{
delete [] array;
}
void push(T value)
{
if (Queue<T>::count == arrayLength)
{
T* newArray = new T[arrayLength + cap];
memcpy(newArray, array + first, (arrayLength - first) * sizeof(T));
memcpy(newArray + arrayLength - first, array, first * sizeof(T));
arrayLength += cap;
delete [] array;
array = newArray;
first = 0;
}
array[(first + Queue<T>::count) % arrayLength] = value;
++Queue<T>::count;
}
T pop()
{
T value = array[first];
array[first] = 0;
first = (first + 1) % arrayLength;
--Queue<T>::count;
return value;
}
T front()
{
return array[first];
}
protected:
private:
int arrayLength;
int cap;
int first;
T* array;
};
#endif
|
enqueue和dequeue 500000次實測，同時候內建的類別比較
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| C#
Built-in Queue Enqueue Time: 30ms
Built-in Queue Dequeue Time: 10ms
LinkedListQueue Enqueue Time: 80ms
LinkedListQueue Pop Time: 20ms
ArrayQueue Enqueue Time: 60ms
ArrayQueue Dequeue Time: 10ms
Java
Built-in Queue Offer Time: 130ms
Built-in Queue Poll Time: 20ms
LinkedListQueue Offer Time: 178ms
LinkedListQueue Poll Time: 12ms
ArrayQueue Offer Time: 112ms
ArrayQueue Poll Time: 10ms
C++
Built-in Push Time: 10ms
Built-in Pop Time: 30ms
LinkedListQueue Push Time: 50ms
LinkedListQueue Pop Time: 40ms
ArrayQueue Push Time: 30ms
ArrayQueue Pop Time: 10ms
|
延伸閱讀
連結串列 (LinkedList)
堆疊 (Stack)
