欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

数据结构队列 —— 详细讲解（配有图解）

2026-06-04 分类：服务器技术 阅读(31) 评论(0)

目录

一、队列的概念

二、队列的实现

1.顺序结构方式实现：

1.1定义顺序结构队列

1.2初始化

1.3判断队列是否为空队列

1.4入队

1.4.1顺序结构入队方式

1.4.2循环队列入队方式

1.5出队

1.6获取对头元素

2.链表结构实现方式

2.1定义链式结构队列

2.2 初始化

2.3判断队列是否为空

2.4入队

2.4出队

2.5 获取对头元素

3.代码展示和图解的展示

3.1顺序表代码代码

3.2顺序表详解

3.3链表代码实现

3.4链表图解详解

一、队列的概念

1.队列(Queue)：是一种先进先出的线性表。他只允许在表的一端进行插入，在另一端进行删除元素。

2.队头：允许插入的一端。

3.对尾：允许删除的一端。

如图所示：

二、队列的实现

        分为顺序表和链表（这里基于单链表进行实现）两种结构的实现方式。

1.顺序结构方式实现：

1.1定义顺序结构队列

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
//定义队列
typedef int ElemType; //重新定义数据类型，以便后续修改。
typedef struct //队列的结构体
{
//队列的数据
ElemType *data;
//队头指针
int front;
//队尾指针
int rear;
}Queue;

1.2初始化

        这里利用动态内存分配的方式进行开辟空间，以便合理的利用空间。让对头指针和队尾指针都先指向队头的位置。

//初始化队列
Queue* InitQueue()
{
//动态内存分配方式进行开辟空间
Queue* Q = (Queue*)malloc(sizeof(Queue));
if (Q == NULL)
{
perror("InitQueue:Q");
return NULL;
}
Q->data = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
Q->front = 0;
Q->rear = 0;
return Q;
}

1.3判断队列是否为空队列

        当对头指针和对位指针相等的时候此时便为空队列。以下图解有所展示。

//判断队列是为空
int IsEmpty(Queue* Q)
{
if (Q->front == Q->rear)
{
printf("空队列\\n");
return 1;
}
else
{
return 0;
}
}

图解

1.4入队

        在入队操作这里有两种实现方式，第一种是采用顺序结构进行的入队操作，第二种是采用循环队列进行入队的操作。前者效率低，后者效率较高。

1.4.1顺序结构入队方式

//入队时没有完全满处理
int QueueFull(Queue* Q)
{
if (Q->front > 0)
{
int step = Q->front;
int i = 0;
for (i = Q->front; i < Q->rear; i++)
{
Q->data[i – step] = Q->data[i];
}
Q->front = 0;
Q->rear = Q->rear – step;
return 1;
}
else
{
printf("满了\\n");
return 0;
}
}

//第一种入队实现方法（效率低）
int Enqueue(Queue* Q, ElemType e)
{
if (Q->rear>= MAXSIZE)
{
if (!QueueFull(Q))
{
return 0;
}
}
Q->data[Q->rear] = e;
Q->rear++;
return 1;
}

图解

1.4.2循环队列入队方式

//第二种入队实现方法(效率高)
int Enqueue(Queue* Q, ElemType e)
{
if ((Q->rear+1) % MAXSIZE == Q->front)
{
printf("满了\\n");
return 0;
}
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAXSIZE;
return 1;
}

1.5出队

        这里出队的操作本应该是每出去一个元素就让队指针向前挪动一个位置，但是如果数据足够大这种方法的效率显然是不行的，所以就采用了循环链表的方法进行出队。

//出队
int Dequeue(Queue* Q, ElemType* e)
{
if (Q->front == Q->rear)
{
printf("空队\\n");
return 0;
}
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
//等价Q->front++，但上面的代码效率高
return 1;
}

图解

1.6获取对头元素

        想要获取到队头的元素，只需要让队头指针作为下标就行了。

//获取对头元素
int Get_Title(Queue* Q,ElemType*e)
{
if (Q->front == Q->rear)
{
printf("空队\\n");
return 0;
}
*e = Q->data[Q->front];
return 1;

}

2.链表结构实现方式

2.1定义链式结构队列

        这里是基于单链表进行实现的队列，所以是按照单链表方式进行的定义。

//定义链式结构队列
typedef int ElemType;
//定义链表
typedef struct QueueNode
{
ElemType data;
struct QueueNode* next;

}QueueNode;

//定义对头和队尾
typedef struct
{
QueueNode* front;
QueueNode* rear;

}Queue;

2.2 初始化

//初始化
Queue* InitQueue()
{
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
if (node == NULL)
{
perror("InitQueue:node");
return NULL;
}
Queue* q = (Queue*)malloc(sizeof(Queue));
if (q == NULL)
{
perror("InitQueue:Q");
return NULL;
}
node->data = 0;
node->next = NULL;
q->front = node;
q->rear = node;
return q;
}

2.3判断队列是否为空

//判断队列是否为空
int IsEmpty(Queue* q)
{
if (q->front == q->rear)
{
printf("空的\\n");
return 1;
}
else
{
return 0;
}
}

图解

2.4入队

//入队（相当于链表尾插法）
void Enqueue(Queue* q,ElemType e)
{
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
if (node == NULL)
{
perror("InsertTitle:node");
return;
}
node->data = e;
node->next = NULL;
q->rear->next = node;
q->rear = node;
}

图解

2.4出队

//出队(相当于链表删除)
int Dequeue(Queue* q, ElemType* e)
{
QueueNode* node = q->front->next;
if (node == NULL)
{
perror("Dequeue:p");
return 0;
}
*e = node->data;
q->front->next = node->next;
if (q->rear == node)
{
q->rear = q->front;
}
free(node);
node = NULL;
return 1;
}

