队列只允许在表的一端插入，在另一端删除。
循环队列
对于数组实现的顺序队列来说，队列为空时，front == rear；队列为满时，rear == maxSize。但是要注意，rear == maxSize时，可能数组头部还有空位置，也就是说，这是一个“假溢出”。为了解决这个问题，我们将数组的前后端连接起来，就成了循环队列。为了区分队列是空是满，(rear+1)%maxSize == front作为队满的判断，即在队列为满时空了一个元素的位置。
#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;
};链式队列
用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在溢出的情况。
#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;
};队列应用
杨辉三角
#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 << ' ';
}
}
}
};一般这种逐行处理的情况都需要队列作为辅助工具。
电线布线
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;
};优先级队列
每次从队列中取出的应是具有最高优先级的元素。
类声明。
#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();
};存储表示和实现。
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.