【数据结构】顺序队列模拟实现

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 ：阿然成长日记 👈点击可跳转
📆 个人专栏： 🔹数据结构与算法🔹C语言进阶
🚩 不能则学，不知则问，耻于问人，决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

一、队列的定义：

一、队列的基本概念

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出 （First In FirstOut）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头

二、链式结构队列的模拟实现

1.结构图;

使用单向链表

初始状态:（队空条件）：Q->front == Q->rear == 0。
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
出队操作：队不空时，先取队头元素值，再将队头指针加1。

2.队列的结构体

在这里我使用的是单链表的形式来模拟队列。

//定义data数据类型
typedef int QueueDataType;//定义节点
typedef struct QueueNode
{struct QueueNode* next;QueueDataType data;
}QNode;//定义队列
typedef struct QueueList
{//头指针QNode* head;//尾指针QNode* tail;//链表长度int size;
}QList;

3.初始化

这里没有设置头节点，初始化时，两个指针都指向空。

//初始化
void QueueInit(QList* p)
{assert(p);p->head = p->tail = NULL;p->size = 0;
}

4.销毁队列

需要注意 由于动态分配的内存空间 ，在使用完队列之后，要把申请的空间及时的释放掉。具体做法就是遍历单链表，释放每一个节点。的遍历每一个节点，并对节点进行释放

//销毁队列
void QueueDestroy(QList* p)
{assert(p);QNode* cur = p->head;while (cur){QNode* next = cur->next;free(cur);cur = cur->next; }p->head = p->tail = NULL;p->size = 0; 
}

5.入队（尾插）

注意为空时的插入，与存在节点时，分情况讨论

//入队（尾插）
void QueuePush(QList* p, QueueDataType x)
{assert(p);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (p->head == NULL){p->head = p->tail = newnode;}else{p->tail->next = newnode;p->tail = p->tail->next;}p->size++;
}

6.出队（头删）

//出队（头删）
void QueuePop(QList* p)
{assert(p);assert(!IsEmpty(p));//当只有一个节点时 if (p->head->next == NULL){free(p->head);p->head = p->tail = NULL;}//当有两个或两个以上节点else{QNode* phead = p->head->next;free(p->head);p->head->next = phead;}p->size--;
}

7.获取队头

//获取队头
QueueDataType QueueHead(QList* p)
{assert(p);assert(!IsEmpty(p));return p->head->data;
}

8.获取队尾

//获取队尾
QueueDataType QueueTail(QList* p)
{assert(p);assert(!IsEmpty(p));return p->tail->data;
}

9.判断是否为空

//判断是否为空
bool IsEmpty(QList* p)
{assert(p);return p->head == NULL;
}

10.获取队列长度

//获取队列长度
int QueueSize(QList* p)
{return p->size;
}