佇列，又稱為-{zh-hans:伫列;zh-hant:隊列}-（queue），计算机科學中的一種抽象資料型別，是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。
队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
单链队列
单链队列使用链表作为基本数据结构，所以不存在伪溢出的问题，队列长度也没有限制。但插入和读取的时间代价较高
存储结构
/ c3-2.h 单链队列－－队列的链式存储结构 /
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; / 队头、队尾指针 /
}LinkQueue;
基本操作
/ bo3-2.c 链队列(存储结构由c3-2.h定义)的基本操作(9个) /
void InitQueue(LinkQueue *Q)
{ / 构造一个空队列Q /
(Q).front=(Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(*Q).front)
exit(OVERFLOW);
(*Q).front->next=NULL;
}
void DestroyQueue(LinkQueue *Q)
{ / 销毁队列Q(无论空否均可) /
while((*Q).front)
{
(Q).rear=(Q).front->next;
free((*Q).front);
(Q).front=(Q).rear;
}
}
void ClearQueue(LinkQueue *Q)
{ / 将Q清为空队列 /
QueuePtr p,q;
(Q).rear=(Q).front;
p=(*Q).front->next;
(*Q).front->next=NULL;
while(p)
{
q=p;
p=p->next;
free(q);
}
}
Status QueueEmpty(LinkQueue Q)
{ / 若Q为空队列，则返回TRUE，否则返回FALSE /
if(Q.front->next==NULL)
return TRUE;
else
return FALSE;
}
int QueueLength(LinkQueue Q)
{ / 求队列的长度 /
int i=0;
QueuePtr p;
p=Q.front;
while(Q.rear!=p)
{
i++;
p=p->next;
}
return i;
}
Status GetHead_Q(LinkQueue Q,QElemType e) / 避免与bo2-6.c重名 */
{ / 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR /
QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
*e=p->data;
return OK;
}
void EnQueue(LinkQueue *Q,QElemType e)
{ / 插入元素e为Q的新的队尾元素 /
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) / 存储分配失败 /
exit(OVERFLOW);
p->data=e;
p->next=NULL;
(*Q).rear->next=p;
(*Q).rear=p;
}
Status DeQueue(LinkQueue Q,QElemType e)
{ / 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR /
QueuePtr p;
if((Q).front==(Q).rear)
return ERROR;
p=(*Q).front->next;
*e=p->data;
(*Q).front->next=p->next;
if((*Q).rear==p)
(Q).rear=(Q).front;
free(p);
return OK;
}
void QueueTraverse(LinkQueue Q,void(*vi)(QElemType))
{ / 从队头到队尾依次对队列Q中每个元素调用函数vi() /
QueuePtr p;
p=Q.front->next;
while(p)
{
vi(p->data);
p=p->next;
}
printf("\n");
}
循环队列
循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。
// 队列的顺序存储结构(循环队列)
#define MAX_QSIZE 5 // 最大队列长度+1
typedef struct {
int *base; // 初始化的动态分配存储空间
int front; // 头指针，若队列不空，指向队列头元素
int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
} SqQueue;
// 构造一个空队列Q
SqQueue* Q_Init() {
SqQueue Q = (SqQueue)malloc(sizeof(SqQueue));
// 存储分配失败
if (!Q){
exit(OVERFLOW);
}
Q->base = (int )malloc(MAX_QSIZE sizeof(int));
// 存储分配失败
if (!Q->base){
exit(OVERFLOW);
}
Q->front = Q->rear = 0;
return Q;
}
// 销毁队列Q，Q不再存在
void Q_Destroy(SqQueue *Q) {
if (Q->base)
free(Q->base);
Q->base = NULL;
Q->front = Q->rear = 0;
free(Q);
}
// 将Q清为空队列
void Q_Clear(SqQueue *Q) {
Q->front = Q->rear = 0;
}
// 若队列Q为空队列，则返回1；否则返回-1
int Q_Empty(SqQueue Q) {
if (Q.front == Q.rear) // 队列空的标志
return 1;
else
return -1;
}
// 返回Q的元素个数，即队列的长度
int Q_Length(SqQueue Q) {
return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;
}
// 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
int Q_GetHead(SqQueue Q, int &e) {
if (Q.front == Q.rear) // 队列空
return -1;
e = Q.base[Q.front];
return 1;
}
// 打印队列中的内容
void Q_Print(SqQueue Q) {
int p = Q.front;
while (Q.rear != p) {
cout rear + 1) % MAX_QSIZE == Q->front) // 队列满
return -1;
Q->base[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAX_QSIZE;
return 1;
}
// 若队列不空，则删除Q的队头元素，用e返回其值，并返回1；否则返回-1
int Q_Poll(SqQueue *Q, int &e) {
if (Q->front == Q->rear) // 队列空
return -1;
e = Q->base[Q->front];
Q->front = (Q->front + 1) % MAX_QSIZE;
return 1;
}
陣列佇列
#define MAX_QSIZE 10 // 最大队列长度+1
// 阵列队列的存储结构
struct Queue {
int Array[MAX_QSIZE]; // 阵列空间大小
int front; // 队头
int rear; // 队尾
int length; // 队列长度
};
// 构造一个空队列Q
Queue* Q_Init() {
Queue Q = (Queue)malloc(sizeof(Queue));
if (!Q){
// 存储分配失败
exit(OVERFLOW);
}
//初始化
Q->front = Q->rear = Q->length = 0;
return Q;
}
// 将Q清为空队列
void Q_Clear(Queue *Q) {
//清除头尾下标和长度
Q->front = Q->rear = Q->length = 0;
}
// 入列
int Q_Put(Queue *Q, int x) {
//如果当前元素数量等于最大数量 返回 -1
if (Q->rear + 1 == MAX_QSIZE) {
return -1;
}
Q->Array[Q->rear] = x;
Q->rear = Q->rear + 1;
//length + 1
Q->length = Q->length + 1;
return 1;
}
// 出列
int Q_Poll(Queue *Q) {
//如果当前元素数量等于最大数量 返回 -1
if (Q->front + 1 == MAX_QSIZE)
return -1;
int x = Q->Array[Q->front];
Q->front = Q->front + 1;
// 移出后減少1
Q->length = Q->length - 1;
return x;
}
参考文献
参见
- 堆栈
- 链表
- 数组
- 数据结构
评论 (0)