2.5 获取对头元素

//获取对头元素
ElemType GetPop(Queue* q)
{
if (IsEmpty(q))
{
printf("空的\\n");
return 0;
}
return q->front->next->data;
}

3.代码展示和图解的展示

3.1顺序表代码代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
//定义队列
typedef int ElemType;
typedef struct
{
ElemType *data;
int front;
int rear;
}Queue;
//初始化
Queue* InitQueue()
{
Queue* Q = (Queue*)malloc(sizeof(Queue));
if (Q == NULL)
{
perror("InitQueue:Q");
return NULL;
}
Q->data = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
Q->front = 0;
Q->rear = 0;
return Q;
}
//判断队列是为空
int IsEmpty(Queue* Q)
{
if (Q->front == Q->rear)
{
printf("空队列\\n");
return 1;
}
else
{
return 0;
}
}
//入队时没有完全的满处理
int QueueFull(Queue* Q)
{
if (Q->front > 0)
{
int step = Q->front;
int i = 0;
for (i = Q->front; i < Q->rear; i++)
{
Q->data[i – step] = Q->data[i];
}
Q->front = 0;
Q->rear = Q->rear – step;
return 1;
}
else
{
printf("满了\\n");
return 0;
}
}

//第一种入队实现方法（效率低）
int Enqueue(Queue* Q, ElemType e)
{
if (Q->rear>= MAXSIZE)
{
if (!QueueFull(Q))
{
return 0;
}
}
Q->data[Q->rear] = e;
Q->rear++;
return 1;
}
//第二种入队实现方法(效率高)
int Enqueue(Queue* Q, ElemType e)
{
if ((Q->rear+1) % MAXSIZE == Q->front)
{
printf("满了\\n");
return 0;
}
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAXSIZE;
return 1;
}

//出队
int Dequeue(Queue* Q, ElemType* e)
{
if (Q->front == Q->rear)
{
printf("空队\\n");
return 0;
}
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
return 1;
}

//获取对头元素
int Get_Title(Queue* Q,ElemType*e)
{
if (Q->front == Q->rear)
{
printf("空队\\n");
return 0;
}
*e = Q->data[Q->front];
return 1;

}

//执行
int main()
{

//初始化
Queue* Q = InitQueue();
//入队
Enqueue(Q, 10);
Enqueue(Q, 20);
Enqueue(Q, 30);
Enqueue(Q, 40);
//出队
ElemType e;
Dequeue(Q, &e);
printf("%d\\n", e);
Dequeue(Q, &e);
printf("%d\\n", e);
//获取对头元素
Get_Title(Q, &e);
printf("%d\\n", e);
return 0;

}

3.2顺序表详解

3.3链表代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
//定义链式结构队列
typedef int ElemType;
//定义链表
typedef struct QueueNode
{
ElemType data;
struct QueueNode* next;

}QueueNode;

//定义对头和队尾
typedef struct
{
QueueNode* front;
QueueNode* rear;

}Queue;

//初始化
Queue* InitQueue()
{
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
if (node == NULL)
{
perror("InitQueue:node");
return NULL;
}
Queue* q = (Queue*)malloc(sizeof(Queue));
if (q == NULL)
{
perror("InitQueue:Q");
return NULL;
}
node->data = 0;
node->next = NULL;
q->front = node;
q->rear = node;
return q;
}

//判断队列是否为空
int IsEmpty(Queue* q)
{
if (q->front == q->rear)
{
printf("空的\\n");
return 1;
}
else
{
return 0;
}
}

//入队（尾插法）
void Enqueue(Queue* q,ElemType e)
{
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
if (node == NULL)
{
perror("InsertTitle:node");
return;
}
node->data = e;
node->next = NULL;
q->rear->next = node;
q->rear = node;
}

//出队(删除)
int Dequeue(Queue* q, ElemType* e)
{
QueueNode* node = q->front->next;
if (node == NULL)
{
perror("Dequeue:p");
return 0;
}
*e = node->data;
q->front->next = node->next;
if (q->rear == node)
{
q->rear = q->front;
}
free(node);
node = NULL;
return 1;
}

//获取对头元素
ElemType GetPop(Queue* q)
{
if (IsEmpty(q))
{
printf("空的\\n");
return 0;
}
return q->front->next->data;
}

//执行
int main()
{
//初始化
Queue* p = InitQueue();
//入队
Enqueue(p, 10);
Enqueue(p, 20);
Enqueue(p, 30);
Enqueue(p, 40);
//出队
ElemType e;
Dequeue(p, &e);
printf("%d\\n", e);
Dequeue(p, &e);
printf("%d\\n", e);
//获取队头元素
printf("%d\\n", GetPop(p));
return 0;
}

3.4链表图解详解

赞(0)
未经允许不得转载：171主机测评 » 数据结构队列 —— 详细讲解（配有图解）
分享到： 更多 (0)
标签：

相关推荐

评论 抢沙发

取消

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

热门标签

#人工智能(60952)#python(20538)#开发语言(17171)#java(15755)#运维(15617)#linux(15154)#大数据(14811)#服务器(13249)#算法(11916)#前端(11135)#网络(9563)#ai(9286)#数据库(9064)#c++(8303)#学习(6920)#课程设计(6891)#机器学习(6812)#区块链(5970)#OpenClaw(5401)#后端(5252)#spring boot(5077)#深度学习(5038)#c语言(4422)#毕业设计(4330)#数据结构(4234)#安全(4232)#docker(3979)#架构(3975)#javascript(3866)#大模型(3739)

热门文章

最新文章

归档

分类