队列是具有一定操作约束的线性表，只能在一端插入，而在另一端删除。长度为MaxSize的队列，队列元素item
数据插入：入队（AddQ）
数据删除：出队（DeleteQ）
先来先服务，先进先出（FIFO）
【队列的顺序存储实现】
/* 队列的顺序存储结构通常是由一个一维数组
和一个记录队列头元素位置的变量front
以及一个记录队列尾元素的变量rear组成 */
/* 定义队列 */
#define MaxSize 100
struct QNode{
ElementType Data[MaxSize];
int rear; //数组下标，队列头元素下标-1
int front; //数组下标，队列尾元素下标
};
typedef struct QNode * Queue;
/* 入队 */
void AddQ(Queue PtrQ,ElementType item)
{
if((PtrQ->rear+1)%MaxSize==PtrQ->front){
printf("the Queue full");
return;
}
PtrQ->rear=(PtrQ->rear+1)%MaxSize;
PtrQ->Data[PtrQ->rear]=item;
}
/* 出队 */
ElementType DeleteQ(Queue PtrQ)
{
if(PtrQ->front==PtrQ->rear){
printf("the Queue empty");
return ERROR;
}else{
PtrQ->front=(PtrQ->front+1)%MaxSize;
return PtrQ->Data[PtrQ->front];
}
}
【队列的链式存储实现】
/* 队列的链式存储结构也可以用一个单链表实现，
插入和删除操作分别在链表的两头进行
front 指向链表的头 rear指向链表的尾 */
/* 定义链表队列 */
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 FrontElem;
if(PtrQ->front == NULL){
printf("the Queue empty");
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;
}
