队列（queue )是一种先进先出(first in first out，简称 FIFO表)的线性表。
它只允许在表的一端进行插入，而在另一端删 除元素。
在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端 称为队头(front)。
一、队列的顺序表示和实现，循环队列（数组）
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h> #define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXQSIZE 100 //最大队列长度 typedef int Status;
typedef int QElemType; /* 0.队列结构体 */
typedef struct {
QElemType *base; // 指针(指向动态分配存储空间)
int front; //头指针，若队列不空，
//指向队列头元素
int rear; //尾指针，若队列不空，
//指向队列尾元素的下 一个位置
}SqQueue; //定义循环队列类型 /* 1.队列Q初始化(构造一个空队列Q) */
Status InitQueue (SqQueue &Q) {
Q.base = (QElemType *) malloc(MAXQSIZE *sizeof (QElemType));
if (!Q.base) exit (OVERFLOW);// 存储分配失败
Q.front = Q.rear = ; //队列为空(数组下标均为0)
return OK;
} /* 2.队列Q的队尾插入元素e*/
Status EnQueue (SqQueue &Q, QElemType e) {
if ((Q.rear+) % MAXQSIZE == Q.front)
return ERROR; //队列满 rear+1 == front
Q.base[Q.rear] = e; //插入队尾
Q.rear = (Q.rear+) % MAXQSIZE; //队尾指针更新 rear+1
return OK;
} /* 3.删除队列Q的队头元素 */
Status DeQueue (SqQueue &Q, QElemType &e) {
if (Q.front == Q.rear) return ERROR; //空队列 front == rear
e = Q.base[Q.front]; //返回删除的元素
Q.front = (Q.front+) % MAXQSIZE; //删除元素(更新队头指针 front+1)
return OK;
} /* 测试代码 */
int main()
{
int array[] = {};
SqQueue Q; //创建一个队列变量
InitQueue(Q);//队列初始化(分配空间,构造空队列)
for(int i=; i<; ++i)
EnQueue(Q,i+); //队列插入元素
for(int j=; j<; ++j)
DeQueue(Q,array[j]); //删除队列元素,到数组array
for(int k=; k<; ++k) //输出数组元素
printf("%3d",array[k]);
printf("\n");
return ;
}
//浙大数据结构 \ 顺序队列
typedef int Position;
struct QNode {
ElementType *Data; /* 存储元素的数组 */
Position Front, Rear; /* 队列的头、尾指针 */
int MaxSize; /* 队列最大容量 */
};
typedef struct QNode *Queue; Queue CreateQueue( int MaxSize )
{
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
Q->Front = Q->Rear = ;
Q->MaxSize = MaxSize;
return Q;
} bool IsFull( Queue Q )
{
return ((Q->Rear+)%Q->MaxSize == Q->Front);
} bool AddQ( Queue Q, ElementType X )
{
if ( IsFull(Q) ) {
printf("队列满");
return false;
}
else {
Q->Rear = (Q->Rear+)%Q->MaxSize;
Q->Data[Q->Rear] = X;
return true;
}
} bool IsEmpty( Queue Q )
{
return (Q->Front == Q->Rear);
} ElementType DeleteQ( Queue Q )
{
if ( IsEmpty(Q) ) {
printf("队列空");
return ERROR;
}
else {
Q->Front =(Q->Front+)%Q->MaxSize;
return Q->Data[Q->Front];
}
}
二、队列的链式表示和实现，链队列（链表）
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h> #define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXQSIZE 100 //最大队列长度 typedef int Status;
typedef int QElemType;
typedef struct Node QNode; //结点类型
typedef struct Node* QueuePtr;//结点指针
struct Node { //定义结点
QElemType data; //结点data
QueuePtr next; //结点next指针
}; /* 0.队列结构体 */
typedef struct {
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} LinkQueue; // 链队列类型 /* 1.队列Q初始化(构造一个空队列Q) */
Status InitQueue (LinkQueue &Q) {
//队列的队头、队尾指向队头结点(空队列)
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front) exit (OVERFLOW);//存储分配失败
Q.front->next = NULL;//头指针置空
return OK;
} /* 2.销毁队列Q */
Status DestroyQueue (LinkQueue &Q) {
Q.front = Q.front->next;//带头结点的队列
while (Q.front)
{
Q.rear = Q.front->next;
free (Q.front) ;
Q.front = Q.rear;
}
return OK;
} /* 3.队列Q的队尾插入元素e*/
Status EnQueue (LinkQueue &Q, QElemType e) {
QueuePtr p = (QueuePtr) malloc (sizeof (QNode));
if(!p) exit (OVERFLOW); //存储分配失败
p->data = e;
p->next = NULL; //新结点p->next置为NULL
Q.rear->next = p;//插入队列
Q.rear = p; //更新队尾
return OK;
} /* 3.删除队列Q的队头元素 */
Status DeQueue (LinkQueue &Q, QElemType &e) {
if (Q.front == Q.rear) return ERROR; //队列为空
QueuePtr p = Q.front->next;
e = p->data;
Q.front->next = p->next; //删除队头元素(其后继元素挂到队列头结点)
if (Q.rear == NULL) Q.rear = Q.front; //队尾空,队列置空
free (p); //释放删除的对头元素
return OK;
} /* 测试代码 */
int main()
{
int array[] = {};
LinkQueue Q; //创建一个队列变量
InitQueue(Q);//队列初始化(分配空间,构造空队列)
for(int i=; i<; ++i)
EnQueue(Q,i+); //队列插入元素
for(int j=; j<; ++j)
DeQueue(Q,array[j]); //删除队列元素,到数组array
for(int k=; k<; ++k) //输出数组元素
printf("%3d",array[k]);
printf("\n");
return ;
}
/* 只有尾指针的循环队列 */
#include <stdio.h>
#include <malloc.h> #define OK 1
#define ERROR 0 typedef int QElemType, Status;
typedef struct LinkQueueNode* LinkQueuePTR; /* 0.结点 */
struct LinkQueueNode{
QElemType e;
LinkQueuePTR next;
}; /* 1. 初始化队列*/
Status InitQueue(LinkQueuePTR *rear)
{
LinkQueuePTR p;
p = (LinkQueuePTR)malloc(sizeof(struct LinkQueueNode));
if(p == NULL)
return ERROR; p->next = p;
*rear = p;
return OK;
}
/* 2. 队列是否为空*/
Status isEmpty(LinkQueuePTR rear)
{
if(rear == NULL)
return ERROR;
return rear == rear->next ? OK : ERROR;
}
/* 3. 进队*/
Status enqueue(LinkQueuePTR *rear,QElemType e)
{
LinkQueuePTR p;
p = (LinkQueuePTR)malloc(sizeof(struct LinkQueueNode));
if(p == NULL)
return ERROR; p->e=e;
p->next = (*rear)->next;
(*rear)->next = p;
*rear = p;
return OK;
}
/* 4. 出队*/
Status dequeue(LinkQueuePTR *rear,QElemType *e)
{
if(isEmpty(*rear))
return ERROR; LinkQueuePTR front;
front = (*rear)->next->next; if(front == *rear){/* 是否只一个结点 */
*rear = front->next;
(*rear)->next = *rear;
}
else{
(*rear)->next->next = front->next;
} *e = front->e;
free(front);
return OK;
} /* 测试代码 */
int main()
{
LinkQueuePTR rear = NULL;
QElemType e;
int n = ;
/* 初始化只有尾指针的循环队列 */
InitQueue(&rear);
/* 队列输入数据(进队) */
for(int i=; i<n; ++i){
scanf("%d",&e);
enqueue(&rear,e);
}
/* 出队 */
while(!isEmpty(rear))
{
dequeue(&rear,&e);
printf("%5d",e);
}
return ;
}
//浙大数据结构 \ 链队列
typedef struct Node *PtrToNode;
struct Node { /* 队列中的结点 */
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode Position; struct QNode {
Position Front, Rear; /* 队列的头、尾指针 */
int MaxSize; /* 队列最大容量 */
};
typedef struct QNode *Queue; bool IsEmpty( Queue Q )
{
return ( Q->Front == NULL);
} ElementType DeleteQ( Queue Q )
{
Position FrontCell;
ElementType FrontElem; if ( IsEmpty(Q) ) {
printf("队列空");
return ERROR;
}
else {
FrontCell = Q->Front;
if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
else
Q->Front = Q->Front->Next;
FrontElem = FrontCell->Data; free( FrontCell ); /* 释放被删除结点空间 */
return FrontElem;
}
}