- 传送门：博客汇总帖
本文部分内容来自于公众号技术让梦想更伟大
队列
队列是一种数据结构（FIFO【 first in firet out 】）先入先出。
| 队列 | 栈 |
|---|---|
| FIFO（first in firet out） | FILO（first in last out ） |
| 先入先出 | 先入后出 |
队列（queue）是限定在表的一端进行插入（入队），表的另一端进行删除（出队）的数据结构。
如下图所示，假如你去买票排队，每一列队伍都有一个队尾和对头，先来的先买票，后来的后买，买好的就从对头出去，新来买票的就需要从队尾继续排队。
通常，称进数据的一端为 队尾，出数据的一端为 队头，数据元素进队列的过程称为 入队，出队列的过程称为 出队。
队列是一个线性的数据结构，并且这个数据结构只允许在一端进行插入，另一端进行删除，禁止直接访问除这两端以外的一切数据，且队列是一个先进先出的数据结构。
如上图，队列就像一个两端相通的水管，只允许一端插入，另一端取出，取出的球就不在水管里面了，而先放入管中的球就会先从管中拿出。
队列的存储有两种方式：
- 顺序队列：在顺序表的基础上实现的队列结构
- 链队列：在链表的基础上实现的队列结构
两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。
下面都是说链式队列
1 队列的结点设计与初始化
队列本身分为多种队列，如顺序队列和循环队列，还有衍生的优先队列等等，我们以顺序队列的设计为例。
首先是队列的结点设计，我们可以设计出两个结构体，一个结构体Node表示结点，其中包含有一个data域和next指针，如图所示：
其中data表示数据，其可以是简单的类型，也可以是复杂的结构体。
next指针表示，下一个的指针，其指向下一个结点，通过next指针将各个结点链接。
然后我们再添加一个结构体，其包括了两个分别永远指向队列的队尾和队头的指针
我们主要的操作只对这两个指针进行操作
//节点数据类型定义
typedef struct Node
{
int data;
struct Node *next;
/* data */
} node;
//队列定义，队首指针和队尾指针以及节点数量
typedef struct queue
{
node *headpoint;
node *tailpoint;
int queteSize;
/* data */
} queue;
//创建新节点
node *crete_node(int data)
{
node *new_node;
if ((new_node = (node *)malloc(sizeof(node))) == NULL)
{
printf("node malloc error\n");
return NULL;
/* code */
}
new_node->next = NULL;
new_node->data = data;
return new_node;
}
//初始化队列
queue *queue_init(void)
{
queue *point;
if ((point = (queue *)malloc(sizeof(queue))) == NULL)
{
printf("queue malloc error\n");
return NULL;
}
point->headpoint = point->tailpoint = NULL;
point->queteSize = 0;
return point;
}
2 判断队列是否为空
已经在队列结构体中定义了queueSize，所以直接判断这个就OK
//队列定义，队首指针和队尾指针以及节点数量
typedef struct queue
{
node *headpoint;
node *tailpoint;
int queueSize;
/* data */
} queue;
3 入队
void queue_push(queue * point,int value)
{
node *newnode = crete_node(value);
if (point->queueSize == 0)
point->headpoint = newnode;
else
point->tailpoint->next = newnode;
point->tailpoint = newnode;
point->queueSize += 1;
}
4 出队
void queue_pop(queue *point)
{
if (point->queueSize == 0)
{
printf("queue is NULL\n");
return ;
/* code */
}
node * newnode = point->headpoint->next;
free(point->headpoint);
point->headpoint = newnode;
point->queueSize -= 1;
}
5 得到头节点data
int GetHeandNodeData(queue * point)
{
if (point->queueSize == 0)
{
printf("queue is NULL\n");
return -1;
}
return point->headpoint->data;
}
6 遍历
void queue_show(queue * point)
{
while (!(point->queueSize == 0))
{
printf("%d \t",GetHeandNodeData(point));
queue_pop(point);
/* code */
}
}
7 源码
/*
* @Author: Mr.Dragon
* @Date: 2021-09-04 16:04:27
* @LastEditTime: 2021-09-04 22:29:10
* @LastEditors: Mr.Dragon
* @Description: Fall_down:所念皆星河
*/
#include "stdio.h"
#include "stdlib.h"
//节点数据类型定义
typedef struct Node
{
int data;
struct Node *next;
/* data */
} node;
//队列定义，队首指针和队尾指针以及节点数量
typedef struct queue
{
node *headpoint;
node *tailpoint;
int queueSize;
/* data */
} queue;
//创建新节点
node *crete_node(int data)
{
node *new_node;
if ((new_node = (node *)malloc(sizeof(node))) == NULL)
{
printf("node malloc error\n");
return NULL;
/* code */
}
new_node->next = NULL;
new_node->data = data;
return new_node;
}
//初始化队列
queue *queue_init(void)
{
queue *point;
if ((point = (queue *)malloc(sizeof(queue))) == NULL)
{
printf("queue malloc error\n");
return NULL;
}
point->headpoint = point->tailpoint = NULL;
point->queueSize = 0;
return point;
}
void queue_push(queue * point,int value)
{
node *newnode = crete_node(value);
if (point->queueSize == 0)
point->headpoint = newnode;
else
point->tailpoint->next = newnode;
point->tailpoint = newnode;
point->queueSize += 1;
}
int GetHeandNodeData(queue * point)
{
if (point->queueSize == 0)
{
printf("queue is NULL\n");
return -1;
}
return point->headpoint->data;
}
void queue_pop(queue *point)
{
if (point->queueSize == 0)
{
printf("queue is NULL\n");
return ;
/* code */
}
node * newnode = point->headpoint->next;
free(point->headpoint);
point->headpoint = newnode;
point->queueSize -= 1;
}
void queue_show(queue * point)
{
while (!(point->queueSize == 0))
{
printf("%d \t",GetHeandNodeData(point));
queue_pop(point);
/* code */
}
}
int main(void)
{
queue * point = queue_init();
queue_push(point,1);
queue_push(point,2);
queue_push(point,3);
queue_show(point);
return 0;
}