【数据结构】详谈队列的顺序存储及C语言实现

循环队列及其基本操作的C语言实现

  • 前言
  • 一、队列的顺序存储
    • 1.1 队尾指针与队头指针
    • 1.2 基本操作实现的底层逻辑
      • 1.2.1 队列的创建与销毁
      • 1.2.2 队列的增加与删除
      • 1.2.3 队列的判空与判满
      • 1.2.4 逻辑的局限性
  • 二、循环队列
    • 2.1 循环队列的实现逻辑一
    • 2.2 循环队列的实现逻辑二
    • 2.3 循环队列的实现逻辑三
  • 三、如何实现队列的循环
  • 四、循环队列的C语言实现
    • 4.1 空间置换法的C语言实现
      • 4.1.1 数据类型的定义
      • 4.1.2 队列的初始化
      • 4.1.3 队列的判空
      • 4.1.4 队列的判满
      • 4.1.5 队列的入队
      • 4.1.6 队列的出队
      • 4.1.7 队列的查找
      • 4.1.8 队列的销毁
      • 4.1.9 空间置换法的演示
    • 4.2 标志法的C语言实现
      • 4.2.1 数据类型的定义
      • 4.2.2 队列的初始化
      • 4.2.3 队列的判空
      • 4.2.4 队列的判满
      • 4.2.5 队列的入队
      • 4.2.6 队列的出队
      • 4.2.7 队列的查找
      • 4.2.8 队列的销毁
      • 4.2.9 标志法的C语言实现
  • 结语

封面

前言

大家好，很高兴又和大家见面啦！！！
在上一篇内容中，我们在介绍完队列的基本概念、重要术语以及基本操作后，又回顾了一下数据结构的三要素——数据的逻辑结构、数据的存储结构以及数据的运算。
队列这种数据结构我们已经介绍了它的逻辑结构以及数据运算的定义，从这一篇开始，我们将详细介绍队列的数据的存储结构以及数据的运算的实现。
在今天的内容中，我们要介绍的是队列在内存中的顺序存储结构以及如何通过C语言来实现相关的基本操作。

一、队列的顺序存储

顺序存储想必大家都并不陌生了，顺序存储指的是逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系有存储单元的邻接关系来体现。简单的理解就是在内存中分配一块连续的存储单元来存放队列中的元素。

1.1 队尾指针与队头指针

由队列的操作特性可知，我们在对队列进行入队时需要有一个指向队尾的标志，在进行出队时需要有一个指向队头的标志，这样我们才能正常实现数据元素的入队和出队操作。

在栈中，我们将指向栈顶的标志称为栈顶指针，在队列中同理：

  • 指向队尾的标志称为队尾指针（rear）；
  • 指向队头的标志称为队头指针（front）；

这两个指针的主要做用就是告诉我们元素从哪里入队，从哪里出队。现在了解完了这两个指针，下面我们就来探讨一下如何在队列的顺序存储上来实现队列的基本操作；

1.2 基本操作实现的底层逻辑

为了更好的介绍这些基本操作，我们还是以创建、销毁、增删改查的顺序来进行介绍；

1.2.1 队列的创建与销毁

  1. 队列的创建

对于队列的创建实际上就是定义数据类型、定义队列变量以及初始化一个队列。那如果要定义一个数据类型，按照前面的介绍，队列的数据类型中至少有三个内容：

  1. 存放元素的一块连续的存储空间；
  2. 指向队尾的队尾指针rear；
  3. 指向队头的队头指针front；

对于这三个内容的实现起始并不复杂，我们可以通过静态数组来实现一块连续的存储空间；
既然是静态数组，那么我们要想找到数组中不同位置的元素那就需要数组下标，因此队头指针与队尾指针就需要是两个存放数组下标的整型变量，因此我们可以将其用C语言表述为：

//队列的顺序存储类型
#define MaxSize 10 //定义队列的最大长度
typedef int ElemType;//重命名队列中数据元素的数据类型，可以修改为其它数据类型
typedef struct SqQueue {
	ElemType data[MaxSize];//存放队列数据元素的静态数组
	int front, rear;	   //定义队列的队头指针与队尾指针
}SqQueue;				   //重命名后的队列数据类型

那这样是不是就没问题了呢？这里我们先放一放，后面再来讨论；

在定义好数据类型后，我们只需要通过类型来定义一个变量并即将该变量进行初始化，即可完成队列的创建。定义变量都很简单，关键是这个初识我们应该如何表示？

为了更好的理解这个问题，那我们来看一下图片：
队列的创建
按照两个指针的描述，我们在创建队列时应该是如图所示，但是现在就有一个问题，队尾是负责进行入队操作的，队首是负责进行删除操作的，我们应该如何来表示队列的插入与删除呢？

这里我们需要联想一下栈的插入与删除。在栈中如果栈为空栈时，栈顶指针指向的是栈底，入栈一个新元素，栈顶指针就需要往上移动一位来表示入栈；当我们的栈不为空栈时，栈顶指针每往下移动一位就是表示出栈。

