数据结构
文章目录
- 数据结构
- 一、什么是队列
- 二、队列的实现
- 1.队列的结构
- 2.队列的初始化
- 3.入队
- 4.出队
- 6.队头队尾的获取
- 总结
一、什么是队列
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)。
入队:进行插入操作的一端称为队尾。
![在这里插入图片描述](https://img-blog.csdnimg.cn/f8d37f2a6e144c39930aaf44139b4bc8.png)
出队:进行删除操作的一端称为队头。
![在这里插入图片描述](https://img-blog.csdnimg.cn/475250d222a24af4b87307157a7931bc.png)
队列也是分为顺序队列和链式队列
二、队列的实现
1.队列的结构
队列需要同时在队头和队尾进行操作,这里使用链表实现。
但由于链表访问队尾时效率较低,所以用tail结构体指针指向链表的末尾。
typedef int QNDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QNDataType val;
}QueueNode;
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
2.队列的初始化
void QueueInit(Queue* pq)
{
pq->head = NULL;
pq->tail = NULL;
printf("队列初始化成功\n");
}
![在这里插入图片描述](https://img-blog.csdnimg.cn/c2fd87d4381746f8ac3b4aa8ec75f4da.png)
3.入队
void QueuePush(Queue* pq, QNDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
exit(-1);
}
newnode->val = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->head = newnode;
pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
printf("%d入队成功\n",x);
}
![在这里插入图片描述](https://img-blog.csdnimg.cn/627bbfbba6e14a0fbfb95d9de54c14f9.png)
4.出队
void QueuePop(Queue* pq)
{
assert(pq);
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = NULL;
pq->tail = NULL;
i++;
}
else
{
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
i++;
}
printf("第%d个数出队成功\n",i);
}
![在这里插入图片描述](https://img-blog.csdnimg.cn/40875979f9984cca86abd4902d9b8a65.png)
5.队列的判断
void QueueEmpty(Queue* pq)
{
assert(pq);
if(pq->head == NULL)
printf("队列为空\n");
else
printf("队列不为空\n");
}
int QueueSize(Queue* pq)
{
int size = 0;
QueueNode* cur = pq->head;
while (cur)
{
size++;
cur = cur->next;
}
printf("队列长度为%d\n",size);
}
![在这里插入图片描述](https://img-blog.csdnimg.cn/63c69d324f1a40db80a786d8060c0aa0.png)
6.队头队尾的获取
QNDataType QueueFront(Queue* pq)
{
assert(pq);
if(pq->head!=NULL)
printf("队头数据为%d\n",pq->head->val);
else
printf("无队头");
}
QNDataType QueueBack(Queue* pq)
{
assert(pq);
if(pq->tail!=NULL)
printf("队尾数据为%d\n",pq->tail->val);
else
printf("无队尾");
}
![在这里插入图片描述](https://img-blog.csdnimg.cn/a9056f41391d4287ba43d7946693837b.png)
总结
附上完整代码
#include<stdio.h>
#include<assert.h>
static i=0;
typedef int QNDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QNDataType val;
}QueueNode;
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
void QueueInit(Queue* pq)
{
pq->head = NULL;
pq->tail = NULL;
printf("队列初始化成功\n");
}
void QueuePush(Queue* pq, QNDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
exit(-1);
}
newnode->val = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->head = newnode;
pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
printf("%d入队成功\n",x);
}
void QueuePop(Queue* pq)
{
assert(pq);
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = NULL;
pq->tail = NULL;
i++;
}
else
{
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
i++;
}
printf("第%d个数出队成功\n",i);
}
void QueueEmpty(Queue* pq)
{
assert(pq);
if(pq->head == NULL)
printf("队列为空\n");
else
printf("队列不为空\n");
}
int QueueSize(Queue* pq)
{
int size = 0;
QueueNode* cur = pq->head;
while (cur)
{
size++;
cur = cur->next;
}
printf("队列长度为%d\n",size);
}
QNDataType QueueFront(Queue* pq)
{
assert(pq);
if(pq->head!=NULL)
printf("队头数据为%d\n",pq->head->val);
else
printf("无队头");
}
QNDataType QueueBack(Queue* pq)
{
assert(pq);
if(pq->tail!=NULL)
printf("队尾数据为%d\n",pq->tail->val);
else
printf("无队尾");
}
int main()
{
QueueNode que;
QueueInit(&que);
QueuePush(&que,1) ;
QueuePush(&que,5) ;
QueueEmpty(&que);
QueueSize(&que);
QueueFront(&que);
QueueBack(&que);
QueuePop(&que);
QueuePop(&que);
QueueEmpty(&que);
QueueSize(&que);
QueueFront(&que);
QueueBack(&que);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)