数据结构之队列
【摘要】 1.概述
队列是一种操作受限的线性表，它只允许在一端进行元素插入，而在另一端进行元素删除。允许插入的一端，称为队尾，允许删除的一端，称为队头。 在队列的操作中，插入称为入队，删除称为出队。
新来的成员总是加入队尾，排在队列前面的元素总是最先离开队列，由于这种先进先出的特性，让队列又叫先进先出表。
队列可以用顺序存储，也可以用链式存储，前者叫顺序队列，后者叫链队列。...
1.概述
队列是一种操作受限的线性表，它只允许在一端进行元素插入，而在另一端进行元素删除。允许插入的一端，称为队尾，允许删除的一端，称为队头。 在队列的操作中，插入称为入队，删除称为出队。
新来的成员总是加入队尾，排在队列前面的元素总是最先离开队列，由于这种先进先出的特性，让队列又叫先进先出表。
队列可以用顺序存储，也可以用链式存储，前者叫顺序队列，后者叫链队列。
2.顺序队列与链队列
2.1顺序队列定义
#define QueueSize 100
typedef int DataType;
typedef struct { DataType data[QueueSize]; int front,rear;// 记录头和尾
} SeqQueue;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.1.1顺序队列基本运算
// 置空队列
void initQueue(SeqQueue *Q){ Q->front = Q->rear = 0;
}
// 判队空
int queueEmpty(SeqQueue *Q){ return Q->front == Q->rear;
}
// 判队満
int queueFull(SeqQueue *Q){ if(Q->rear > 0){ // 加１的原因请参考后面讲到的循环队列对边界条件的处理 return （Q->rear+1) % QueueSize == 0; }else{ return 0; }
}
// 入队列
void enQueue(SeqQueue *Q,DataType x){ // 插入元素x为队列新的队尾元素 if(queueFull(Q)){ printf("Queue overflow"); }else{ Q->data[Q->rear] = x; Q->rear = Q->rear + 1; }
}
// 出队列
DataType deQueue(SeqQueue *Q){ DataType x; if(queueEmpty(Q)){ printf("Queue empty"); exit(0); }else{ x = Q->data[Q->front]; Q->front = Q->front+1; return x; }
}
// 取队头
DataType GetFront(SeqQueue *Q){ if(queueEmpty(Q)){ printf("Queue empty"); exit(0); }else{ return Q->data[Q->front];// 返回队头元素 }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
2.2链队列定义
typedef int DataType;
// 链队列结点类型
typedef struct qnode{ DataType data; struct qnode* next;
} QueueNode;
// 链队列类型
typedef struct{ QueueNode* front;// 队头指针 QueueNode* rear;// 队尾指针
} LinkQueue;
LinkQueue Q;//定义一个链队列Q
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
2.2.1链队列基本运算
链队列一般是不带头结点的，为了简化边界条件的处理，在队头结点之前添加了一个头结点，并设头结点指向队头结点，下面的运算也是带有头结点的链队列的运算：
// 构造空队列
void initQueue(LinkQueue *Q){ Q->front = (QueueNode *)malloc(sizeof(QueueNode));// 申请头结点 Q->rear = Q->front; Q->rear->next = NULL;
}
// 判队空
int queueEmpty(LinkQueue *Q){ return Q->rear == Q->front;
}
// 入队列
void enQueue(LinkQueue *Q,DataType x){ QueueNode * p = (QueueNode *)malloc(sizeof(QueueNode));// 申请新结点o p->data = x; p->next = NULL; Q->rear->next = p; // p链到原队尾结点之后 Q->rear = p;// 队尾指针指向新的队尾结点
}
// 出队列
DataType deQueue(LinkQueue *Q){ QueueNode *p; if(queueEmpty(Q)){ printf("Queue underflow"); exit(0); }else{ p = Q->front;// p指向头结点 Q->front = Q->front->next;// 头指针指向原队头结点 free(p);// 删除释放原头结点 return (Q->front->data);// 返回原队头结点的数据 }
}
// 取队头元素
DataType getFront(LinkQueue *Q){ if(queueEmpty(Q)){ printf("Queue underflow"); exit(0); }else{ return Q->front->next->data; }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
出队列的操作中：
当队列的长度大于１，则出队操作只需要修改头结点的指针域即可，尾指针不变：
s=Q->front->next;
Q->front->next = s->next;
x=s->data;
free(s);
return x;
- 1
- 2
- 3
- 4
- 5
当队列的长度刚好等于１时，则出队操作不仅要修改头结点还要修改尾指针
s=Q->front->next;
Q->front->next = NULL;
Q->rear=Q->front;
x=s->data;
free(s);
return x;
- 1
- 2
- 3
- 4
- 5
- 6
那么为了统一以上两种操作，就有了我们一开始给出的出队操作。
3.顺序循环队列与循环链队列
在循环队列的运算中，要涉及一些边界条件要处理。由于入队时的尾指针Q->rear向前追赶头指针Q->front，出队时头指针向前追赶尾指针，如果尾指针追赶上头指针说明队满，如果头指针追赶上尾指针，说明队空。因此，无论是空还是满，Ｑ->rear==Q->front都成立。由此可见，仅凭队列的头尾指针是否相等是无法判断队空还是队满。解决方法有多种，我们提供可能的三种：
- 另外设立一个标志位，用来区别队空和队满
- 用计数器记录队列中元素的个数
- 少用一个元素空间，约定入队前，测试尾指针在循环意义下加１后，是否等于头指针，如果相等，则认为队满，即尾指针Ｑ->rear所指向的单元始终是空的。
3.1顺序循环队列定义
与顺序队列的定义是一样的。一般情况下，真正实用的顺序队列是循环队列。
#define QueueSize 100
typedef int DataType;
typedef struct { DataType data[QueueSize]; int front,rear;// 记录头和尾
} CirQueue;
- 1
- 2
- 3
- 4
- 5
- 6
3.1.1顺序循环队列基本运算
// 置空队列
void initQueue(CirQueue *Q){ Q->front = Q->rear = 0;
}
// 判队空
int queueEmpty(CirQueue *Q){ return Q->front == Q->rear;
}
// 判队満
int queueFull(CirQueue *Q){ return (Q->rear + 1) % QueueSize == Q->front;
}
// 入队列
void enQueue(CirQueue *Q,DataType x){ // 插入元素x为队列新的队尾元素 if(queueFull(Q)){ printf("Queue overflow"); }else{ Q->data[Q->rear] = x; Q->rear = (Q->rear + 1) % QueueSize;// 这里是循环的重要部分，这里使用数组可以循环使用 }
}
// 出队列
DataType deQueue(CirQueue *Q){ DataType x; if(queueEmpty(Q)){ printf("Queue empty"); exit(0); }else{ x = Q->data[Q->front]; Q->front = (Q->front+1) % QueueSize;//只有这样才能让头指针回到开始的地方 return x; }
}
// 取队头
DataType GetFront(CirQueue *Q){ if(queueEmpty(Q)){ printf("Queue empty"); exit(0); }else{ return Q->data[Q->front];// 返回队头元素 }
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
3.2循环链队列定义
与链队列的定义是一样的。
typedef int DataType;
typedef struct qnode{ DataType data; struct qnode * next;
} QueueNode;
typedef struct { QueueNode * front; QueueNode * rear;
} CirLinkQueue;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
3.2.1循环链队列基本运算
// 初始化队列
void initQueue( CirLinkQueue * Q){ Q->front=Q->rear = (QueueNode *)malloc(sizeof(QueueNode)); Q->front->next = Q->front;
}
// 判队空
int queueEmpty(CirLinkQueue *Q){ return Q->front->next == Q->front;
}
// 入队列
// 在队列中插入一个结点是在队尾进行的。过程：
// １、首先生成一个新结点s，因为链表带头结点，所有队空与否对插入没有影响；
// ２、将尾指针域值赋给新结点的指针域；
// ３、同时将新结点指针赋给尾的指针域
// ４、最后，移动尾指针指向最后一个结点，其实就是将新结点指针赋给尾指针
//
void enQueue(CirLinkQueue *Q,DataType x){ // 插入元素x为队列新的队尾元素 QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode)); p->data = x; p->next = Q->rear->next; Q->rear->next = p; Q->rear = p;
}
// 出队列
DataType deQueue(CirLinkQueue *Q){ DataType x; if(queueEmpty(Q)){ printf("Queue empty"); exit(0); }else{ x = Q->front->next->data; Q->front->next = Q->front->next->next; return x; }
}
// 取队头
DataType GetFront(CirLinkQueue *Q){ if(queueEmpty(Q)){ printf("Queue empty"); exit(0); }else{ return Q->front->next->data;// 返回队头元素 }
}
// 队列长度
int queueLength(CirLinkQueue *Q){ int count; QueueNode *p = Q->front; while(p != Q->rear){ ++count; p=p->next; } return count;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
以上就是队列相关的内容，谢谢！
文章来源: blog.csdn.net，作者：WongKyunban，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/weixin_40763897/article/details/105404841
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）