也就是说在栈中，我们是借助指针的移动来表示栈顶的出栈与入栈，在队列中，我同样也可以仿照这种思路了，通过指针的移动来表示入队与出队。因此我们在创建一个队列时，可以将front和rear都指向队头，如下所示：
队列的创建2
当有新元素入队时，我们可以将队尾指针往上移动，当有元素出栈时，我们同样可以将队头指针往上移动，入下图所示：
队列的创建3
既然这样，那我们就可以在初始化时将队头指针与队尾指针都初始化为0，如下所示：

	Q->front = Q->rear = 0;//赋值语句的连续赋值形式
	//等价于下面两句代码
	//Q->rear = 0;
	//Q->front = Q->rear;

具体是不是如此，我们还是先继续往下看。

  1. 队列的销毁

如果我们想要销毁一个队列，无非就是将队列中的所有元素依次出队，那如果一个存满元素的队列要销毁的话，那我们就需要队头指针一直上移如下图所示：

队列的销毁
如图所示，当我们在完全销毁队列后，此时的队列的两个指针又重合了，并且都指向了队尾，转化成C语言，则可以表述为：

	if (Q->front == Q->rear && Q->rear == MaxSize - 1)
		printf("队列已销毁\n");

如果只是这样判断，还有没有什么问题呢？我们先继续往后看；

1.2.2 队列的增加与删除

队列的增加与删除，在创建与销毁的讨论中我们已经提到过了，当增加一个新的数据元素时，我们可以通过队尾指针的移动来表示，那现在的问题是，队尾指针是应该如何进行移动？下面就有几种情况：

  1. 先入队新的元素再移动，指针指向队尾元素的下一个位置；
  2. 先移动指针再入队新元素，指针指向队尾元素；

用C语言来表达则是：

	//先入队再移动
	Q->data[Q->rear++] = x;
	//先移动再入队
	Q->data[++Q->rear] = x;

PS：在介绍栈的入栈与出栈时已经介绍过这里的代码简写的意思，这里我就不再重复介绍了。

队列的入队逻辑具体选择哪一种我们先不着急，接着往下看；

当我们要删除一个数据元素时，我们可以通过队头指针的移动来表示，同样的，队头指针的移动和队尾指针一样，也有下面几种情况：

  1. 先出队元素再移动，指针指向的是队头元素；
  2. 先移动指针再出队，指针指向的是队头元素的前一个位置；

用C语言表示则是：

	//先出队再移动
	x = Q->data[Q->front++];
	//先移动再出队
	x = Q->data[++Q->front];

队列的出队逻辑具体选择哪一种我们也不着急，接着往下看；

1.2.3 队列的判空与判满

队列的判空与判满的实现取决于队列初始化的方式，当我们创建好一个队列时，此时的队列中是不存在任何元素的，因此刚创建好的队列是一个空队列，这相信大家应该都能理解。
那么我们在判空时，只要按照初始化的方式即可进行判空操作也就是：

	if (Q.front == Q.rear && Q.front == 0)
		printf("队列为空\n");

那判满的话我们则可以根据队头指针与队尾指针来同时判断，如下所示：

if (Q.front == 0 && Q.rear == MaxSize - 1)
		return true;

但是具体能不能像这样实现呢？下面我们就来仔细探讨一下；

1.2.4 逻辑的局限性

在前面对基本操作的实现中，我们有提到过以下几个问题：

  1. 数据类型只定义静态数组和两个指针行不行？
  2. 队列的初始化能不能将两个指针都初始化为0？
  3. 队列的销毁能不能通过两个指针都指向MaxSize-1来判断是否成功销毁？
  4. 队列的增加与删除的逻辑应该是什么？
  5. 队列的判满与判空能不能实现？

我们来看一下下面的图片：
队列操作的演示
从上图中我们可以看到按照前面的分析，在创建数据类型时只定义静态数组与两个指针并将指针初始化为0的情况下，我们要实现一个队列，那我们的入队操作与出队操作都应该选择先执行入队或者出队，后执行指针的移动，并且判满与销毁的判定应该是rear==MaxSize;
但是这样就会造成一个问题，如下图所示：
逻辑的局限性
在这种情况下，我们此时的队列并不是满队列，但是rear指针已经指向了MaxSize，如果我们要继续入队的话此时就会出现数组越界的情况。

也就是说我们前面的分析只适合与创建好队列后从初始化开始到销毁结束，中间的流程都不能发生任何变化，即入队就要全部元素入满，出队就要直接到销毁。

这样实现的队列就好比一次性碗筷，只能够使用一次，感受一下，并不能重复利用，那我们应该如何调整才能实现一个完整的队列呢？这里就需要引入一个新的概念——循环队列；

二、循环队列

2.1 循环队列的实现逻辑一

所谓的循环队列并不是指像循环链表那种头尾相连的结构，队列的存储结构依然是顺序存储，只不过指针存储的范围是0～MaxSize-1；通过指针的这种存储的循环方式将队列看做一个环，如下图所示：

