队列之顺序队列详解（C语言版）

---

前言

        大家好，越努力，越幸运。本篇文章小猿将跟您分享数据结构队列中的顺序队列，希望对您有所帮助。

一、顺序队列的定义

       首先我们来看看什么是队列？队列是一种先进先出（FIFO）的线性表，它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。队列的结构图如下所示：

       明白了队列之后，顺序队列就非常简单了，用顺序存储结构表示的队列就简称为顺序队列。和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。为了在C语言中描述方便起见，在此我们约定：初始化建空队列时，令front=rear=0，每当插人新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。了解了顺序队列之后，我们可以发现顺序队列有一个很大的缺点，它会出现虚假的满状态，为了解决这个问题我们可以将其改造成循环队列（循环队列将在下次进行介绍）。

二、顺序队列的结构

结构图

代码描述

//数据类型
#define ElemType int
//队列可容纳的最多元素个数
#define MAXSIZE 8
//队列的管理结构
typedef struct Queue
{
	ElemType *base; //指向队列的存储空间
	int       front; //指向队头
	int       rear;  //指向队尾
}Queue;
1
2
3
4
5
6
7
8
9
10
11

三、顺序队列的常用操作

初始化

//初始化顺序队列
void InitQueue(Queue *Q)
{
	//为顺序队列开辟存储空间
	Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
	assert(Q->base != NULL);
	//初始化时，队头和队尾都在0位置
	Q->front = Q->rear = 0;
}
1
2
3
4
5
6
7
8
9

入队

//入队操作
void EnQueue(Queue *Q, ElemType x)
{
	//判断队列是否还有存储空间
	if(Q->rear >= MAXSIZE)
		return;
	//如果还有存储空间，将数据入队
	Q->base[Q->rear++] = x;
}
1
2
3
4
5
6
7
8
9

出队

//出队
void DeQueue(Queue *Q)
{
	//判断队列中的元素是否为空
	if(Q->front == Q->rear)
		return;
	//如果队列中的元素不为空，进行出队操作
	Q->front++;
}
1
2
3
4
5
6
7
8
9

打印队列数据

//打印顺序队列中的元素
void ShowQueue(Queue *Q)
{
	//遍历队头到队尾中的每个元素，并将其打印输出
	for(int i=Q->front; i<Q->rear; ++i)
	{
		printf("%d ",Q->base[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10

获取队头元素

//获取队头元素
void GetHdad(Queue *Q, ElemType *v)
{
	//判断队列中的元素是否为空
	if(Q->front == Q->rear)
		return;
	//如果队列中的元素不为空，取出队头元素
	*v = Q->base[Q->front];
}
1
2
3
4
5
6
7
8
9

求队列长度

//获取队列元素个数
int Length(Queue *Q)
{
	//将尾指针位置减去头指针的位置就是队列中元素的个数
	return (Q->rear - Q->front);
}
1
2
3
4
5
6

清空队列

//清空队列
void ClearQueue(Queue *Q)
{
	//将队头指针和队尾指针都重置为0
	Q->front = Q->rear = 0;
}
1
2
3
4
5
6

销毁队列

//销毁队列
void DestroyQueue(Queue *Q)
{
	//释放队列的存储空间
	free(Q->base);
	//将队列空间的位置指针置空
	Q->base = NULL;
}
1
2
3
4
5
6
7
8

结语

        对顺序队列的介绍就到这里啦，希望这篇文章能给予你一些帮助，感谢各位人才的：点赞、收藏和评论，我们下次见。

附录

以下提供顺序队列的测试代码

SeqQueue.h

#ifndef __SEQQUEUE_H__
#define __SEQQUEUE_H__

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

//数据类型
#define ElemType int
//队列可容纳的最多元素个数
#define MAXSIZE 8
//队列的管理结构
typedef struct Queue
{
	ElemType *base; //指向队列的存储空间
	int       front; //指向队头
	int       rear;  //指向队尾
}Queue;

void InitQueue(Queue *Q);
void EnQueue(Queue *Q, ElemType x);
void ShowQueue(Queue *Q);
void DeQueue(Queue *Q);

void GetHdad(Queue *Q, ElemType *v);
int Length(Queue *Q);
void ClearQueue(Queue *Q);
void DestroyQueue(Queue *Q);


#endif //__SEQQUEUE_H__
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

SeqQueue.cpp

#include"SeqQueue.h"

//初始化顺序队列
void InitQueue(Queue *Q)
{
	//为顺序队列开辟存储空间
	Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
	assert(Q->base != NULL);
	//初始化时，队头和队尾都在0位置
	Q->front = Q->rear = 0;
}

//入队操作
void EnQueue(Queue *Q, ElemType x)
{
	//判断队列是否还有存储空间
	if(Q->rear >= MAXSIZE)
		return;
	//如果还有存储空间，将数据入队
	Q->base[Q->rear++] = x;
}

//打印顺序队列中的元素
void ShowQueue(Queue *Q)
{
	//遍历队头到队尾中的每个元素，并将其打印输出
	for(int i=Q->front; i<Q->rear; ++i)
	{
		printf("%d ",Q->base[i]);
	}
	printf("\n");
}

//出队
void DeQueue(Queue *Q)
{
	//判断队列中的元素是否为空
	if(Q->front == Q->rear)
		return;
	//如果队列中的元素不为空，进行出队操作
	Q->front++;
}

//获取队头元素
void GetHdad(Queue *Q, ElemType *v)
{
	//判断队列中的元素是否为空
	if(Q->front == Q->rear)
		return;
	//如果队列中的元素不为空，取出队头元素
	*v = Q->base[Q->front];
}

//获取队列元素个数
int Length(Queue *Q)
{
	//将尾指针位置减去头指针的位置就是队列中元素的个数
	return (Q->rear - Q->front);
}

//清空队列
void ClearQueue(Queue *Q)
{
	//将队头指针和队尾指针都重置为0
	Q->front = Q->rear = 0;
}

//销毁队列
void DestroyQueue(Queue *Q)
{
	//释放队列的存储空间
	free(Q->base);
	//将队列空间的位置指针置空
	Q->base = NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

Main.cpp

#include"SeqQueue.h"

void main()
{
	Queue Q;
	InitQueue(&Q);

	for(int i=1; i<=8; ++i)
	{
		EnQueue(&Q, i);
	}
	ShowQueue(&Q);
	DeQueue(&Q);
	EnQueue(&Q,10);
	ShowQueue(&Q);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17