上一期我们认识了栈，这一期我们来看看队列是如何实现的
文章目录- 队列的概念以及结构
- 队列的实现
- 1、结构体的定义
- 2、函数接口声明
- 3、初始化
- 4、销毁空间
- 5、入队列
- 6、出队列
- 7、判断队列是否为空
- 8、取出队头数据
- 9、取出队尾数据
- 10、队列剩余数据个数
- 全部代码
- Queue.h
- Queue.c
- test.c
- 总结
队列的概念以及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
用图片展示：
我们先来看一张图片：
队列里面的每一个数据都是结构体类型的，其中front（head）结构体指针指向队头，rear（tail）结构体指针指向队尾。
这里用不用带哨兵位是头节点都可以，我这里没有用哨兵头节点，大家像用头节点可以自己加上
1、结构体的定义typedef int DataType;
typedef struct QueueNode//单链表的形式
{
DataType data;//数值
struct QueueNode* next;//指向下一个节点的指针
}QN;//重命名为QN
typedef struct Queue//定义一个结构体用来存放两个结构体指针，这样修改外面指针（也就是改变head和tail指向节点）的时候，不用传二级指针和接收改变指针的返回值
{
QN* head;//指向队列的对头
QN* tail;//指向队列的对尾
int size;//记录队列数据个数，用一个计数器可以提高计算效率
}Queue;
2、函数接口声明
队列与栈的区别在于：
1、栈是：后进先出；队列是：先进先出
2、栈只能取出栈顶数据，队列可以取出队头数据和队尾数据
void QueueInit(Queue* ps);//初始化 void QueueDestroy(Queue* ps);//释放空间 bool QueueEmpty(Queue* ps);//判断队列是否为空 void QueuePush(Queue* ps,DataType x);//入队列 void QueuePop(Queue* ps);//出队列 DataType QueueFront(Queue* ps);//队头数据 DataType QueueBack(Queue* ps);//队尾数据 int QueueSize(Queue* ps);//队列剩余数据个数3、初始化
void QueueInit(Queue* ps)//初始化
{
assert(ps);
ps->head = ps->tail = NULL;//两个指针都指向空
ps->size = 0;//此时队列没有数据
}
4、销毁空间
void QueueDestroy(Queue* ps)//释放空间
{
assert(ps);
QN* cur = ps->head;//cur等于头指针，ps是结构体指针，结构体指针指向头指针
while (cur)//如果头指针不为空，就进入循环释放空间
{
QN* del = cur;//保留头指针的节点
cur = cur->next;//头指针向后移动
free(del);//释放头指针移动前的节点
}
ps->head = ps->tail = NULL;//释放完之后，头尾指针指向NULL
ps->size = 0;//数据个数清0
}
5、入队列
与栈同理，只有入数据才就行扩容，所以扩容不用写一个函数
void QueuePush(Queue* ps, DataType x)//入队列
{
assert(ps);
QN* newnode = (QN*)malloc(sizeof(QN));//扩容一个新的节点出来
if (newnode == NULL)
{
perror("malloc failn");
exit(-1);
}
else
{
newnode->data = x;//对新节点就行初始化操作
newnode->next = NULL;//这里将新节点的next置空，不用考虑插入节点后的next指向了
}
if (ps->tail == NULL)//第一次入队列数据head和tail都是指向NULL的，直接让head和tail都指向第一个新节点
{
ps->head = ps->tail = newnode;
}
else
{
ps->tail->next = newnode;//将扩容节点插在tail后面
ps->tail = newnode;//让tail指向到插入的节点处
}
++ps->size;//插入size就加1，记录此时队列节点的个数
}
6、出队列
void QueuePop(Queue* ps)//出队列（队列出数据就相当于单链表的头删）
{
assert(ps);
assert(!QueueEmpty(ps));//如果队列没有节点了，断言生效
if(ps->head->next==NULL)//如果队列只剩下一个节点了，直接释放该节点，然后将头尾指针置空
{
free(ps->head);
ps->head = ps->tail = NULL;
}
else
{
QN* cur = ps->head;//保存当前头节点
ps->head = ps->head->next;//让头指针指向下一个节点
free(cur);//释放之前的头节点
cur = NULL;
}
--ps->size;//出一个数据size就减1
}
7、判断队列是否为空
bool QueueEmpty(Queue* ps)//判断队列是否为空
{
assert(ps);
return ps->head == NULL && ps->tail == NULL;//头尾指针都指向NULL，队列才为空
}
8、取出队头数据
这个很简单，下面的取出队尾数据也是
DataType QueueFront(Queue* ps)//队头数据
{
assert(ps);
assert(!QueueEmpty(ps));
return ps->head->data;
}
9、取出队尾数据
DataType QueueBack(Queue* ps)//队尾数据
{
assert(ps);
assert(!QueueEmpty(ps));
return ps->tail->data;
}
10、队列剩余数据个数
int QueueSize(Queue* ps)//队列剩余数据个数
{
assert(ps);
return ps->size;
}
全部代码
Queue.h
#pragma once #includeQueue.c#include #include #include typedef int DataType; typedef struct QueueNode//单链表的形式 { DataType data;//数值 struct QueueNode* next;//指向下一个节点的指针 }QN;//重命名为QN typedef struct Queue//定义一个结构体用来存放两个结构体指针 //这样修改外面指针（也就是改变head和tail指向节点）的时候，不用传二级指针和接收改变指针的返回值 { QN* head;//指向队列的对头 QN* tail;//指向队列的对尾 int size;//记录队列数据个数，用一个计数器可以提高计算效率 }Queue; void QueueInit(Queue* ps);//初始化 void QueueDestroy(Queue* ps);//释放空间 bool QueueEmpty(Queue* ps);//判断队列是否为空 void QueuePush(Queue* ps,DataType x);//入队列 void QueuePop(Queue* ps);//出队列 DataType QueueFront(Queue* ps);//队头数据 DataType QueueBack(Queue* ps);//队尾数据 int QueueSize(Queue* ps);//队列剩余数据个数
#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
void QueueInit(Queue* ps)//初始化
{
assert(ps);
ps->head = ps->tail = NULL;//两个指针都指向空
ps->size = 0;//此时队列没有数据
}
void QueueDestroy(Queue* ps)//释放空间
{
assert(ps);
QN* cur = ps->head;//cur等于头指针，ps是结构体指针，结构体指针指向头指针
while (cur)//如果头指针不为空，就进入循环释放空间
{
QN* del = cur;//保留头指针的节点
cur = cur->next;//头指针向后移动
free(del);//释放头指针移动前的节点
}
ps->head = ps->tail = NULL;//释放完之后，头尾指针指向NULL
ps->size = 0;//数据个数清0
}
void QueuePush(Queue* ps, DataType x)//入队列
{
assert(ps);
QN* newnode = (QN*)malloc(sizeof(QN));//扩容一个新的节点出来
if (newnode == NULL)
{
perror("malloc failn");
exit(-1);
}
else
{
newnode->data = x;//对新节点就行初始化操作
newnode->next = NULL;//这里将新节点的next置空，不用考虑插入节点后的next指向了
}
if (ps->tail == NULL)//第一次入队列数据head和tail都是指向NULL的，直接让head和tail都指向第一个新节点
{
ps->head = ps->tail = newnode;
}
else
{
ps->tail->next = newnode;//将扩容节点插在tail后面
ps->tail = newnode;//让tail指向到插入的节点处
}
++ps->size;//插入size就加1，记录此时队列节点的个数
}
void QueuePop(Queue* ps)//出队列（队列出数据就相当于单链表的头删）
{
assert(ps);
assert(!QueueEmpty(ps));//如果队列没有节点了，断言生效
if(ps->head->next==NULL)//如果队列只剩下一个节点了，直接释放该节点，然后将头尾指针置空
{
free(ps->head);
ps->head = ps->tail = NULL;
}
else
{
QN* cur = ps->head;//保存当前头节点
ps->head = ps->head->next;//让头指针指向下一个节点
free(cur);//释放之前的头节点
cur = NULL;
}
--ps->size;//出一个数据size就减1
}
bool QueueEmpty(Queue* ps)//判断队列是否为空
{
assert(ps);
return ps->head == NULL && ps->tail == NULL;//头尾指针都指向NULL，队列才为空
}
DataType QueueFront(Queue* ps)//队头数据
{
assert(ps);
assert(!QueueEmpty(ps));
return ps->head->data;
}
DataType QueueBack(Queue* ps)//队尾数据
{
assert(ps);
assert(!QueueEmpty(ps));
return ps->tail->data;
}
int QueueSize(Queue* ps)//队列剩余数据个数
{
assert(ps);
return ps->size;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
//void Test1()
//{
// Queue p;
// QueueInit(&p);//初始化
// QueuePush(&p, 1);//入队列
// QueuePush(&p, 2);
// QueuePush(&p, 3);
// QueuePush(&p, 4);
// while (!QueueEmpty(&p))
// {
// printf("%d ",QueueFront(&p));
// QueuePop(&p);//出队列
// }
// printf("n");
// printf("%d ", QueueSize(&p));
//
// QueueDestroy(&p);//释放空间
//}
void menu()
{
printf("-----------------------------------------------n");
printf("***********************************************n");
printf("***1、入队列数据 2、出队列数据***n");
printf("***3、查看队列数据个数 4、判断队列是否为空***n");
printf("***5、提取队头数据 6、提取队尾数据***n");
printf("*************7、出队列打印所有数据*************n");
printf("***********************************************n");
printf("-----------------------------------------------n");
}
int main()
{
//Test1();
Queue p;
QueueInit(&p);
int n = 0;
int x = 0;
do
{
menu();
printf("请选择操作:");
scanf("%d", &n);
switch (n)
{
case 1:
printf("请输入入队列数据，以-1截止:n");
do
{
scanf("%d", &x);
//QueuePush(&p, x);
if (x == -1)
break;
QueuePush(&p, x);
} while (x != -1);
break;
case 2:
QueuePop(&p);
break;
case 3:
printf("%dn", QueueSize(&p));
break;
case 4:
if (QueueEmpty(&p))
{
printf("队列为空n");
}
else
{
printf("队列不为空n");
}
break;
case 5:
printf("%dn",QueueFront(&p));
QueuePop(&p);
break;
case 6:
printf("%dn", QueueBack(&p));
QueuePop(&p);
break;
case 7:
while (!QueueEmpty(&p))
{
printf("%d ", QueueFront(&p));
QueuePop(&p);
}
printf("n");
break;
case 0:
QueueDestroy(&p);
printf("退出程序n");
break;
default:
printf("操作错误，请重新选择n");
break;
}
} while (n);
return 0;
}
总结
到这里栈和链表就结束了，如果有时间的话还会出一些栈和队列的oj题，如果没有时间的话下一期就直接进入二叉树了，又是一个难点。
那么就让我们下期见吧！