循环队列
此时我们各个操作的执行逻辑如下所示：

  1. 数据类型的定义：此时我们只需要定义三个对象——存储数据元素的一维数组，指向队头元素的队头指针与指向队尾元素下一个位置的队尾指针；
  2. 初始化：在初始化时我们将队头指针与队尾指针都初始化为0，使他们同时指向数组首元素的位置；
  3. 判空：我们在进行判空时只需要判断front == rear 这个条件是否成立，成立则为空队列，否则为非空队列；
  4. 入队：入队时的逻辑是先入队后移动，即data[rear] = x;rear++;简写为data[rear++] = x；
  5. 判满：为了保证判空的逻辑正常，此时我们需要舍弃最后一个空间来作为判满的条件，也就是说当队尾指针的下一个位置为队头指针时表示队列已满，也就是rear++ == front;当条件成立时表示队列已满，否则表示队列未满；
  6. 出队：在进行出队操作时的逻辑则是先出队后移动，即x = data[front];front++;简写为x = data[front++]；
  7. 销毁：在进行销毁时我们需要重复进行出队操作，当队头指针与队尾指针再一次指向同一个位置时，表示队列中的元素已经全部出队，此时队列为空队列，之后我们在将对应的空间释放掉就行，因为是通过静态数组实现，所以当程序结束后，空间就会被操作系统自动回收；

这时可能就有朋友会说了，你像这个样子不就造成了空间的浪费吗？有没有什么办法可以将这一块空间也给利用起来呢？

2.2 循环队列的实现逻辑二

首先对于空间浪费的问题，我想说的是我们这里只浪费了一个数据类型所需的空间，相比于之前的一次性队列来说，我们在利用上面会节省更多的内存空间；
最后我们也可以通过对数据类型的调整来完成队列空间的饱和运用，如下所示：
循环队列2
我们通过设定一个记录当前队列长度的变量len，在这种情况下，我们的基本操作就需要做出如下调整：

  1. 数据类型的定义：增设一个记录当前队列长度的变量len；
  2. 初始化：在初始化时需要将当前队列长度初始化为0；
  3. 判空：在判空时，我们可以直接判断len == 0是否成立，成立，则为空队列，否则，为非空队列；
  4. 入队：每次完成一个新元素入队后，我们都需要执行一次len++；
  5. 判满：在判满时，我们可以直接判断len == MaxSize是否成立，成立队列已入满，否则队列还未满；
  6. 出队：每完成一个元素的出队后，我们都需要执行一次len--；
  7. 销毁：在完成所有的元素出队后，此时的队列长度又会变为0，所以我们只需要指向判空操作即可；

这时可能又有朋友会问，你这里是将队尾指针指向的是队尾元素的下一个位置，那如果我将其指向队尾元素又应该如何操作呢？

2.3 循环队列的实现逻辑三

其实这个实现方式也有很多种，这里我们还是以初始化为0的情况下来实现，如下所示：
循环队列3

我们通过增设一个入队标志tag来表示当前空间元素的入队情况，对应的基本操作就有如下调整：

  1. 数据类型的定义：增设一个标志变量tag，当tag = 0时表示此时的空间没有元素入队，当tag = 1时表示此时的空间有元素入队；
  2. 初始化：在初始化阶段，我们需要将队头指针初始化为0，入队标志初始化为0，队尾指针初始化为MaxSize - 1；
  3. 判空：在进行判空时，我们需要通过判断rear++ ==front && tag == 0是否成立，成立，则队列为空队列，否则，队列为非空队列；
  4. 入队：在进行入队操作时，此时的入队逻辑是先移动后入队，即rear++;data[rear] = x;简写为data[++rear] = x，并且我们还需要将入队标志tag修改为1，如下图所示：
    循环队列4
  5. 判满：在判断队列是否入满时，我们需要判断rear++ == front && tag == 1是否成立，成立则说明此时的队列已满，否则此时的队列未满；
  6. 出队：在进行出队操作时，我们需要将入队标志tag修改为0，如下图所示：
    循环队列5
  7. 销毁：在完成所有元素出队后，队列又会变为空队列，因此，我们只需要进行判空即可；

循环队列的实现逻辑主要是有以上三种方式，当然肯定还有其他的方式，但是操作上基本上都是大同小异，现在我们还有一个最重要的问题还有有提到——如何实现队列的循环？

三、如何实现队列的循环

在前面的逻辑中，我们来判断空队列和满队列时有提过通过判断队尾指针的下一个空间是否为队头指针，我们前面也是通过rear++ == front来说明这种判断的过程，但是在实际实现中，这是有问题的，因为我们是通过静态数组实现的队列，它在内存中还是以顺序存储的形式进行存放的，如下所示：
指针的循环
我们是将这种连续存放的空间臆想为一个环状结构，但并不代表它就是一个环状结构，因此，我们只能够通过指针来完成队列的循环。

那如何实现呢？我们现在先来思考一下这两个指针存放的是什么内容？

没错，就是数组下标，在前面我们也有提到过它们的取值范围是0～MaxSize - 1，只要我能够保证不管如何进行入队和出队操作，它们的取值都是在这个范围内，那就能实现队列的循环操作。

在C语言中我们有介绍过一个只能够在整型中使用的算术操作符——%（取模），这个操作符的作用就是获取两个整数相除后的余数，就比如在整型运算中我们知道 5 / 2 = 2 … … 1 5/2=2……1 5/2=2……1，在C语言中我们通过 / / /来获取两个整数的商，通过 % \% %来获取两个整数的余数，如下所示：
指针的循环2
在除法 a / b = c … … d a / b = c …… d a/b=c……d中，d的取值肯定是在[0 , b - 1]之间的，也就是说如果通过对下标进行与MaxSize取模的话，那是不是就能保证指针存储的值一定是在[0 , MaxSize - 1]之间了呢？

