队列只允许在表的一端插入，在另一端删除。

#循环队列

对于数组实现的顺序队列来说，队列为空时，front == rear；队列为满时，rear == maxSize。但是要注意，rear == maxSize时，可能数组头部还有空位置，也就是说，这是一个“假溢出”。为了解决这个问题，我们将数组的前后端连接起来，就成了循环队列。为了区分队列是空是满，(rear+1)%maxSize == front作为队满的判断，即在队列为满时空了一个元素的位置。

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
67
68
69
70
71
72
73
74
75
76
#include <assert.h>
#include <iostream.h>
#include "Queue.h"
template <class T>
class SeqQueue: public Queue<T> {
public:
	SeqQueue(int sz = 10);
	~SeqQueue() {
		delete[] elements;
	}
	bool EnQueue(const T& x);
	bool int DeQueue(T& x);
	bool getFront(T& x);
	void makeEmpty() {
		front = rear = 0;
	}
	bool IsEmpty() const {
		return (front == rear) ? true : false;
	}
	bool IsFull() const {
		return ((rear + 1) % maxSize == front) ? true : false;
	}
	int getSize() const {
		return (rear - front + maxSize) % maxSize;
	}
	friend ostream& operator << (ostream& os, SeqQueue<T>& Q);
	
protected:
	int rear, front;
	T *elements;
	int maxSize;
};
template <class T>
SeqQueue<T>::SeqQueue(int sz): front(0), rear(0), maxSize(sz) {
	elements = new T[maxSize];
	assert(elements != NULL);
};
template <class T>
bool SeqQueue<T>::EnQueue(const T& x) {
	if (IsFull() == true) {
		return false;
	}
	elements[rear] = x;
	rear = (rear + 1) % maxSize;
	return true;
};
template <class T>
bool SeqQueue<T>::DeQueue(T& x) {
	if (IsEmpty() == true) {
		return false;
	}
	x = elements[front];
	front = (front + 1) % maxSize;
	return true;
};
template <class T>
bool SeqQueue<T>::getFront(T& x) const {
	if (IsEmpty() == true) {
		return false;
	}
	x = elements[front];
	return true;
};
template <class T>
ostream& operator << (ostream& os, SeqQueue<T>& Q) {
	os << "front = " << Q.front << ", rear =" << Q.rear << endl;
	for (int i = front; i != rear; i = (i + 1) % maxSize) {
		os << i << ":" << Q.elements[i] << endl;
	}
	return os;
};

#链式队列

用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在溢出的情况。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream.h>
#include "LinkedList.h"
#include "Queue.h"
template <class T>
class LinkedQueue: public Queue<T> {
public:
	LinkedQueue(): rear(NULL), front(NULL) {}
	~LinkedQueue(makeEmpty());
	bool EnQueue(const T& x);
	bool DeQueue(T& x);
	bool getFront(T& x) const;
	void makeEmpty();
	bool IsEmpty() const {
		return (front == NULL) ? true : false;
	}
	int getSize() const;
	friend ostream& operator << (ostream& os, LinkedQueue<T>& Q);
	
protected:
	LinkNode<T> *front, *rear;
};
template <class T>
void LinkedQueue<T>::makeEmpty() {
	LinkNode<T> *p;
	while (front != NULL) {
		p = front;
		front = front->link;
		delete p;
	}
};
template <class T>
bool LinkedQueue<T>::EnQueue(const T& x) {
	if (front == NULL) {
		front = rear = new LinkNode<T>(x);
		if (front == NULL) {
			return false;
		}
	} else {
		rear->link = new LinkNode<T>(x);
		if (rear->link == NULL) {
			return false;
		}
		rear = rear->link;
	}
	return true;
};
template <class T>
bool LinkedQueue<T>::DeQueue(T& x) {
	if (IsEmpty() == true) {
		return false;
	}
	LinkNode<T> *p = front;
	x = front->data;
	front = front->link;
	delete p;
	return true;
};
template <class T>
bool LinkedQueue<T>::getFront(T& x) const {
	if (IsEmpty() == true) {
		return false;
	}
	x = front->data;
	return true;
};
template <class T>
bool LinkedQueue<T>::getSize() const {
	LinkNode<T> *p = front;
	int k = 0;
	while (p != NULL) {
		p = p->link;
		k ++;
	}
	return k;
};
template <class T>
ostream& operator << (ostream& os, LinkedQueue<T>& Q) {
	os << "队列中元素个数：" << Q.getSize() << endl;
	LinkNode<T> *p = Q.front;
	int i = 0;
	while (p != NULL) {
		os << ++i << ":" << p->data << endl;
		p = p->link;
	}
	return os;
};

