循环队列 订阅
为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。 展开全文
为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。
信息
特    点
大小固定
实现方式
单链表
有关术语
队列
中文名
循环队列
外文名
Circular Queue
领    域
数据结构
循环队列简介
循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列结构中,当存储空间的最后一个位置已被使用而再要进入队运算时,只需要存储空间的第一个位置空闲,便可将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。 [1]  循环队列可以更简单防止伪溢出的发生,但队列大小是固定的。在循环队列中,当队列为空时,有front=rear,而当所有队列空间全占满时,也有front=rear。为了区别这两种情况,规定循环队列最多只能有MaxSize-1个队列元素,当循环队列中只剩下一个空存储单元时,队列就已经满了。因此,队列判空的条件是front=rear,而队列判满的条件是front=(rear+1)%MaxSize。 [2] 
收起全文
精华内容
下载资源
问答
  • 循环队列

    万次阅读 多人点赞 2018-07-03 10:54:18
    队列是一种只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表(头删尾插),它的存储方式分为顺序队或链队,以循环队列更常见。 这里仅介绍顺序队以及顺序队存在的假溢出缺陷,进而引出循环队列。顺序...
            队列是一种只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表(头删尾插),它的存储方式分为顺序队或链队,以循环队列更常见。
           这里仅介绍顺序队以及顺序队存在的假溢出缺陷,进而引出循环队列。

    顺序队列

                
        在顺序队列中,当队尾指针已经到数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫做“假溢出”,解决假溢出的途径----采用循环队列。

    循环队列

           
    消除假溢出就是当队尾指针rear和队头指针front到达存储空间最大值QueueSize时,让队尾指针自动转化为存储空间的最小值0.
    新问题:
        在循环队列中,空队特征是front = rear, 队满时也会有front = rear; 判断条件将出现二义性
    解决方案有三种:
    1. 加设标志位,让删除动作使其为1,插入动作使其为0, 则可识别当前front == rear;
    2. 使用一个计数器记录队列中元素个数(即队列长度)
    3. 人为浪费一个单元,令队满特征为 front = (rear +1)%N---空闲单元法  
    这里采用空闲单元法解决二义性问题。
    空闲单元法

    实现:
    #include <iostream>
    using namespace std;
    
    #define MAXSIZE 5 //最大队列长度
    
    template<class T>
    class RQueue
    {
    public:
    	RQueue()
    		:_base(NULL)
    		,_front(0)
    		,_rear(0)
    	{
    		_base = (T*) malloc (MAXSIZE*sizeof(T));
    		if(!_base)
    		{
    			cout<<"开辟空间失败"<<endl;
    		}
    	}
    
    	//返回队列元素个数
    	int Length()
    	{
    		return (_rear-_front+MAXSIZE)%MAXSIZE;
    	}
    
    	//插入元素
    	bool Insert(const T& x)
    	{
    		if((_rear+1)%MAXSIZE == _front)//队列满
    		{
    			cout<<"队列已满!"<<endl;
    			return false;
    		}
    
    		_base[_rear] = x;
    		_rear = (_rear+1)%MAXSIZE;
    		return true;
    	}
    
    	//删除元素
    	bool Delete()
    	{
    		if(_front == _rear)
    		{
    			cout<<"队列为空!"<<endl;
    			return false;
    		}
    		_front = (_front+1)%MAXSIZE;
    		return true;
    	}
    
    	
    private:
    	T* _base; //初始化的动态分配存储空间
    	int _front;  //头指针,若队列不空,指向队列头元素
    	int _rear;   //尾指针,若队列不空,指向队列尾元素的下一个位置
    };

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,135
精华内容 8,854
关键字:

循环队列