队列的链式存储结构,简单看来和线性表的单链表非常相似,只不过,链式存储的队列,只可以在队尾rear
入队,队头front
出队。
同样为了方便,在队列前添加头结点。
1.1 链式存储队列结构设计:
// 结点结构
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QListNode;
// 队列链表结构
typedef struct {
QListNode front; // 队头
QListNode rear; // 队尾
}SqQueue;
1.2 初始化队列 将队列的front,rear都指向新建的头结点。
// 初始化
Status InitQueue(SqQueue *Q){
Q->front = Q->rear = (QListNode)malloc(sizeof(QListNode));
if (!Q->front) {
return ERROR;
}
Q->front->next = NULL; // 头结点的指针域置空 此处Q->rear的next同样指向空
return OK;
}
1.3 添加入队,只需要调整rear就可以,front始终指向头结点。
// 添加元素
Status EnterQueue(SqQueue *Q,QElemType e){
if (!Q) {
return ERROR;
}
QListNode temp = (QListNode)malloc(sizeof(QNode));
if (!temp) {
return ERROR;
}
temp->data = e;
temp->next = NULL; // 要将新结点的next指向空,以免脏数据
Q->rear->next = temp;
Q->rear = temp; // 调整rear 指向最新的结点
return OK;
}
1.4 删除出队
删除要注意两个条件:
- 删除前判断队列是否是空的
- 判断要删除的是不是最后一个元素
// 删除
Status DeleteQueue(SqQueue *Q,QElemType *e){
if (!Q) {
return ERROR;
}
if (Q->front == Q->rear) { // 判断是否为空
printf("队列已空\n");
return ERROR;
}
QListNode temp = Q->front->next;
*e = temp->data;
Q->front->next = temp->next; // 要把头结点的next指向要删除结点的next
if (Q->rear == temp) { // 假如要删除的是最后一个,要把rear指向头结点
Q->rear = Q->front;
}
free(temp);
return OK;
}
1.5 遍历所有元素
// 遍历
Status QueueTrave(SqQueue Q){
QListNode temp = Q.front->next;
while (temp) {
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
return OK;
}
1.6 队列长度
通过遍历每一个结点,计算遍历的次数,来获取队列的长度。
获取队列长度也可以在设计队列时,添加count,每次入列出列进行count加减
// 队列长度
int QueueLength(SqQueue Q){
if (Q.front != Q.rear) {
QListNode temp = Q.front->next;
int count = 0;
while (temp) {
count++;
temp = temp->next;
}
return count;
}
return 0;
}
1.7 队列清空
- 将rear重新指向头结点
- 遍历所有的结点,free掉
- 将front的next指向为null
// 清空
Status ClearQueue(SqQueue *Q){
if (!Q) {
return ERROR;
}
if (Q->front == Q->rear) { // 判断队列是否为空
return ERROR;
}
Q->rear = Q->front;
QListNode temp = Q->front->next;
while (temp) {
QListNode p = temp->next;
free(temp);
temp = p;
}
Q->front->next = NULL;
return OK;
}
1.8 销毁队列
// 销毁
Status DestoryQueue(SqQueue *Q){
QListNode temp = Q->front;
while (temp) {
QListNode p = temp->next;
free(temp);
temp = p;
}
/* 销毁不用在意front rear ,所以也可以不用太多其它的参数,如下
while (Q->front) {
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}*/
return OK;
}