目录
一、队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
下面用一张图来看清楚队列的结构：
二、队列的实现
与栈的实现不同，队列的实现一般是基于数组的。虽然队列既可以数组也可以用链表的结构实现，但是在实际使用中，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
2.1 队列的初始化
void QueueInit(Queue* q)
{
q->front = NULL;
q->rear = NULL;
}2.2 入列
QNode* buyNewnode(QDataType x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc failed");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
QNode* newnode = buyNewnode(data);
assert(q);
if (q->rear == NULL)
{
q->front = newnode;
q->rear = newnode;
}
else
{
q->rear->next = newnode;
q->rear = newnode;
}
}2.3 出列
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->front != NULL);
QNode* Next = q->front->next;
if (q->front == NULL)
{
q->rear = NULL;
}
free(q->front);
q->front = Next;
}2.4 获取队头元素
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->front != NULL);
return q->front->data;
}2.5 获取队尾元素
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->rear != NULL);
return q->rear->data;
}2.6 获取队列内有效元素个数
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
int size = 0;
QNode* current = q->front;
while (current != NULL)
{
size++;
current = current->next;
}
return size;
}2.7 销毁队列
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* current = q->front;
while (current != NULL)
{
QNode* temp = current;
current = current->next;
free(temp);
}
q->front = NULL;
q->rear = NULL;
}三、测试代码
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* front;
QNode* rear;
}Queue;
// 初始化队列
void QueueInit(Queue* q)
{
q->front = NULL;
q->rear = NULL;
}
QNode* buyNewnode(QDataType x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc failed");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
QNode* newnode = buyNewnode(data);
assert(q);
if (q->rear == NULL)
{
q->front = newnode;
q->rear = newnode;
}
else
{
q->rear->next = newnode;
q->rear = newnode;
}
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->front != NULL);
QNode* Next = q->front->next;
if (q->front == NULL)
{
q->rear = NULL;
}
free(q->front);
q->front = Next;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->front != NULL);
return q->front->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->rear != NULL);
return q->rear->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
int size = 0;
QNode* current = q->front;
while (current != NULL)
{
size++;
current = current->next;
}
return size;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* current = q->front;
while (current != NULL)
{
QNode* temp = current;
current = current->next;
free(temp);
}
q->front = NULL;
q->rear = NULL;
}
int main()
{
Queue q;
QueueInit(&q);
// 测试入队
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
// 测试队列头部元素
printf("队列头部元素: %d\n", QueueFront(&q)); // 应该输出1
// 测试队列尾部元素
printf("队列尾部元素: %d\n", QueueBack(&q)); // 应该输出4
// 测试队列大小
printf("队列大小: %d\n", QueueSize(&q)); // 应该输出4
// 测试出队
QueuePop(&q);
printf("队列头部元素: %d\n", QueueFront(&q)); // 应该输出2
// 测试队列大小
printf("队列大小: %d\n", QueueSize(&q)); // 应该输出3
// 清空队列
while (QueueSize(&q) > 0)
{
printf("弹出元素: %d\n", QueueFront(&q));
QueuePop(&q);
}
// 测试队列是否为空
printf("队列是否为空: %d\n", QueueSize(&q) == 0); // 应该输出1（true）
// 销毁队列
QueueDestroy(&q);
return 0;
}