#队列应用

##杨辉三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <iostream.h>
#include "queue.h"
void YANGVI(int n) {
	Queue q(n + 1);
	int i = 1, j, s = k = 0, t, u;
	q.EnQueue(i);
	q.EnQueue(i);
	for (i = 1; i <= n; i++) {
		cout << endl;
		q.EnQueue(k);
		for (j = 1; j <= i + 2; j ++) {
			q.DeQueue(t);
			u = s + t;
			q.EnQueue(u);
			s = t;
			if (j != i + 2) {
				cout << s << ' ';
			}
		}
	}
};

一般这种逐行处理的情况都需要队列作为辅助工具。

##电线布线

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
bool FindPath(Position start, Position finish, int& PathLen, Position *& path) {
	if (start.row == finish.row && start.col == finish.col) {
		PathLen = 0;
		return true;
	}
	int NumOfNbrs = 4, i, j;
	for (i = 0; i <= m + 1; i ++) {
		grid[0][i] = grid[m+1][i] = 1;
		grid[i][0] = grid[i][m+1] = 1;
	}
	Position offset[4];
	offsets[0].row = 0;
	offsets[0].col = 1;
	offsets[1].row = 1;
	offsets[1].col = 0;
	offsets[2].row = 0;
	offsets[2].col = -1;
	offsets[3].row = -1;
	offsets[3].col = 0;
	Position here, nbr;
	here.row = start.row;
	here.col = start.col;
	grid[start.row][start.col] = 2;
	LinkedQueue <Position> Q;
	do {
		for (i = 0; i < NumOfNbrs; i ++) {
			nbr.row = here.row + offsets[i].row;
			nbr.col = here.row + offsets[i].col;
			if (grid[nbr.row][nbr.col] == 0) {
				grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1;
				if (nbr.row == finish.row && nbr.col == finish.col) {
					break;
				}
				Q.EnQueue(nbr);
			}
		}
		if (nbr.row == finish.row && nbr.col == finish.col) {
			break;
		}
		if (Q.IsEmpty() == true) {
			return false;
		}
		Q.DeQueue(here);
	} while (true);
	PathLen grid[finish.row][finish.col] - 2;
	path = new Position[PathLen];
	here = finish;
	for (j = PathLen - 1; j >= 0; j --) {
		path[j] = here;
		for (i = 0; i < NumOfNbrs; i ++) {
			nbr.row = here.row + offsets[i].row;
			nbr.col = here.col + offsets[i].col;
			if (grid[nbr.row][nbr.col] == j + 2) {
				break;
			}
		}
		here = nbr;
	}
	return true;
};

#优先级队列

每次从队列中取出的应是具有最高优先级的元素。

类声明。

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
#include <assert.h>
#include <iostream.h>
#include <stdlib.h>
const int DefaultPQSize = 50;
enum bool {false, true}
template <class T>
class PQueue {
public:
	PQueue(int sz = DefaultPQSize);
	~PQueue() {
		delete[] pqelements;
	}
	bool Insert(const T& x);
	bool RemoveMin(T& x);
	bool getFront(T& x) const;
	void makeEmpty() {
		count = 0;
	}
	bool IsEmpty() const {
		return (count == 0) ? true : false;
	}
	bool IsFull() const {
		return (count == maxSize) ? true : false;
	}
	int getSize() const {
		return count;
	}
	
protected:
	T *pqelements;
	int count;
	int maxSize;
	Adjust();
};

存储表示和实现。

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
template <class T>
PQueue<T>::PQueue(int sz): maxSize(sz), count(0) {
	pqelements = new T[maxSize];
	assert(pqelements != NULL);
};
template <class T>
bool PQueue<T>::Insert(const T& x) {
	if (count == maxSize) {
		return false;
	}
	pqelements[count++] = x;
	Adjust();
}
template <class T>
void PQueue<T>::Adjust() {
	T temp = pqelements[count - 1];
	for (int j = count - 2; j >= 0; j --) {
		if (pqelements[j] <= item) {
			break;
		} else {
			pqelements[j + 1] = pqelements[j];
		}
	}
	pqelements[j + 1] = item;
};
template <class T>
bool PQueue<T>::RemoveMin(T& x) {
	if (count == 0) {
		return false;
	}
	x = pqelements[0];
	for (int i = 1; i < count; i ++) {
		pqelements[i - 1] = pqelements[i];
	}
	count --;
	return true;
};
template <class T>
bool PQueue<T>::getFront() {
	if (count == 0) {
		return false;
	} else {
		return pqelements[0];
	}
};

#双端队列

全称是Double-Ended Queue.