队列的定义队列的结构队列的基本操作队列的实现
队列的定义
你平时有观察过排队的现象吗？
取票的时候，先进去取票的人先出来，而后面来的只能在队尾排队。
数据结构里的队列也是这样的性格。
队列（Queue）也是一种特殊的线性表，它只允许在固定的一端进行插入元素的操作，另一端进行删除操作。没有元素的队列被称为空队列。进行插入操作的这一端被称为队尾（rear），另一端则被称为队头（front）。
队列的特点是，最先入队列的最早出队列，即“先进先出”
队列的结构❤️ 队列同链表相似，有 顺序队列和链式队列两种，顺序队列由数组实现，而链式队列则由链表实现。
【顺序队列】
顺序队列中，在队尾插入元素和在队头删除数据指针都在增加，这意味着队列在整体后移。但是顺序队列是用数组实现的，数组的长度是固定的，当队尾指针移到数组尾部时，数组前面往往由于元素出队列而空出大量可用的空间，也就是指这些空出来的空间是已经出队的队列元素以前所占用过的存储单元。
为了克服这种现象导致的浪费，通常会使用顺序队列中的循环队列。
当指针rear或front到达存储空间末尾的时候，再加一就能够使它们指向存储空间的开头。
【链式队列】
链式队列比顺序队列更加灵活，不需要考虑溢出，需要空间时开辟新节点就可以。
typedef int QDataType;
//节点
typedef struct Node
{
struct Node* next;
QDataType data;
}QueueNode;
//队头尾指针
typedef struct Queue
{
struct Node* front;
struct Node* rear;
}Queue;
【本文采用链式队列】
队列的基本操作void* InitQueue(Queue* sq); 作用：创建一个空队列 void* DestroyQueue(Queue* sq); 调用条件：队列sq存在 作用：销毁队列 void QueuePush(Queue* sq, QDataType x); 调用条件：队列sq存在 作用：将x这个元素入队列 void QueuePop(Queue* sq); 调用条件：队列sq存在且不为空队列 作用：队头出一个元素 QDataType QueueFront(Queue* sq); 调用条件：队列sq存在且不为空队列 作用：返回队头的元素 QDataType QueueRear(Queue* sq); 调用条件：队列sq存在且不为空队列 作用：返回队尾的元素 int QueueSize(Queue* sq); 调用条件：队列sq存在 作用：返回队列有效元素的个数 bool QueueEmpty(Queue* sq); 调用条件：队列sq存在 作用：判断队列是否为空，为空返回true，反之返回false队列的实现
# include# include # include typedef int QDataType; //节点 typedef struct Node { struct Node* next; QDataType data; }QueueNode; //队头尾指针 typedef struct Queue { struct Node* front; struct Node* rear; }Queue; //初始化 void* InitQueue(Queue* sq); //销毁队列 void* DestroyQueue(Queue* sq); //入队列 void QueuePush(Queue* sq, QDataType x); //出队列 void QueuePop(Queue* sq); //队头元素 QDataType QueueFront(Queue* sq); //队尾元素 QDataType QueueRear(Queue* sq); //队列有效元素大小 int QueueSize(Queue* sq); //判断队列是否为空 bool QueueEmpty(Queue* sq); //初始化 void* InitQueue(Queue* sq) { assert(sq); sq->front = NULL; sq->rear = NULL; } //销毁队列 void* DestroyQueue(Queue* sq) { assert(sq); QueueNode* cur = sq->front; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } sq->front = sq->front = NULL; } //入队列 void QueuePush(Queue* sq, QDataType x) { assert(sq); //开辟新节点 QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { printf("malloc failn"); exit(-1); } newnode->data = x; newnode->next = NULL; //空队列插入 if (sq->front == NULL) { sq->front = sq->rear = newnode; } else { //尾插 sq->rear->next = newnode; sq->rear = newnode; } } //出队列 void QueuePop(Queue* sq) { assert(sq); if (sq->front == NULL) return; QueueNode* next = sq->front->next; free(sq->front); sq->front = next; //如果队头为空指针，将队尾也置为空指针 if (sq->front == NULL) { sq->rear = NULL; } } //队头元素 QDataType QueueFront(Queue* sq) { assert(sq); assert(!QueueEmpty(sq)); //非空队列 return sq->front->data; } //队尾元素 QDataType QueueBack(Queue* sq) { assert(sq); assert(!QueueEmpty(sq)); return sq->rear->data; } //队列有效元素大小 int QueueSize(Queue* sq) { assert(sq); int count = 0; QueueNode* cur = sq->front; while (cur) { count++; cur = cur->next; } return count; } //判断队列是否为空 bool QueueEmpty(Queue* sq) { assert(sq); return sq->front == NULL; }
