当前位置:   article > 正文

C数据结构:循环队列的顺序存储结构_设计循环队列存储结构

设计循环队列存储结构

队列的定义

声明: 本篇博客是实现循环队列。

定义

记住队列是先进先出,FIFO——first in first out,
(和栈的区别也是这个,栈是一头开一头闭,就像一个瓶子,先进的后出)
队列就是两头开,但是当队列用于顺序存贮的时候很容易造成假溢出。

假溢出

假设在队满的,但是尾指针指向的是比队列空间的大小还要大一个位置,所以称之为假溢出,这也是造成空间浪费的一个缺点。

空间浪费的缺点

因为队列是先进先出,所以在队头出队,当队头指针和队尾指针指向的位置一样的时候就表示全部出队成功,但是队头以前指向的空间就无法得以继续利用,就造成了空间浪费。

如何解决

这时候假设我们已经队满了,若想要继续录入信息,大家肯定能想到的是回到头指针的位置继续录入信息。
那么一个叫循环队列的算法解决了这个问题,其实就是用指针让队列形成一个闭环,这样既控制了空间的大小,又防止了出栈时候的空间浪费,因为只要有这两个指针在,按顺序录入的时候总能有一个空间给你录入。

循环队列的缺点

其实与其说是缺点,不如说是程序员不应该选择这个循环队列的算法。缺点就是当队列满队了时候,继续录入信息,我们知道队列的尾部指针会重新指向头部指针,这时候就会造成你前面录入的信息丢失,被新录入的信息覆盖掉。

主要的算法思想(重要)

循环队列可以把他想象成小时候经常看到的幸运转盘,按一个方向旋转,所以进队的时候也是按一个方向进,只是把一个顺序队列用一个算法使之成为看似循环的一个队列。

如何理解循环队列(必看)

这里rear是尾部,front是头部,但是我这个不同的是使用尾进尾出的方式,和其他博客有点不一样,我单纯觉得这样比较好理解。

首先分为三个部分
第一部分: 进队
第二部分: 出队
(在你队满了的时候,若还想继续录入信息,进入下一步)
第三部分: 队头移动+1个位置,在队满的情况下+1会造成假溢出,也就是队头队尾相撞了,那么这时候队尾也进行一个+1的操作,这样就实现了队头队尾一直处于连在一起的形式,也就是形成了循环队列。

考虑的因素
队列还没满的时候想出队的话,也不用担心这个算法会出错,因为你出队的时候也包含在了队头+1移动的操作,第三部的算法肯定能满足这个条件,现在我总是不禁感叹前辈们的智慧,太妙了。

***如果看到这也不懂的话,恕我无力回天。 ***

结构体代码

/*单词顺序表*/
typedef struct _Elem{
	char *word;//存放单词 
	int lenth; 
	int front;
	int rear;
}Elem; 
Elem *temp = NULL;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

两种实现方法

①循环队列,队头和队尾指针连在一起的形式。

(这个方法理解了,那么等下将第二个方法的时候就比较容易理解。)

首先解释一下下面的代码以便理解:
temp结构体,存字符进word这个字符数组里面,word就是一个循环队列,
我们现在是要实现不浪费一个空间写出一个循环队列。

第一个字符进队前,rear和front在同一个位置,但是这时候不能移动空间,因为如果移动了,第一个位置就没有存到信息,所以要再用一个temp->lenth作为判断条件,这个的意思就是当你还没有录入字符的时候,不能进入if语句把front指针进行移动。

下面开始进队,进队的时候把尾部指针rear进行移动+1,所以这时候rear和front指针位置开始不一样了, 这一点很重要,如果没有这步,会直接导致后面的错误。

接下来就是把lenth进行自加,用来记录录入了多少个字符,但是由于该队列是循环队列,不能超过MAXSIZE空间,所以也要一个 限制的大小条件,

#1#: 这时候如果你继续进队,回到第一步的代码里面,进行第二个字符录入,现在可以知道rear和front的位置不一样,所以即使lenth不等于零也无法进入if语句对front指针向前移动+1,←这个是循环队列实现的算法精髓
往后就是一直录入,直到rear = (rear + 1)%MAXSIZE;
#2#: 这个语句运行完成后,变成队满状态了,这时候rear和front 同时% MAXZSIZE ←这也是循环队列实现的算法精髓

不会改变你rear和front的位置关系,所以他们队满的时候他们是相等的,如此来
%MAXSIZE不仅不会造成空间溢出,
rear%MAXSIZE ==front%MAXSIZE && temp->lenth!=0中个条件判断将front向前+1移动的操作 把该队列变成了一个循环队列

下面是伪代码:


if(rear ==front%MAXSIZE && temp->lenth!=0) 
	front = (front+1)%MAXSIZE;

	temp->word[rear] = ch;
	rear = (rear + 1)%MAXSIZE;


if(temp->lenth < MAXSIZE)
{
	temp->lenth++;
} 
		}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

②浪费一个空间形成循序队列

这个的思想就是不用像第一种方法一样要用一个lenth条件来判断是否已经录入一个字符了,这个方法就是简单粗暴的形式,浪费一个空间来使之直接形成循环队列。

代码区别:
if的判断语句变成了 rear%MAXSIZE ==(front+1)%MAXSIZE,去掉了lenth这部分的代码

具体实现如下:

if(rear ==(front+1)%MAXSIZE) front = (front+1)%MAXSIZE;
	temp->word[rear] = ch;
	rear = (rear + 1)%MAXSIZE;
  • 1
  • 2
  • 3

③浪费多个空间

其实你理解了第二个思想的话,很简单就能举一反三,只要把所有的+1修改成+2就代表浪费两个空间,这样也能形成闭环,+3、+4只要按照你的需求来修改就可以,需要注意的是千万不能让你的数组越界,浪费几个空间就要保证你的数组空间足够给你去挥霍,不然程序就很容易越界崩溃掉。

结尾

看完后是不是觉得就几行代码就实现了这么强大的循环队列功能,其实我也是这么觉得的,但是真正理解起来确实一丢丢的时间。

注:本博客主要用文字叙述的方式帮助理解,希望能帮助到各位。
因为我觉得文字叙述虽然比不上图表理解来得更快,但是文字叙述会比图表更能透彻的理解队列。所以如果希望各位耐心读完。
(如有错误请私信我,如果确实有错,到时候我可以直接修改喔~)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/461522
推荐阅读
相关标签
  

闽ICP备14008679号