前言
大家好啊，我又双叒叕来水博客了，道路是曲折的，前途是光明的，事物是呈螺旋式上升的，事物最终的发展结果还是我们多多少少能够决定的，好啦，吹水结束，这与这篇博客的主题并没有太多联系。关于栈和队列这一板块本来是想不写（就是想偷懒），但是想了想，觉得这样不太好，关于数据结构这一块可能会有缺失，所以最终还是决定写，必须补齐这一块，恰好最近有时间写博客，所以还是写了，这篇博客将介绍队列的知识点，理解链表那一块的操作后，栈和队列的相关操作还是比较容易去理解的。
队列的表示和实现
队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First in First Out）
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
敲黑板，开始摸鱼：
其实也没什么重点啦，都是一些基本的概念性东西，主要有：
1.要理解FIFO代表的意思
2.什么是队尾队头，别弄混了
队列的实现有两种方法：
数组：不适合，队头出数据需要挪动数据，一般还会出现假溢出，循环队列啥的
链表：单链表较合适，头删尾插，效率较高
当然，并不是说一定要用哪种，由于课本是以数组为例，这里以单链表为例
代码实现
还是老样子，分为三部分，直接上手代码，来，跟着我一起敲
Queue.h
#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(Queue* pq);
//队尾入
void QueuePush(Queue* pq, QDataType x);
//队头出
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueuBack(Queue* pq);
//个数
int QueueSize(Queue* pq);
//判断是否为空
bool QueueEmpty(Queue* pq);
Queue.c
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
//队尾入
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
printf("malloc 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);
//1.一个（防止野指针）
//2.多个
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
QDataType QueuBack(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->tail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
int size = 0;
QNode* cur = pq->head;
while (cur)
{
++size;
cur = cur->next;
}
return size;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
Test.c
#include "Queue.h"
void TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
printf("%d ", QueueFront(&q));
QueuePop(&q);
QueuePush(&q, 3);
QueuePush(&q, 4);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestory(&q);
}
int main()
{
TestQueue();
return 0;
}
束语
关于堆栈和队列的相关操作就说到这里了，如果对你有帮助的话，那就点个赞把！
提供CDN加速