#C/C++泛型编程实现数据结构之队列
早在曾经一篇博文中，我曾介绍过顺序存储和链式存储的区别和好处
本章将讲诉：
-
- 队列的逻辑结构刨析
- 顺序存储结构下的循环队列
- 链式存储结构下的循环链队列
- C/C++泛型编程类模板实现队列
###逻辑结构：
顺序队列的逻辑结构：
#define Max_Size = 100;
template <typename DataType>
struct Queue{
DataType data[Max_Size];
int front;
int rear;
};
由于队列是一种先进先出的FIFO的线性表，所以我们在这里设置了队列的头front和队列的尾部rear;从而实现rear进入的元素可以在front处删除。下面来看链队列的逻辑结构。
链队列的逻辑结构：
struct QueueNode{
DataType data;
QueueNode* next;
};
struct LinkQueue{
QueueNode* front;
QueueNode* rear;
};
LinkQueue Q;
其中Queue_Node这个结构题代表了每个节点的类型，顺序存储中我们采用数组来实现这个队列空间，而在这里我们采用了链表来实现这个访问受限的线性表。
###入队列和出队列
这里入队和出队操作要单独拿出来讲。
由于循环队列的入队和出队是循环意义上的入队和出队，为了充分利用数组空间，克服上溢，可将数组空间想象成一个环状空间，并称这个环状空间为循环队列。这种循环队列的出队和入队运算时，头尾指针仍然要加1，只不过当头尾指针指向数组上界Queue_Size-1时，如何按正常的操作进行+1运算，则数组就会产生溢出。因此需要判断+1后是否超过数组上界。
顺序队列入队列和出队列实现：
void En_Queue(DataType info) {
if(!Queue_full()){
data[rear] = info;
rear = (rear + 1) % QueueSize;
}
else {
cout << "the Queue is overflow!" << endl;
}
}
DataType De_Queue() {
if (!Empty_Queue()){
DataType x = data[front];
front = (front + 1) % QueueSize;
return x;
}
else {
cout << "the Queue is Empty!" << endl;
exit(0);
}
}
链队列入队和出队实现：
void EnQueue(DataType x) {
QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode));
p->data = x;
p->next = NULL;
Q->rear->next= p;
Q->rear = p;
}
DataType DeQueue() {
QueueNode* p;
if (QueueEmpty()) {
cout << "the Queue is empty!" << endl;
exit(0);
}
else {
p = Q->front;
Q->front = Q->front->next;
free(p);
return Q->front->data;
}
}
###以上即为重点部分，现在来看完整代码实现：
###顺序存储结构下的队列：
template <typename DataType>
class Queue {
private:
const int QueueSize = 100;
protected:
DataType data = new DataType[QueueSize];
int front, rear;
public:
Queue() {
front = rear = 0;
}
void En_Queue(DataType info) {
if(!Queue_full()){
data[rear] = info;
rear = (rear + 1) % QueueSize;
}
else {
cout << "the Queue is overflow!" << endl;
}
}
DataType De_Queue() {
if (!Empty_Queue()){
DataType x = data[front];
front = (front + 1) % QueueSize;
return x;
}
else {
cout << "the Queue is Empty!" << endl;
exit(0);
}
}
bool Empty_Queue() {
return rear == front;
}
bool Queue_full() {
return (rear + 1) % QueueSize == front;
}
};
###链式存储结构下的队列：
template <typename DataType>
class Link_Queue{
private:
struct QueueNode{
DataType data;
QueueNode* next;
};
protected:
struct LinkQueue{
QueueNode* front;
QueueNode* rear;
};
private:
LinkQueue* Q;
public:
Link_Queue() {
Q->front = (QueueNode*)malloc(sizeof(QueueNode));
Q->rear = Q->front;
Q->rear->next = NULL;
}
bool QueueEmpty() {
return Q->rear == Q->front;
}
void EnQueue(DataType x) {
QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode));
p->data = x;
p->next = NULL;
Q->rear->next= p;
Q->rear = p;
}
DataType GetFront() {
if (QueueEmpty()) {
cout << "the Queue is Empty!" << endl;
exit(0);
}
else {
return Q->front->next->data;
}
}
DataType DeQueue() {
QueueNode* p;
if (QueueEmpty()) {
cout << "the Queue is empty!" << endl;
exit(0);
}
else {
p = Q->front;
Q->front = Q->front->next;
free(p);
return Q->front->data;
}
}
};
