队列的实现（C语言）

 

1.结构体设计

结构说明：使用单链表作为基础的数据结构 链表结点存储数据和下一个结点地址

但是队列要可以访问队头和队尾 函数需要传两个指针参数 所以单独设计一个结构体存储这两个结点指针front和rear

再创建一个size记录队列结点个数

typedef int QueueNodeDataType;
typedef struct QListNode
{struct QListNode* _pNext;QueueNodeDataType _data;
}QNode;typedef struct Queue
{QNode* _front;QNode* _rear;int _size;
}Queue;

2.功能设计

2.1 初始化： 将队列的front和rear都置为空 队列内有效元素置为0

void QueueInit(Queue* q)
{assert(q);q->_front = NULL;q->_rear = NULL;q->_size = 0;
}

2.2 插入元素设计 队尾入队列：判断front为不为空

1.为空则说明front和rear都要置为newNode

2.不为空则说明只需要改变rear即可 申请新节点链接到链表中 改变rear

void QueuePush(Queue* q, QueueNodeDataType val)
{assert(q);QNode* newNode = (QNode*)malloc(sizeof(QNode));assert(newNode);newNode->_data = val;newNode->_pNext = NULL;if (q->_front == NULL)//队列没有结点{q->_front = q->_rear = newNode;}else{q->_rear->_pNext = newNode;q->_rear = newNode;}q->_size++;
}

2.3 队头出队列：

判断队列为不为空 为空则返回 不为空分两种情况

1.只有一个结点 将front和rear都置为NULL

2.多个结点 只将front指向它的下一个结点即可

void QueuePop(Queue* q)
{assert(q);if (q->_front == NULL){return;}else{if (q->_front == q->_rear)//说明只有一个结点{free(q->_front);q->_front = q->_rear = NULL;}else{QNode* cur = q->_front->_pNext;free(q->_front);q->_front = cur;}}q->_size--;
}

2.4 判空：为空返回true 不为空返回false

bool QueueEmpty(Queue* q)
{assert(q);return q->_front == NULL;
}

2.5 取队列头元素和取队列尾部元素：判断队列为空的情况

QueueNodeDataType QueueFront(Queue* q)
{assert(q);assert(q->_front);return q->_front->_data;
}
QueueNodeDataType Queuerear(Queue* q)
{assert(q);assert(q->_rear);return q->_rear->_data;
}

2.6 返回队列有效元素个数：返回size

int QueueSize(Queue* q)
{assert(q);return q->_size;
}

2.7 销毁队列：遍历队列 销毁结点

void QueueDestory(Queue* q)
{assert(q);QNode* cur = q->_front;while (cur){QNode* tmp = cur;cur = cur->_pNext;free(tmp);}q->_front = q->_rear = NULL;}

整体代码 

Queue.h 

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include<stdbool.h>typedef int QueueNodeDataType;
typedef struct QListNode
{struct QListNode* _pNext;QueueNodeDataType _data;
}QNode;typedef struct Queue
{QNode* _front;QNode* _rear;int _size;
}Queue;void QueueInit(Queue* q);
void QueuePush(Queue* q, QueueNodeDataType val);
void QueuePop(Queue* q);
bool QueueEmpty(Queue* q);
int QueueSize(Queue* q);
QueueNodeDataType QueueFront(Queue* q);
QueueNodeDataType Queuerear(Queue* q);
void QueueDestory(Queue* q);

Queue.c 

#include"queue.h"
void QueueInit(Queue* q)
{assert(q);q->_front = NULL;q->_rear = NULL;q->_size = 0;
}
void QueuePush(Queue* q, QueueNodeDataType val)
{assert(q);QNode* newNode = (QNode*)malloc(sizeof(QNode));assert(newNode);newNode->_data = val;newNode->_pNext = NULL;if (q->_front == NULL)//队列没有结点{q->_front = q->_rear = newNode;}else{q->_rear->_pNext = newNode;q->_rear = newNode;}q->_size++;
}
void QueuePop(Queue* q)
{assert(q);if (q->_front == NULL){return;}else{if (q->_front == q->_rear)//说明只有一个结点{free(q->_front);q->_front = q->_rear = NULL;}else{QNode* cur = q->_front->_pNext;free(q->_front);q->_front = cur;}}q->_size--;
}
bool QueueEmpty(Queue* q)
{assert(q);return q->_front == NULL;
}
int QueueSize(Queue* q)
{assert(q);return q->_size;
}
QueueNodeDataType QueueFront(Queue* q)
{assert(q);assert(q->_front);return q->_front->_data;
}
QueueNodeDataType Queuerear(Queue* q)
{assert(q);assert(q->_rear);return q->_rear->_data;
}
void QueueDestory(Queue* q)
{assert(q);QNode* cur = q->_front;while (cur){QNode* tmp = cur;cur = cur->_pNext;free(tmp);}q->_front = q->_rear = NULL;}