下面我们可以通过代码来测试一下，如下所示：
指针的循环3
可以看到，确实如此，通过取模运算后得到的值正好是在[0 , 8]之间。因此循环队列的实现就需要借助取模运算符来完成。下面我们就来看一下循环队列的C语言实现；

四、循环队列的C语言实现

前面我们介绍了3中实现方式，对于记录队列长度的实现相比之下会简单一点，这里我就不多做介绍了，我们主要是介绍另外两种方式，这里我们将这两种方式分别叫做空间置换法与标志法。
这里的空间置换指的是舍弃小块空间来获取整个队列的空间复用；
标志法指的是通过设立入队标志来完成循环队列；

4.1 空间置换法的C语言实现

4.1.1 数据类型的定义

空间置换法在定义类型时，总共定义了三个对象——静态数组、队头指针与队尾指针，它的实现就比较简单，如下所示：

//队列的顺序存储类型——空间置换法
#define MaxSize 10 //定义队列的最大长度
typedef int ElemType;//重命名队列中数据元素的数据类型，可以修改为其它数据类型
typedef struct SqQueue {
	ElemType data[MaxSize];//存放队列数据元素的静态数组
	int front, rear;	   //定义队列的队头指针与队尾指针
}SqQueue;				   //重命名后的队列数据类型

在定义好数据类型后，我们就可以通过数据类型来定义一个队列Q，如下所示：

void test_Queue1() {
	SqQueue Q;//定义队列Q
}

4.1.2 队列的初始化

在初始化阶段，我们只需要将两个指针初始化为0就行，如下所示：

//队列的初始化
bool InitQueue(SqQueue* Q) {
	if (!Q)
		return false;//当指针Q为空指针时，返回false
	Q->front = Q->rear = 0;//赋值语句的连续赋值形式
	return true;
}

一定要注意，当我们需要对实参进行修改时，是需要通过传址的方式进行传参，而形参则需要通过指针来接收。我们如果需要调用对应的函数时，一定要对形参进行判空，如果此时的形参为空指针，那说明我们的传参出现了问题，这里千万要记得；

4.1.3 队列的判空

对于空间置换法的判空，我们是根据两个指针是否相等来判断的，所以此时直接判断就是，如下所示：

//队列的判空
bool EmptyQueue(SqQueue Q) {
	if (Q.rear == (Q.front))
		return true;
	return false;
}

4.1.4 队列的判满

在进行判满时，因为此时的两个指针在逻辑上应该是处于相邻的位置，也就是队尾指针的下一个空间就是队头指针指向的空间，因此这里我们就需要通过 % \% %操作符来完成逻辑上的相邻，如下所示：

//队列的判满
bool FullQueue(SqQueue Q) {
	if ((Q.rear + 1) % MaxSize == Q.front)
		return true;
	return false;
}

4.1.5 队列的入队

在进行入队操作时，因为我们要确保队尾指针的取值是循环的，因此我们在移动队尾指针时就需要借助取模操作符，如下所示：

//队列的入队
bool EnQueue(SqQueue* Q, ElemType x) {
	if (!Q)
		return false;
	if (FullQueue(*Q))//判满
		return false;
	Q->data[Q->rear] = x;//先入队
	Q->rear = ++(Q->rear) % MaxSize;//再移动
	return true;
}

我们可以执行入队操作的前提条件是此时的队列还未满，因此，在入队前我们需要调用一下判满函数，来确保此时的队列还未满。

在调用函数的时候一定要注意，此时在入队函数中的参数Q是一个指针，但是判满函数的参数Q是一个变量，这里我们需要先对指针Q进行解引用，再传参

4.1.6 队列的出队

在进行出队操作时，我们同样也是需要借助 % \% %操作符来确保队头指针的取值是循环的，如下所示：

//队列的出队
bool DeQueue(SqQueue* Q, ElemType* x) {
	if (!Q)
		return false;
	if (EmptyQueue(*Q))//判空
		return false;
	*x = Q->data[Q->front];//先出队
	Q->front = ++(Q->front) % MaxSize;//再移动
	return true;
}

执行出队的前提条件是此时的队列为非空队列，因此，在出队前我们需要调用一下判空函数，来确保此时的队列为非空队列；

4.1.7 队列的查找

在队列中，我们的查找也是受到限制的，我们不能越过队头或者队尾来访问其他元素，因此，这里我们在实现查找时，只能够查找队头或者队尾元素，如下所示：

//队列的查找
bool GetHead(SqQueue Q,ElemType* x) {
	if (EmptyQueue(Q))//判空
		return false;
	*x = Q.data[Q.front];//查找队头元素
	return true;
}

我们在进行队列元素访问时，只能从出队的一端来访问元素，因此，队列的查找只支持访问队头元素。

4.1.8 队列的销毁

队列的销毁就是通过重复进行出队操作使队列变成空队列，最后再将队列的空间回收即可完成销毁，因此我们指向销毁时需要判断队列是否为空，如下所示：

//队列的销毁
bool DestroyQueue(SqQueue* Q) {
	if (!Q)
		return false;
	while (EmptyQueue(*Q)) {
		int x = 0;
		if (DeQueue(Q, &x))
			printf("元素%d已成功出队\n", x);
		else
			printf("出队失败\n");
	}
	return true;
}

4.1.9 空间置换法的演示

在完成了这些基本操作后，下面我们就来演示一下空间置换法，代码如下所示：

