队列的顺序/链式存储实现

队列：具有一定操作约束的线性表，只能在一端插入，在另一端删除。

特点：先来先服务，先进先出表

头front，尾rear

顺序存储

 1 #define MaxSize <储存数据元素的最大个数>
 2 
 3 struct QNode {
 4 
 5 　　ElementType Data[MaxSize];
 6 
 7 　　int rear;　　//尾
 8 
 9 　　int front;　　//头
10 
11 };
12 
13 typedef struct QNode *Queue;
14　　//front = rear = -1;

循环队列的储存办法：

　　（1）使用额外标记：size或者tag（插入为1，删除为0）域

　　（2）仅使用n-1个数组空间

（1）入队列(循环队列)

 1 void AddQ (Queue PtrQ, ElementType item){
 2 
 3 　　if ( (PtrQ->rear+1) % MaxSize == PtrQ->front ){
 4 
 5 　　　　printf("队列满");
 6 
 7 　　　　return;
 8 
 9 　　}
10 　　//这两句看情况进行交换
11 　　PtrQ->reat = (PtrQ->rear+1) % MaxSize;
12 
13 　　PtrQ->Data[PtrQ->rear] = item;
14 
15 }

（2）出队列

ElementType DeleteQ ( Queue PtrQ ){

　　if (PtrQ->front == PtrQ->reat) {

　　　　printf("队列空");

　　　　return ERROR;

　　}

　　else {

　　　　PtrQ->front = (PtrQ->front+1) % MaxSize;

　　　　return PtrQ->Data[PtrQ->front];

　　}

}

链式存储

struct Node {　　//链表的结点结构

　　ElementType Data;

　　struct Node *Next;

};

struct QNode {　　//链队列结构
　　struct Node *rear;　　//指向队尾结点
　　struct Node *front;　　//指向对头结点
};

typedef struct QNode *Queue;

Queue PtrQ;

插入和删除操作分别在链表的两头进行

不带头结点的链式队列出队操作

ElementType DeleteQ ( Queue PtrQ ){

　　struct Node *FrontCell;

　　ElementType FrotElem;

　　if ( PtrQ->front == NULL ){

　　　　printf("队列空");

　　　　return ERROR;

　　}

　　FrontCell = PtrQ->front;

　　if (PtrQ->front == PtrQ->rear)　　//若队列只有一个元素

　　　　PtrQ->front = PtrQ->rear = NULL;　　//删除后置队列为空

　　else {

　　　　PtrQ->front = PtrQ->front->Next;

　　}

　　FrontElem = FrontCell->Data;

　　free(FrontCell);

　　return FrontElem;

}