队列的定义，实现与基本 *** 作_C

定义:一头进另一头出的线性表（排队）

术语：队头，队尾，空队列

基本 *** 作（静态数组式）

定义与初始化

#define Maxsize 10
//定义队列中的最大个数
typedef struct {
   int data[Maxsize];
   int front, rear; //队头指针和队尾指针
}SeQueue;
//初始化队列
void InitQueue(SeQueue &Q) {
   Q.rear = Q.front; //初始化时队头队尾指针指向0
}
void testQueue() {
   SeQueue Q;
   InitQueue(Q);
}
//判断队列是否为空
bool QueueEmpty(SeQueue Q) {
   if (Q.rear == Q.front) {
       return true;
   }
   else
   {
       return false;
   }
}

定义了一个最大长度为10，元素类型为int的静态数组

用front 和rear分别指向头元素和尾元素。初

初始化两指针都指向0结点。

所以当两指针指向结点相同时候，队列为空。

插入与删除

//入队 *** 作(循环队列)
bool EnQueue(SeQueue& Q, int x) { //在队头插入元素X
   if ((Q.rear+1)%Maxsize == Q.front){ //队列已满
       return false;
   }
   else
   {
       Q.data[Q.rear] = x; //将X插入队尾
       Q.rear = (Q.rear + 1)%Maxsize;
       return true;
   }
}
//出队 *** 作
bool DeQueue(SeQueue &Q, int& x) {
   if (Q.rear == Q.front) { //判断是否是空表
       return false;
   }
   x = Q.data[Q.front];
   Q.front = (Q.front + 1) % Maxsize;
   return true;

}

插入一个元素，rear往后移动一位;删除一个元素，front往后移动一位。

Q.rear = (Q.rear+1)&Maxsize：当尾指针在第9个节点时，插入一个元素，尾指针会指向0结点。

Q.front = (Q.front + 1) % Maxsize;同理。

这样，我们的直队列就变成了一个环状的队列，称为环状队列。

查找

//查找队头元素
bool GetHead(SeQueue Q, int& x) {

   //计算元素个数
   //(Q.rear+Maxsize-Q.front)%Maxsize
   if (Q.rear == Q.front) { //判断是否是空表
       return false;
   }
   //相对于出队少了一步头指针移动的过程
   x = Q.data[Q.front];
   return true;
}

**但这样，会导致一部分空间被浪费，也就是当rear在front后面时候，再想加一个元素进来会判断为队列已满。

解决方法：初始化表时候，将Q.rear指向第九结点。同时，定义一个int 型辅助变量，当插入一个元素时，其++；删除一个元素时，其--。

基本 *** 作（链表结构）

特点：队列不会满（除非内存满了）

阉割版单链表

typedef struct LinkNode { //链式队列结点
int data;
struct LinkNode* next;
}LinkNode;

typedef struct { //链式队列
LinkNode* front, * rear; //链式队列的队头和队尾指针
}LinkQueue;

初始化

//初始化
void InitQueue(LinkQueue &Q) {
   //初始化时 front ， rear都指向头结点
   Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
   Q.front->next = NULL;
}
void testLinkQueue() {
   LinkQueue Q;
   InitQueue(Q);
}

出队 *** 作和入队 *** 作

//入队 *** 作
void EnQueue(LinkQueue& Q, int x) {
   LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
s->data = x;
   s->next = NULL;
   Q.rear->next = s; //新节点插入到   rear之后
   Q.rear = s; //修改表尾指针
}
//出队 *** 作
bool DeQueue(LinkQueue& Q, int X) {
   if (Q.front = Q.rear) {
       return false; //队列为空
   }
   else {
       LinkNode* p = Q.front->next; //一个新的指针P，令其指向头结点的下一个结点（即队头）
       X = p->data; //将头结点的元素赋值给X
       Q.front->next= p->next; //改变头结点的指针，指向队列中第二个结点。
       if (Q.rear == p) { //如果第二个结点就是队尾，则另队头指针赋值给队尾指针
           Q.rear = Q.front;
       }
       free(p); //释放掉要删除的结点内存
       return true;
   }
}