//队列的顺序存储类型——空间置换法
#define MaxSize 10 //定义队列的最大长度
typedef int ElemType;//重命名队列中数据元素的数据类型，可以修改为其它数据类型
typedef struct SqQueue {
	ElemType data[MaxSize];//存放队列数据元素的静态数组
	int front, rear;	   //定义队列的队头指针与队尾指针
}SqQueue;				   //重命名后的队列数据类型
//队列的初始化
bool InitQueue(SqQueue* Q) {
	if (!Q)
		return false;//当指针Q为空指针时，返回false
	Q->front = Q->rear = 0;//赋值语句的连续赋值形式
	return true;
}
//队列的判空
bool EmptyQueue(SqQueue Q) {
	if (Q.rear == (Q.front))
		return true;
	return false;
}
//队列的判满
bool FullQueue(SqQueue Q) {
	if ((Q.rear + 1) % MaxSize == Q.front)
		return true;
	return false;
}
//队列的入队
bool EnQueue(SqQueue* Q, ElemType x) {
	if (!Q)
		return false;
	if (FullQueue(*Q))//判满
		return false;
	Q->data[Q->rear] = x;//先入队
	Q->rear = ++(Q->rear) % MaxSize;//再移动
	return true;
}
//队列的出队
bool DeQueue(SqQueue* Q, ElemType* x) {
	if (!Q)
		return false;
	if (EmptyQueue(*Q))//判空
		return false;
	*x = Q->data[Q->front];//先出队
	Q->front = ++(Q->front) % MaxSize;//再移动
	return true;
}
//队列的查找
bool GetHead(SqQueue Q,ElemType* x) {
	if (EmptyQueue(Q))//判空
		return false;
	*x = Q.data[Q.front];//查找队头元素
	return true;
}

//队列的销毁
bool DestroyQueue(SqQueue* Q) {
	if (!Q)
		return false;
	while (EmptyQueue(*Q)) {
		int x = 0;
		if (DeQueue(Q, &x))
			printf("元素%d已成功出队\n", x);
		else
			printf("出队失败\n");
	}
	return true;
}
void test_Queue1() {
	SqQueue Q;//定义队列Q
	if (InitQueue(&Q))//队列初始化
		printf("初始化成功\n");
	else {
		printf("初始化失败\n");
		return;
	}
	int x = 0;
	if (GetHead(Q,&x))//查找队头元素
		printf("此时的队列为非空队列，队头元素为%d\n", x);
	else {
		printf("此时的队列为空队列\n");
	}
	//元素入队
	while (scanf("%d", &x) == 1) {
		if (EnQueue(&Q, x)) {
			printf("元素%d入队成功\n", x);
		}
		else {
			printf("元素%d入队失败\n", x);
			if (FullQueue(Q))//插入失败后进行判满
				printf("此时的队列已满\n");
			else {
				printf("此时的队列未满\n");
			}
		}
	}
	//元素出队
	if (DeQueue(&Q, &x)) {
		printf("元素%d出队成功\n", x);
		if (GetHead(Q, &x))//查找队头元素
			printf("此时的队列为非空队列，队头元素为%d\n", x);
		else {
			printf("此时的队列为非空队列\n");
		}
	}
	else {
		printf("出队失败\n");
		if (EmptyQueue(Q))//队列判空
			printf("此时的队列为空队列\n");
		else
			printf("此时的队列为非空队列\n");
	}
	//队列销毁
	if (DestroyQueue(&Q)) {
		printf("队列成功销毁\n");
	}
	else {
		printf("队列销毁失败\n");
	}
}

接下来我们在主函数中调用一下test_Queue1函数来测试一下空间置换法：
空间置换法的演示
可以看到，此时所有的功能都能够正常运行，也就是说我们完成了通过空间置换法完成了一个循环队列；

4.2 标志法的C语言实现

4.2.1 数据类型的定义

在标志法中，我们增设了一个出入队的标志，对应的数据类型如下所示：

//队列的顺序存储类型——标志法
#define MaxSize 10 //定义队列的最大长度
typedef int ElemType;//重命名队列中数据元素的数据类型，可以修改为其它数据类型
typedef struct SqQueue {
	ElemType data[MaxSize];//存放队列数据元素的静态数组
	int front, rear;	   //定义队列的队头指针与队尾指针
	int tag;			   //出入队标志
}SqQueue;				   //重命名后的队列数据类型

4.2.2 队列的初始化

出入队的标志取值，我们将其设定为出队为0，入队为1，

//队列的初始化
bool InitQueue(SqQueue* Q) {
	if (!Q)
		return false;//当指针Q为空指针时，返回false
	Q->front = 0;//队头指针指向的是队头元素所在空间
	Q->rear = MaxSize - 1;//队尾指针指向的是队尾元素所在空间
	Q->tag = 0;//此时队列为空队列，相当于执行了出队操作
	return true;
}

4.2.3 队列的判空

当队列为空队列时，此时队头指针与队尾指针在逻辑上是相邻的，我们可以通过队尾指针向上移动找到队头指针，并且此时的入队标志为0，表示的是通过出队操作的到的对应关系，代码如下所示：

//队列的判空
bool EmptyQueue(SqQueue Q) {
	if (((Q.rear + 1) % MaxSize) == Q.front && Q.tag == 0)
		return true;
	return false;
}

