队列是一种常见的数据结构，它具有先进先出（First-In-First-Out，FIFO）的特性，类似于排队等候的场景。以下是队列的要点：
1. 定义：队列是一种线性数据结构，由一系列元素组成，可以进行插入和删除操作。插入操作（称为入队）只能在队列的末尾进行，删除操作（称为出队）只能从队列的前端进行。
2. 特性：队列遵循先进先出的原则，最先入队的元素将最先出队。
3. 基本操作：
- 入队（Enqueue）：将元素插入到队列的末尾。
- 出队（Dequeue）：从队列的前端删除一个元素，并返回删除的元素。
- 队列是否为空（isEmpty）：判断队列是否为空，即没有任何元素。
- 队列长度（size）：返回队列中元素的个数。
4. 实现方式：
- 数组：使用数组实现队列时，需要维护两个指针，一个指向队列的前端，另一个指向队列的末尾。出队时移动前端指针，入队时移动末尾指针。注意需要循环利用数组空间。
- 链表：使用链表实现队列时，新元素可以直接添加到链表末尾，出队时删除链表的头节点。
5. 队列的应用：
- 广度优先搜索算法（BFS）：在图的遍历中，广度优先搜索需要使用队列来实现层次遍历。
- 计算机任务调度：操作系统中的任务调度可以使用队列来管理任务的执行顺序。
- 队列作为其他数据结构的辅助结构：例如，树的层次遍历、图的广度优先搜索等。
6. 常见类型：
- 普通队列（普通队列）：遵循FIFO原则，用于常规的数据排队。
- 优先队列（Priority Queue）：在出队时按照优先级进行排序，元素的出队顺序不一定按照插入顺序。
队列在计算机科学中具有广泛的应用，从操作系统到算法设计都有着重要作用。它是解决许多问题的重要工具之一。
顺序表队列文章来源：https://www.toymoban.com/news/detail-666442.html
/*===============================================
* 文件名称：queue.c
* 创 建 者：WM
* 创建日期：2023年08月21日
* 描 述：顺序队列//下标为rear里没有数据
================================================*/
#include <stdio.h>
#include<stdlib.h>
#define SIZE 8
typedef int data_t;
//构造节点类型
typedef struct node{
data_t data[SIZE];//保存数据的数据域
data_t front;
data_t rear;
} sequeue;
sequeue *createEmptySequeue()
{
sequeue *p = (sequeue *)malloc(sizeof(sequeue));
if(NULL == p)
{
perror("createEmptySequeue malloc failed");
return NULL;
}
//只要你申请空间就是为了让他装上数据
p->rear = 0;//使用的时候是数组的下标
p->front = 0;//使用的时候是数组的下标
return p;
}
int insert(sequeue* sq,data_t h)
{
sq->data[sq->rear]=h;
sq->rear=(sq->rear+1)%SIZE;//注意
}
int out_queue(sequeue *sq)
{
data_t val=sq->data[sq->front];
sq->front=(sq->front+1)%SIZE;
printf("%d \n",val);
return val;
}
int isQueue_empty(sequeue *sq)
{
if(sq==NULL) -1;
return sq->front==sq->rear;
}
//注意
int isQueue_full(sequeue *sq)
{
//return (sq->rear-sq->front+SIZE)%SIZE==SIZE-1;//这个算法很重要
return (sq->rear+1) % SIZE == sq->front;//或者这个。
}
//注意
int isQueue_full2(sequeue*sq)
{
if(sq->front>sq->rear)
return sq->front-sq->rear==1;
if(sq->front<sq->rear)
return sq->rear-sq->front==SIZE-1;
}
int queue_num(sequeue* sq)//谁大谁在前面。
{
return (sq->front<=sq->rear)?(sq->rear-sq->front):(sq->rear-sq->front+SIZE);
}
void clear_queue(sequeue *sq)
{
while (!isQueue_empty(sq))
out_queue(sq);
}
int main(int argc, char *argv[])
{
sequeue*phead=createEmptySequeue();
for (int i = 0; i < SIZE-1; i++)
{
insert(phead,i+1);
}
out_queue(phead);
printf("%d \n",queue_num(phead));
return 0;
}
链表队列文章来源地址https://www.toymoban.com/news/detail-666442.html
/*===============================================
* 文件名称：queue.c
* 创 建 者：WM
* 创建日期：2023年08月21日
* 描 述：链表队列
================================================*/
#include <stdio.h>
#include<stdlib.h>
typedef int data_t;
//构造链表节点类型
typedef struct node{
data_t data;//保存数据的数据域
struct node*next;//保存下一个节点的地址
} linklist ;
typedef struct {
linklist *front;
linklist* rear;
} lqueue;
lqueue* creat_lqueue()
{
lqueue*lq=(lqueue*)malloc(sizeof(lqueue));
lq->front=(linklist*)malloc(sizeof(linklist));
lq->front->next=NULL;
lq->rear=lq->front;
return lq;
}
int insert(lqueue* lq,data_t h)
{
linklist *new=(linklist *)malloc(sizeof(linklist));
if(NULL==new) return -1;
new->data=h;
new->next=NULL;
lq->rear->next=new;
lq->rear=new;
}
int out_queue(lqueue*lq)
{
linklist* m=lq->front->next;
lq->front->next=m->next;
int val=m->data;
free(m);
m=NULL;
printf("%d \n",val);
return val;
}
int isQueue_empty(lqueue*lq)
{
return lq->front==lq->rear;
}
int queue_num(lqueue*lq)
{
int len=0;
linklist* h = lq->front;
while (h->next!=NULL)
{
h=h->next;
len++;
}
return len;
}
void clear_queue(lqueue*lq)
{
while (!isQueue_empty(lq))
out_queue(lq);
}
int main(int argc, char *argv[])
{
lqueue*lqhead=creat_lqueue();
insert(lqhead,9);
insert(lqhead,110);
printf("%d \n",queue_num(lqhead));
out_queue(lqhead);
out_queue(lqhead);
printf("%d \n",queue_num(lqhead));
clear_queue(lqhead);
printf("%d \n",queue_num(lqhead));
return 0;
}
到了这里，关于数据结构，队列，顺序表队列，链表队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
