新干做网站,公司网站如何做百度收录,网站系统架构设计,网站icp备案证明循环队列及其基本操作的C语言实现 前言一、队列的顺序存储1.1 队尾指针与队头指针1.2 基本操作实现的底层逻辑1.2.1 队列的创建与销毁1.2.2 队列的增加与删除1.2.3 队列的判空与判满1.2.4 逻辑的局限性 二、循环队列2.1 循环队列的实现逻辑一2.2 循环队列的实现逻辑二2.3 循环队… 循环队列及其基本操作的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 队列的创建与销毁 队列的创建 对于队列的创建实际上就是定义数据类型、定义队列变量以及初始化一个队列。那如果要定义一个数据类型按照前面的介绍队列的数据类型中至少有三个内容
存放元素的一块连续的存储空间指向队尾的队尾指针rear指向队头的队头指针front
对于这三个内容的实现起始并不复杂我们可以通过静态数组来实现一块连续的存储空间 既然是静态数组那么我们要想找到数组中不同位置的元素那就需要数组下标因此队头指针与队尾指针就需要是两个存放数组下标的整型变量因此我们可以将其用C语言表述为
//队列的顺序存储类型
#define MaxSize 10 //定义队列的最大长度
typedef int ElemType;//重命名队列中数据元素的数据类型可以修改为其它数据类型
typedef struct SqQueue {ElemType data[MaxSize];//存放队列数据元素的静态数组int front, rear; //定义队列的队头指针与队尾指针
}SqQueue; //重命名后的队列数据类型那这样是不是就没问题了呢这里我们先放一放后面再来讨论
在定义好数据类型后我们只需要通过类型来定义一个变量并即将该变量进行初始化即可完成队列的创建。定义变量都很简单关键是这个初识我们应该如何表示
为了更好的理解这个问题那我们来看一下图片 按照两个指针的描述我们在创建队列时应该是如图所示但是现在就有一个问题队尾是负责进行入队操作的队首是负责进行删除操作的我们应该如何来表示队列的插入与删除呢
这里我们需要联想一下栈的插入与删除。在栈中如果栈为空栈时栈顶指针指向的是栈底入栈一个新元素栈顶指针就需要往上移动一位来表示入栈当我们的栈不为空栈时栈顶指针每往下移动一位就是表示出栈。
也就是说在栈中我们是借助指针的移动来表示栈顶的出栈与入栈在队列中我同样也可以仿照这种思路了通过指针的移动来表示入队与出队。因此我们在创建一个队列时可以将front和rear都指向队头如下所示 当有新元素入队时我们可以将队尾指针往上移动当有元素出栈时我们同样可以将队头指针往上移动入下图所示 既然这样那我们就可以在初始化时将队头指针与队尾指针都初始化为0如下所示 Q-front Q-rear 0;//赋值语句的连续赋值形式//等价于下面两句代码//Q-rear 0;//Q-front Q-rear;具体是不是如此我们还是先继续往下看。 队列的销毁 如果我们想要销毁一个队列无非就是将队列中的所有元素依次出队那如果一个存满元素的队列要销毁的话那我们就需要队头指针一直上移如下图所示 如图所示当我们在完全销毁队列后此时的队列的两个指针又重合了并且都指向了队尾转化成C语言则可以表述为 if (Q-front Q-rear Q-rear MaxSize - 1)printf(队列已销毁\n);如果只是这样判断还有没有什么问题呢我们先继续往后看 1.2.2 队列的增加与删除
队列的增加与删除在创建与销毁的讨论中我们已经提到过了当增加一个新的数据元素时我们可以通过队尾指针的移动来表示那现在的问题是队尾指针是应该如何进行移动下面就有几种情况
先入队新的元素再移动指针指向队尾元素的下一个位置先移动指针再入队新元素指针指向队尾元素
用C语言来表达则是 //先入队再移动Q-data[Q-rear] x;//先移动再入队Q-data[Q-rear] x;PS在介绍栈的入栈与出栈时已经介绍过这里的代码简写的意思这里我就不再重复介绍了。 队列的入队逻辑具体选择哪一种我们先不着急接着往下看
当我们要删除一个数据元素时我们可以通过队头指针的移动来表示同样的队头指针的移动和队尾指针一样也有下面几种情况
先出队元素再移动指针指向的是队头元素先移动指针再出队指针指向的是队头元素的前一个位置
用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 逻辑的局限性
在前面对基本操作的实现中我们有提到过以下几个问题
数据类型只定义静态数组和两个指针行不行队列的初始化能不能将两个指针都初始化为0队列的销毁能不能通过两个指针都指向MaxSize-1来判断是否成功销毁队列的增加与删除的逻辑应该是什么队列的判满与判空能不能实现
我们来看一下下面的图片 从上图中我们可以看到按照前面的分析在创建数据类型时只定义静态数组与两个指针并将指针初始化为0的情况下我们要实现一个队列那我们的入队操作与出队操作都应该选择先执行入队或者出队后执行指针的移动并且判满与销毁的判定应该是rearMaxSize; 但是这样就会造成一个问题如下图所示 在这种情况下我们此时的队列并不是满队列但是rear指针已经指向了MaxSize如果我们要继续入队的话此时就会出现数组越界的情况。
也就是说我们前面的分析只适合与创建好队列后从初始化开始到销毁结束中间的流程都不能发生任何变化即入队就要全部元素入满出队就要直接到销毁。
这样实现的队列就好比一次性碗筷只能够使用一次感受一下并不能重复利用那我们应该如何调整才能实现一个完整的队列呢这里就需要引入一个新的概念——循环队列
二、循环队列
2.1 循环队列的实现逻辑一
所谓的循环队列并不是指像循环链表那种头尾相连的结构队列的存储结构依然是顺序存储只不过指针存储的范围是0MaxSize-1通过指针的这种存储的循环方式将队列看做一个环如下图所示 此时我们各个操作的执行逻辑如下所示
数据类型的定义此时我们只需要定义三个对象——存储数据元素的一维数组指向队头元素的队头指针与指向队尾元素下一个位置的队尾指针初始化在初始化时我们将队头指针与队尾指针都初始化为0使他们同时指向数组首元素的位置判空我们在进行判空时只需要判断front rear 这个条件是否成立成立则为空队列否则为非空队列入队入队时的逻辑是先入队后移动即data[rear] x;rear;简写为data[rear] x判满为了保证判空的逻辑正常此时我们需要舍弃最后一个空间来作为判满的条件也就是说当队尾指针的下一个位置为队头指针时表示队列已满也就是rear front;当条件成立时表示队列已满否则表示队列未满出队在进行出队操作时的逻辑则是先出队后移动即x data[front];front;简写为x data[front]销毁在进行销毁时我们需要重复进行出队操作当队头指针与队尾指针再一次指向同一个位置时表示队列中的元素已经全部出队此时队列为空队列之后我们在将对应的空间释放掉就行因为是通过静态数组实现所以当程序结束后空间就会被操作系统自动回收
这时可能就有朋友会说了你像这个样子不就造成了空间的浪费吗有没有什么办法可以将这一块空间也给利用起来呢
2.2 循环队列的实现逻辑二
首先对于空间浪费的问题我想说的是我们这里只浪费了一个数据类型所需的空间相比于之前的一次性队列来说我们在利用上面会节省更多的内存空间 最后我们也可以通过对数据类型的调整来完成队列空间的饱和运用如下所示 我们通过设定一个记录当前队列长度的变量len在这种情况下我们的基本操作就需要做出如下调整
数据类型的定义增设一个记录当前队列长度的变量len初始化在初始化时需要将当前队列长度初始化为0判空在判空时我们可以直接判断len 0是否成立成立则为空队列否则为非空队列入队每次完成一个新元素入队后我们都需要执行一次len判满在判满时我们可以直接判断len MaxSize是否成立成立队列已入满否则队列还未满出队每完成一个元素的出队后我们都需要执行一次len--销毁在完成所有的元素出队后此时的队列长度又会变为0所以我们只需要指向判空操作即可
这时可能又有朋友会问你这里是将队尾指针指向的是队尾元素的下一个位置那如果我将其指向队尾元素又应该如何操作呢
2.3 循环队列的实现逻辑三
其实这个实现方式也有很多种这里我们还是以初始化为0的情况下来实现如下所示
我们通过增设一个入队标志tag来表示当前空间元素的入队情况对应的基本操作就有如下调整
数据类型的定义增设一个标志变量tag当tag 0时表示此时的空间没有元素入队当tag 1时表示此时的空间有元素入队初始化在初始化阶段我们需要将队头指针初始化为0入队标志初始化为0队尾指针初始化为MaxSize - 1判空在进行判空时我们需要通过判断rear front tag 0是否成立成立则队列为空队列否则队列为非空队列入队在进行入队操作时此时的入队逻辑是先移动后入队即rear;data[rear] x;简写为data[rear] x并且我们还需要将入队标志tag修改为1如下图所示 判满在判断队列是否入满时我们需要判断rear front tag 1是否成立成立则说明此时的队列已满否则此时的队列未满出队在进行出队操作时我们需要将入队标志tag修改为0如下图所示 销毁在完成所有元素出队后队列又会变为空队列因此我们只需要进行判空即可
循环队列的实现逻辑主要是有以上三种方式当然肯定还有其他的方式但是操作上基本上都是大同小异现在我们还有一个最重要的问题还有有提到——如何实现队列的循环
三、如何实现队列的循环
在前面的逻辑中我们来判断空队列和满队列时有提过通过判断队尾指针的下一个空间是否为队头指针我们前面也是通过rear front来说明这种判断的过程但是在实际实现中这是有问题的因为我们是通过静态数组实现的队列它在内存中还是以顺序存储的形式进行存放的如下所示 我们是将这种连续存放的空间臆想为一个环状结构但并不代表它就是一个环状结构因此我们只能够通过指针来完成队列的循环。
那如何实现呢我们现在先来思考一下这两个指针存放的是什么内容
没错就是数组下标在前面我们也有提到过它们的取值范围是0MaxSize - 1只要我能够保证不管如何进行入队和出队操作它们的取值都是在这个范围内那就能实现队列的循环操作。
在C语言中我们有介绍过一个只能够在整型中使用的算术操作符——%取模这个操作符的作用就是获取两个整数相除后的余数就比如在整型运算中我们知道 5 / 2 2 … … 1 5/22……1 5/22……1在C语言中我们通过 / / /来获取两个整数的商通过 % \% %来获取两个整数的余数如下所示 在除法 a / b c … … d a / b c …… d a/bc……d中d的取值肯定是在[0 , b - 1]之间的也就是说如果通过对下标进行与MaxSize取模的话那是不是就能保证指针存储的值一定是在[0 , MaxSize - 1]之间了呢
下面我们可以通过代码来测试一下如下所示 可以看到确实如此通过取模运算后得到的值正好是在[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为空指针时返回falseQ-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);elseprintf(出队失败\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为空指针时返回falseQ-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);elseprintf(出队失败\n);}return true;
}
void test_Queue1() {SqQueue Q;//定义队列Qif (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);elseprintf(此时的队列为非空队列\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为空指针时返回falseQ-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;//执行入队操作入队标志改为1return 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;//指向出队操作入队标志改为0return 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);elseprintf(出队失败\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为空指针时返回falseQ-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;//执行入队操作入队标志改为1return 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;//指向出队操作入队标志改为0return 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);elseprintf(出队失败\n);}return true;
}
void test_Queue2() {SqQueue Q;//定义队列Qif (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);elseprintf(此时的队列为非空队列\n);}//队列销毁if (DestroyQueue(Q)) {printf(队列成功销毁\n);}else {printf(队列销毁失败\n);}
}下面我们就来在主函数中调用并测试一下看看结果 可以看到此时的标志法实现时能够比空间置换法要多存储一个元素我们现在也成功使用C语言通过标志法实现了循环队列。
结语
在今天的篇章中我们详细介绍了队列的顺序存储结构——循环队列并详细分析了三种实现循环队列的方式最后通过C语言实现了两种循环队列——空间置换法与标志法希望今天的内容能够帮助大家在了解队列的顺序存储结构的同时还能帮助大家熟悉对应的基本操作并能够实现对应的操作。
今天的内容到这里就全部结束了在下一个篇章中我们将开始介绍队列的链式存储结构通过链式存储的队列的基本操作又应该如何实现呢就让我们期待一下下一篇的内容介绍吧最后感谢大家的翻阅咱们下一篇再见