同样的，为了保证指针的可循环性，我们这里在判断时是借助了 % \% %操作符实现的相邻判断；

4.2.4 队列的判满

在标志法的实现下，判空与判满两个指针的位置关系是一致的，唯一不同的就是入队标志，当标志为1时说明此时是通过入队得到的对应的位置关系，那就说明此时是队列已满的情况，代码如下所示：

//队列的判满
bool FullQueue(SqQueue Q) {
	if (((Q.rear + 1) % MaxSize) == Q.front && Q.tag == 1)
		return true;
	return false;
}

4.2.5 队列的入队

当队尾指针指向的是队尾元素时，我们在进行入队操作是需要先将队尾指针往后移动一位后，再进行入队操作，由于设立了入队标志，所以当我们执行入队操作时，需要将入队标志改为1，对应的代码如下所示：

//队列的入队
bool EnQueue(SqQueue* Q, ElemType x) {
	if (!Q)
		return false;
	if (FullQueue(*Q))//判满
		return false;
	Q->rear = ++(Q->rear) % MaxSize;//先移动
	Q->data[Q->rear] = x;//再入队
	Q->tag = 1;//执行入队操作，入队标志改为1
	return true;
}

4.2.6 队列的出队

队列的出队操作唯一需要改动的就是将入队标志修改为0，代码如下所示：

//队列的出队
bool DeQueue(SqQueue* Q, ElemType* x) {
	if (!Q)
		return false;
	if (EmptyQueue(*Q))//判空
		return false;
	*x = Q->data[Q->front];//先出队
	Q->front = ++(Q->front) % MaxSize;//再移动
	Q->tag = 0;//指向出队操作，入队标志改为0
	return true;
}

4.2.7 队列的查找

对于两种方法的查找而言，都是一致的，因为我此时只需要找到队头或者队尾元素即可；

//队列的查找
bool GetHead(SqQueue Q, ElemType* x) {
	if (EmptyQueue(Q))//判空
		return false;
	*x = Q.data[Q.front];//查找队头元素
	return true;
}

4.2.8 队列的销毁

标志法的销毁操作，同样是通过重复调用出队操作，因此，这里也是不需要有任何修改，代码如下所示：

//队列的销毁
bool DestroyQueue(SqQueue* Q) {
	if (!Q)
		return false;
	while (EmptyQueue(*Q)) {
		int x = 0;
		if (DeQueue(Q, &x))
			printf("元素%d已成功出队\n", x);
		else
			printf("出队失败\n");
	}
	return true;
}

4.2.9 标志法的C语言实现

下面我们就来看一下整体的代码：

//队列的顺序存储类型——标志法
#define MaxSize 10 //定义队列的最大长度
typedef int ElemType;//重命名队列中数据元素的数据类型，可以修改为其它数据类型
typedef struct SqQueue {
	ElemType data[MaxSize];//存放队列数据元素的静态数组
	int front, rear;	   //定义队列的队头指针与队尾指针
	int tag;			   //出入队标志
}SqQueue;				   //重命名后的队列数据类型
//队列的初始化
bool InitQueue(SqQueue* Q) {
	if (!Q)
		return false;//当指针Q为空指针时，返回false
	Q->front = 0;//队头指针指向的是队头元素所在空间
	Q->rear = MaxSize - 1;//队尾指针指向的是队尾元素所在空间
	Q->tag = 0;//此时队列为空队列，相当于执行了出队操作
	return true;
}
//队列的判空
bool EmptyQueue(SqQueue Q) {
	if (((Q.rear + 1) % MaxSize) == Q.front && Q.tag == 0)
		return true;
	return false;
}
//队列的判满
bool FullQueue(SqQueue Q) {
	if (((Q.rear + 1) % MaxSize) == Q.front && Q.tag == 1)
		return true;
	return false;
}
//队列的入队
bool EnQueue(SqQueue* Q, ElemType x) {
	if (!Q)
		return false;
	if (FullQueue(*Q))//判满
		return false;
	Q->rear = ++(Q->rear) % MaxSize;//先移动
	Q->data[Q->rear] = x;//再入队
	Q->tag = 1;//执行入队操作，入队标志改为1
	return true;
}
//队列的出队
bool DeQueue(SqQueue* Q, ElemType* x) {
	if (!Q)
		return false;
	if (EmptyQueue(*Q))//判空
		return false;
	*x = Q->data[Q->front];//先出队
	Q->front = ++(Q->front) % MaxSize;//再移动
	Q->tag = 0;//指向出队操作，入队标志改为0
	return true;
}
//队列的查找
bool GetHead(SqQueue Q, ElemType* x) {
	if (EmptyQueue(Q))//判空
		return false;
	*x = Q.data[Q.front];//查找队头元素
	return true;
}

