队列的概念
队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的FIFO(First in First Out)。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。
同样可以使用链表或者数组
数组：不是适合，队头出数据需要挪动数据。
链表：适合单链表，单链表头删效率很高。
结构定义
typedef int QueueDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QueueDataType data;
}QueueNode;
//单链表除了尾插还要尾删，所以不会加这个
typedef struct Queue
{
QueueNode* tail;
QueueNode* head;
}Queue;
初始化
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->tail = pq->head = NULL;
}
销毁
void QueueDestory(Queue* pq)
{
assert(pq);
//定义一个新结点
QueueNode* cur = pq->head;
while (cur)
{
//依次保存下一个结点，然后删除这个结点
QueueNode* curNext = cur->next;
free(cur);
cur = curNext;
}
pq->head = pq->tail = NULL;
}
队尾入
void QueuePush(Queue* pq, QueueDataType x)
{
assert(pq);
//创建新结点
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
//创建失败
if (newnode == NULL)
{
printf("malloc is fail\n");
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;
}
}
队头出
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head);//队列是不等于空的
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
//先保存下一个结点
QueueNode* nextNode = pq->head->next;
free(pq->head);
pq->head = nextNode;
}
}
队头出
QueueDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
队头数据
QueueDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
队尾数据
QueueDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->tail->data;
}
是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
返回数据个数
int QueueSize(Queue* pq)
{
assert(pq);
int size = 0;
QueueNode* cur = pq->head;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
全部代码
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//结构定义
typedef int QueueDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QueueDataType data;
}QueueNode;
//单链表除了尾插还要尾删，所以不会加这个
typedef struct Queue
{
QueueNode* tail;
QueueNode* head;
}Queue;
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->tail = pq->head = NULL;
}
//销毁
void QueueDestory(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* curNext = cur->next;
free(cur);
cur = curNext;
}
pq->head = pq->tail = NULL;
}
//队尾入
void QueuePush(Queue* pq, QueueDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
printf("malloc is fail\n");
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;
}
}
//队头出
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head);//队列是不等于空的
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
//先保存一下下一个结点
QueueNode* nextNode = pq->head->next;
free(pq->head);
pq->head = nextNode;
}
}
//队头数据
QueueDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
//队尾数据
QueueDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->tail->data;
}
//是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
//返回数据个数
int QueueSize(Queue* pq)
{
assert(pq);
int size = 0;
QueueNode* cur = pq->head;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
void Test1()
{
Queue pq;
QueueInit(&pq);
QueuePush(&pq, 1);
QueuePush(&pq, 2);
QueuePush(&pq, 3);
QueuePush(&pq, 4);
//为空是假的才成立，进入循环(不为空，进入循环)
while (!QueueEmpty(&pq))
{
//取队头的数据然后删除
printf("%d ", QueueFront(&pq));
QueuePop(&pq);
}
QueueDestory(&pq);
}
int main(void)
{
Test1();
return 0;
}
