队列的概念
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
队列的实现
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。
队列定义
typedef int QDataType;
struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;
- 将int重命名为QDataType,方便后续对数据结构的修改
- 创建QueueNode,队列节点结构体,包含next指针和数据域,重命名为QNode
- 创建Queue队列结构体,里面存放队头节点和队尾节点以及队列大小,重命名为Que
初始化
void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
- 判断pq是否为空
- 将head与tail指针置为空
- 将size置为0
销毁
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}
-
判断pq是否为空
-
创建一个cur指针,指向head,即队头的节点
-
将cur->next赋给cur,往后边遍历边释放节点空间,直到cur为空
-
将head与tail置空,size置为0
入队
void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
-
判断pq是否为空
-
malloc一个新QNode节点
-
将newnode的data赋为x,next赋为空
-
如果tail指向空,表示队列为空,将head和tail指向newnode
-
否则,将tail的next指向newnode,再将tail指向newnode
-
最后size++
出队
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}
-
判断pq是否为空
-
判断队列是否为空
-
如果head->next为空,表示只有队列里只有一个节点,直接free掉head节点,并将head和tail都置为空
-
否则将创建next节点来保存第二个节点,再free掉第一个节点,再将head指向第二个节点
-
最后size–
返回队头
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}
- 判断pq是否为空
- 判断队列是否为空
- 返回head指针的data域
返回队尾
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
- 判断pq是否为空
- 判断队列是否为空
- 返回tail指针的data域
判空
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}
- 判断pq是否为空
- 返回head指针是否为空,是空返回true,否则返回false
返回队列大小
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}
- 判断pq是否为空
- 返回size
队列声明定义分离实现
#pragma#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int QDataType;
struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);
#include "Queue.h"void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}int QueueSize(Que* pq)
{assert(pq);return pq->size;
}