//队列的销毁
bool DestroyQueue(SqQueue* Q) {
	if (!Q)
		return false;
	while (EmptyQueue(*Q)) {
		int x = 0;
		if (DeQueue(Q, &x))
			printf("元素%d已成功出队\n", x);
		else
			printf("出队失败\n");
	}
	return true;
}
void test_Queue2() {
	SqQueue Q;//定义队列Q
	if (InitQueue(&Q))//队列初始化
		printf("初始化成功\n");
	else {
		printf("初始化失败\n");
		return;
	}
	int x = 0;
	if (GetHead(Q, &x))//查找队头元素
		printf("此时的队列为非空队列，队头元素为%d\n", x);
	else {
		printf("此时的队列为空队列\n");
	}
	//元素入队
	while (scanf("%d", &x) == 1) {
		if (EnQueue(&Q, x)) {
			printf("元素%d入队成功\n", x);
		}
		else {
			printf("元素%d入队失败\n", x);
			if (FullQueue(Q))//插入失败后进行判满
				printf("此时的队列已满\n");
			else {
				printf("此时的队列未满\n");
			}
		}
	}
	//元素出队
	if (DeQueue(&Q, &x)) {
		printf("元素%d出队成功\n", x);
		if (GetHead(Q, &x))//查找队头元素
			printf("此时的队列为非空队列，队头元素为%d\n", x);
		else {
			printf("此时的队列为非空队列\n");
		}
	}
	else {
		printf("出队失败\n");
		if (EmptyQueue(Q))//队列判空
			printf("此时的队列为空队列\n");
		else
			printf("此时的队列为非空队列\n");
	}
	//队列销毁
	if (DestroyQueue(&Q)) {
		printf("队列成功销毁\n");
	}
	else {
		printf("队列销毁失败\n");
	}
}

下面我们就来在主函数中调用并测试一下看看结果：
标志法的演示
可以看到此时的标志法实现时能够比空间置换法要多存储一个元素，我们现在也成功使用C语言通过标志法实现了循环队列。

结语

在今天的篇章中，我们详细介绍了队列的顺序存储结构——循环队列，并详细分析了三种实现循环队列的方式，最后通过C语言实现了两种循环队列——空间置换法与标志法，希望今天的内容能够帮助大家在了解队列的顺序存储结构的同时，还能帮助大家熟悉对应的基本操作并能够实现对应的操作。

今天的内容到这里就全部结束了，在下一个篇章中，我们将开始介绍队列的链式存储结构，通过链式存储的队列的基本操作又应该如何实现呢？就让我们期待一下下一篇的内容介绍吧！最后感谢大家的翻阅，咱们下一篇再见！！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/336215.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Git 配置与理解

Git 配置与理解

简述 Git 在 Windows 和 Ubuntu 中的配置，以及对 Git 工作区域划分和 Git 中对于文件状态划分的理解。 git 基础安装与配置 基于 WSL 的 Ubuntu 下的 git 打开或关闭Windows功能 -> Hyper-V、Virtual Machine Platform、Windows Subsystem for Linux # 1.必须…
阅读更多...
傲空间私有部署Windows指南

傲空间私有部署Windows指南

推荐阅读 智能化校园：深入探讨云端管理系统设计与实现（一） 智能化校园：深入探讨云端管理系统设计与实现（二） 安装 docker 请下载对应的 Docker，安装完成后启动。 Docker Desktop for Windows…
阅读更多...
【Linux取经路】初探进程地址空间

【Linux取经路】初探进程地址空间

文章目录 一、历史问题回顾二、语言层面的地址空间2.1 验证 三、虚拟地址的引入3.1 初步解释这种现象——引入地址空间的概念3.2 再来粗粒度理解上面的现象 四、细节解释4.1 地址空间究竟是什么？4.2为什么要有地址空间4.3 页表4.3.1 CR3寄存器4.3.2 页表是由页表项组…
阅读更多...
智慧校园大数据应用系统介（3）

智慧校园大数据应用系统介（3）

智能巡课系统 巡课系统是一种新的课堂观察记录工具，它将学校或区域内全体教师作为一个整体，采用数字化手段描述教师和学生的课堂行为。通过移动端实时记录和通用性的统计分析，使教育者更容易发现教学过程与教学成果之间的联系，有助于改变课堂生态、提高教学有效性、提升教…
阅读更多...
Codeforces Round 895 (Div. 3)补题

Codeforces Round 895 (Div. 3)补题

Two Vessels（Problem - A - Codeforces） 题目大意：有两个无限容器，目前一个容器中有a克水，另一个容器中有b克水，现有一个大小为cg的容器，我们每次可以从一个无限容器中取任意不大于c克的水&…
阅读更多...
【Linux】相关背景及环境搭建

【Linux】相关背景及环境搭建

前言： 认识 Linux, 了解 Linux 的相关背景，学会如何使用云服务器，掌握使用远程终端工具 xshell 登陆 Linux 服务器 文章目录 一、Linux介绍1.1 关于UNIX1.2 Linux的诞生及发展历程1.3 Linux开源1.4 Linux在各个行业的现状1.5 发行版本 二、Li…
阅读更多...
令牌桶算法与Guava的实现RateLimiter源码分析

令牌桶算法与Guava的实现RateLimiter源码分析

令牌桶算法与Guava的实现RateLimiter源码分析 令牌桶RateLimiter简介RateLimiter使用示例导入maven依赖编写测试代码 RateLimiter的实现源码解析SmoothRateLimiterSmoothBursty恒速获取令牌acquire(int)tryAcquire(int,long,TimeUnit) 存量桶系数小结 优缺点与漏桶的区别总结 令…
阅读更多...
Python爬虫时被封IP，该怎么解决？四大动态IP平台测评

Python爬虫时被封IP，该怎么解决？四大动态IP平台测评

