数据结构：队列
文章目录
- 数据结构：队列
- 1.队列常用操作：
- 2.队列的实现
- 3.队列典型应用
***「队列 queue」是一种遵循先入先出规则的线性数据结构。***队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。只有当队头的的人逐个离开后，队尾的人才能到队头。
1.队列常用操作：
2.队列的实现
- 实现队列可以基于链表实现，也可以基于数组实现
优势在于链表来实现队列更加方便，因为链表更容易进行头删操作，效率更高，进行头删时链表时间复杂度为O(1)数组时间复杂度为O(N)
下面我将用链表（带头单向）实现队列：
Queue.h:
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//基于 带头单向链表 实现队列
typedef int QueueDateType;
typedef struct MyQueueNode
{
QueueDateType val;
struct MyQueueNode* next;
}Queue;
// 初始化队列
Queue* Init();
//打印队列
void Print(Queue* head);
//创建节点
Queue* Createnewnode(QueueDateType data);
// 队尾入队列
void Push(Queue** head, QueueDateType data);
// 队头出队列
void Pop(Queue** head);
// 获取队列头部元素
QueueDateType Peek(Queue** head);
// 获取队列队尾元素
QueueDateType Back(Queue** head);
// 获取队列中有效元素个数
int Size(Queue* head);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool Empty(Queue* head);
// 销毁队列
void Destroy(Queue** head);
Queue.c:
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
// 初始化队列
// 哨兵位初始化(创建链表的头结点)
Queue* Init()
{
Queue* head = Createnewnode(-1);
return head;
}
//打印队列
void Print(Queue* head)
{
assert(head);
Queue* tail = head->next;
if (tail == NULL)
{
printf("链表为空");
return;
}
while (tail)
{
printf("%d ", tail->val);
tail = tail->next;
}
}
//创建节点
Queue* Createnewnode(QueueDateType data)
{
Queue* newnode = (Queue*)malloc(sizeof(Queue));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->next = NULL;
newnode->val = data;
return newnode;
}
// 队尾入队列 (尾插)
void Push(Queue** head, QueueDateType data)
{
assert(head);
assert(*head);
// 创造一个新节点
Queue* newnode = Createnewnode(data);
//如果链表最初就为空（除去哨兵位）
if ((*head)->next == NULL)
{
(*head)->next = newnode;
}
//找尾
else
{
Queue* tail = (*head)->next;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
// 队头出队列 (头删)
void Pop(Queue** head)
{
assert(head);
assert((*head)->next != NULL);
Queue* first = (*head)->next;
(*head)->next = first->next;
free(first);
first = NULL;
}
// 获取队列头部元素
QueueDateType Peek(Queue** head)
{
assert(head);
assert((*head)->next != NULL);
return (*head)->next->val;
}
// 获取队列队尾元素
QueueDateType Back(Queue** head)
{
assert(head);
assert((*head)->next != NULL);
Queue* tail = (*head)->next;
while (tail->next != NULL)
{
tail = tail->next;
}
return tail->val;
}
// 获取队列中有效元素个数
int Size(Queue* head)
{
assert(head);
int sum = 0;
while (head->next != NULL)
{
sum++;
head = head->next;
}
return sum;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool Empty(Queue* head)
{
if (Size(head) == 0)
{
return true;
}
else
{
return false;
}
}
// 销毁队列
void Destroy(Queue** head)
{
assert(head);
assert(*head);
Queue* cur = (*head)->next;
while (cur)
{
Queue* next = cur->next;
free(cur);
cur = next;
}
free(*head);
*head = NULL;
}
test.c:
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//入队列测试
void test1()
{
//初始化队列
Queue* head = Init();
Push(&head, 1);
Push(&head, 2);
Push(&head, 3);
Push(&head, 4);
Push(&head, 5);
Print(head);
Destroy(&head);
}
//队头出队列测试
void test2()
{
//初始化队列
Queue* head = Init();
Push(&head, 1);
Push(&head, 2);
Push(&head, 3);
Push(&head, 4);
Push(&head, 5);
Pop(&head);
Print(head);
Destroy(&head);
}
//获取头部元素测试
void test3()
{
//初始化队列
Queue* head = Init();
Push(&head, 1);
Push(&head, 2);
Push(&head, 3);
Push(&head, 4);
Push(&head, 5);
printf("%d\n", Peek(&head));
Destroy(&head);
}
// 获取队列队尾元素
void test4()
{
//初始化队列
Queue* head = Init();
Push(&head, 1);
Push(&head, 2);
Push(&head, 3);
Push(&head, 4);
Push(&head, 5);
QueueDateType ret = Back(&head);
printf("%d\n", ret);
Destroy(&head);
}
//获取元素个数测试
void test5()
{
Queue* head = Init();
Push(&head, 1);
Push(&head, 2);
Push(&head, 3);
Push(&head, 4);
Push(&head, 5);
printf("%d\n", Size(head));
Destroy(&head);
}
//检测链表是否为空
void test6()
{
Queue* head = Init();
Push(&head, 1);
Push(&head, 2);
Push(&head, 3);
Push(&head, 4);
Push(&head, 5);
if (Empty(head) == true)
{
printf("链表为空\n");
}
else
{
printf("链表不为空\n");
}
Destroy(&head);
}
int main()
{
//入队列测试
//test1();
//队头出队列测试
//test2();
//获取头部元素测试
//test3();
// 获取队列队尾元素
//test4();
//获取元素个数测试
//test5();
//检测链表是否为空
test6();
return 0;
}
3.队列典型应用
-
淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
-
各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等，队列在这些场景中可以有效地维护处理顺序。