在使用 Python 进行爬虫时，很有可能因为一些异常行为被封 IP，这主要是因为一些爬虫时产生的异常行为导致的。 在曾经的一次数据爬取的时候，我尝试去爬取Google地图上面的商家联系方式和地址信息做营销，可是很不幸，还只…
阅读更多...
CloudPanel file-manager/backend/makefile接口存在远程命令执行漏洞CVE-2023-35885

CloudPanel file-manager/backend/makefile接口存在远程命令执行漏洞CVE-2023-35885

@[toc] 免责声明：请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失，均由使用者本人负责，所产生的一切不良后果与文章作者无关。该文章仅供学习用途使用。 1. CloudPanel 简介 微信公众号搜索：南风漏…
阅读更多...
【漏洞复现】Hikvision摄像头产品越权漏洞(CVE-2017-7921)

【漏洞复现】Hikvision摄像头产品越权漏洞(CVE-2017-7921)

Nx01 产品简介 Hikvision（海康威视）是一家在中国颇具影响力的安防公司，其网络摄像头产品在市场上占据了相当大的份额。Hikvision的网络摄像头产品线非常丰富，涵盖了各种型号和功能，以满足不同用户的需求。 Nx02 漏洞描…
阅读更多...
Spring DI

Spring DI

目录 什么是依赖注入 属性注入 构造函数注入 Setter 注入 依赖注入的优势 什么是依赖注入 依赖注入是一种设计模式，它通过外部实体（通常是容器）来注入一个对象的依赖关系，而不是在对象内部创建这些依赖关系。这种方式使得对象…
阅读更多...
03-黑马程序员大数据开发：Apache Hive

03-黑马程序员大数据开发：Apache Hive

一、 Apache Hive概述 1. 目的：了解什么是分布式SQL计算；了解什么是Apache Hive 2. 使用Hive处理数据的好处 操作接口采用类SQL语法，提供快速开发的能力（简单、容易上手)底层执行MapReduc…
阅读更多...
第七回 林教头刺配沧州道 鲁智深大闹野猪林-FreeBSD/Linux图形界面安装配置

第七回 林教头刺配沧州道 鲁智深大闹野猪林-FreeBSD/Linux图形界面安装配置

高俅定林冲：手持利刃，故入节堂，杀害本官的罪名，将林冲押解去开封府，暗示开封府将林冲处决。 开封府负责办案的叫孙定，他为人刚正不阿，宅心仁厚。在他的据理力争之下，开封府尹最终对…
阅读更多...
【linux】ps的基本使用

【linux】ps的基本使用

ps是linux中用于显示进程的工具，确切来说是显示活动进程的工具 ps的基本格式是 ps [选项] sh-3.2# ps --help ps: illegal option -- - usage: ps [-AaCcEefhjlMmrSTvwXx] [-O fmt | -o fmt] [-G gid[,gid...]][-g grp[,grp...]] [-u [uid,uid...]][-p pid[,pid..…
阅读更多...
windows下redis使用教程

windows下redis使用教程

创建临时服务 redis-server.exe redis.windows.conf启动客户端 验证 # 使用set和get命令，对Redis数据库进行数据存储和获取，如下图所示 config get *创建永久服务 关闭临时服务的cmd窗口，输入以下命令 redis-server.exe --service-insta…
阅读更多...
【设计模式-08】Flyweight享元模式

【设计模式-08】Flyweight享元模式

简要说明 简要的理解：享元模式就是新建一个池(Pool)，该池子(Pool)中有新建好的一堆对象，当需要使用时，从池子(Pool)中直接获取，不用重新新建一个对象。通俗的讲就是：共享元数据。 比如Java中的String就是使…
阅读更多...
Maven详解（入门到精通）学习maven有这个就够了

Maven详解（入门到精通）学习maven有这个就够了

目录 1. Maven简介 2. 什么是Maven? 3. Maven的下载和安装 安装maven核心程序 4.Maven 核心概念 5. 第一个maven项目 创建约定的目录结构 6. 为什么创建约定的目录结构？ 7. 基本的Maven命令 8. 关于联网下载的问题 9. 仓库 10. pom 11.坐标 12. 依赖初步认…
阅读更多...
扎克伯格宣布将购买35万个GPU

扎克伯格宣布将购买35万个GPU

Meta公司马克.扎克伯格1月18日在Instagram上发表文章称，该公司正在加强人工智能研究团队的力量，并在充实AI基础设施“弹药库“，计划在今年年底前向芯片设计商英伟达购买35万个H100 GPU芯片，从而使该公司的GPU总量达到约60万个&…
阅读更多...
蓝桥杯练习题dfs与bfs

蓝桥杯练习题dfs与bfs

📑前言 本文主要是【算法】——dfs与bfs的文章，如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介：大家好，我是听风与他🥇 ☁️博客首页：CSDN主页听风与他 🌄每日一句&#xff…
阅读更多...
璀璨2023，共赴2024——Tempo大数据分析产品年度回顾

璀璨2023，共赴2024——Tempo大数据分析产品年度回顾

随着2024年的到来，2023年已落下了帷幕，这一年里，Tempo大数据分析产品不断追求创新，进行了四次重要的版本升级。为用户带来新功能的同时确保用户在使用产品时获得卓越的体验感，从而更大程度地提升用户的工作效率。 现在…
阅读更多...
最新文章

Copyright @ 2022~2023