精华内容
下载资源
问答
  • 循环队列属于什么结构
    千次阅读
    2022-03-28 19:10:43

    目录

    概念

    循环队列的作用

    题目

    注意事项

    题解

    用顺序表的实现

    用链表的实现


    概念

     基于队列的先进先出的原则,在确定了队列长度的前提下,另队列首尾相接而实现的一种结构。

    循环队列的作用

    循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/design-circular-queue

    查看源图像

    题目

    设置循环队列

    注意事项

    单纯把链表的首尾相接就可以吗?

    那么我们来想想这样一个问题:空的循环队列是什么样的?

    我们规定将头指针放在首元素的位置,尾指针放到尾元素的下一个位置,那空队列就是头指针和尾指针指向同一个位置。

    那么,满的循环链表又是什么样的呢?

    尾指针放在a8元素的后面,恰好又与空链表的指向完全相同。

    那我们怎么解决呢?

    难道在结构体放一个变量判断它是否以满吗?不是不可以,但稍微有点“笨重”。

    所以我们不妨让队列多添加一个位置,这个位置不放任何元素,仅仅是为了区别空与满:

     

    题解

    与通常队列相似,循环队列同样也可以用链表与顺序表两种方式实现

    用顺序表的实现

    typedef int CQDataType;
    typedef struct 
    {
    	CQDataType* cq;
    	int head;
    	int tail;
    	int size;
    } myCircularQueueEnQueue;
    bool myCircularQueueEnQueueIsFull(myCircularQueueEnQueue* obj);
    bool myCircularQueueEnQueueIsEmpty(myCircularQueueEnQueue* obj);
    //构造器,设置队列长度为 k 
    myCircularQueueEnQueue* myCircularQueueEnQueueCreate(int k) 
    {
    	myCircularQueueEnQueue* newCQ = (myCircularQueueEnQueue*)malloc(sizeof(myCircularQueueEnQueue));
    	assert(newCQ);
    	CQDataType* newcq = (CQDataType*)malloc(sizeof(CQDataType) * (k + 1));
    	assert(newcq);
    	newCQ->size = k;
    	newCQ->cq = newcq;
    	newCQ->head = 0;
    	newCQ->tail = 0;
    	return newCQ;
    }
    //向循环队列插入一个元素。如果成功插入则返回真
    bool myCircularQueueEnQueueEnQueue(myCircularQueueEnQueue* obj, int value) 
    {
    	if (myCircularQueueEnQueueIsFull(obj))
    	{
    		return 0;
    	}
    	obj->cq[obj->tail] = value;
    	obj->tail = (obj->tail + 1) % (obj->size + 1);
    	return 1;
    }
    //从循环队列中删除一个元素。如果成功删除则返回真
    bool myCircularQueueEnQueueDeQueue(myCircularQueueEnQueue* obj)
    {
    	if (myCircularQueueEnQueueIsEmpty(obj))
    	{
    		return 0;
    	}
    	//obj->head = ((obj->size + 1) + (obj->tail - 1)) % (obj->size + 1);
    	obj->head = (obj->head + 1) % (obj->size + 1);
    	return 1;
    }
    //从队首获取元素。如果队列为空,返回 -1
    int myCircularQueueEnQueueFront(myCircularQueueEnQueue* obj)
    {
    	if (obj->head == obj->tail)
    	{
    		return -1;
    	}
    	else
    	{
    		return obj->cq[obj->head];
    	}
    }
    // 获取队尾元素。如果队列为空,返回 -1
    int myCircularQueueEnQueueRear(myCircularQueueEnQueue* obj)
    {
    	if (obj->head == obj->tail)
    	{
    		return -1;
    	}
    	else
    	{
    		return obj->cq[((obj->size + 1) + (obj->tail - 1)) % (obj->size + 1)];
    	}
    }
    //检查循环队列是否为空
    bool myCircularQueueEnQueueIsEmpty(myCircularQueueEnQueue* obj) 
    {
    	return obj->head == obj->tail;
    }
    //检查循环队列是否已满
    bool myCircularQueueEnQueueIsFull(myCircularQueueEnQueue* obj)
    {
    	return (obj->tail + 1) % (obj->size + 1) == obj->head;
    }
    //释放
    void myCircularQueueEnQueueFree(myCircularQueueEnQueue* obj) 
    {
    	free(obj->cq);
    	free(obj);
    }
    

    用链表的实现

    typedef int CQDataType;
    typedef struct CQListNode
    {
    	struct CQListNode* _next;
    	CQDataType _data;
    }CQNode;
    typedef struct 
    {
    	CQNode* _head;
    	CQNode* _tail;
    	int size;
    } MyCircularQueue;
    bool myCircularQueueIsFull(MyCircularQueue* obj);
    bool myCircularQueueIsEmpty(MyCircularQueue* obj);
    
    
    MyCircularQueue* myCircularQueueCreate(int k)
    {
    	MyCircularQueue* CQ = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    	assert(CQ);
    	CQ->size = k;
    	CQNode* head = (CQNode*)malloc(sizeof(CQNode));
    	assert(head);
    	CQNode* cur = CQ->_head = CQ->_tail = head;
    	for (int i = 0; i < k; i++)//加上面共k+1个节点
    	{
    		CQNode* cq = (CQNode*)malloc(sizeof(CQNode));
    		assert(cq);
    		cur->_next = cq;
    		cq->_next = NULL;
    		cur = cur->_next;
    	}
    	cur->_next = head;
    
    	return CQ;
    }
    
    
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
    {
    	if (!myCircularQueueIsFull(obj))
    	{
    		obj->_tail->_data = value;
    		obj->_tail = obj->_tail->_next;
    		return 1;
    	}
    	else
    	{
    		return 0;
    	}
    	
    }
    
    bool myCircularQueueDeQueue(MyCircularQueue* obj)
    {
    	if (!myCircularQueueIsEmpty(obj))
    	{
    		obj->_head = obj->_head->_next;
    		return 1;
    	}
    	else
    	{
    		return 0;
    	}
    }
    
    int myCircularQueueFront(MyCircularQueue* obj)
    {
    	if (!myCircularQueueIsEmpty(obj))
    		return obj->_head->_data;
    	else
    		return -1;
    }
    
    int myCircularQueueRear(MyCircularQueue* obj)
    {
    	if (!myCircularQueueIsEmpty(obj))
    	{
    		CQNode* cur = obj->_head;
    		while (cur->_next != obj->_tail)
    		{
    			cur = cur->_next;
    		}
    		return cur->_data;
    	}
    	else
    		return -1;
    }
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
    {
    	return obj->_head == obj->_tail;
    }
    
    bool myCircularQueueIsFull(MyCircularQueue* obj)
    {
    	return obj->_tail->_next == obj->_head;
    }
    
    void myCircularQueueFree(MyCircularQueue* obj)
    {
    	/*CQListNode* cur = obj->_head;
    	while(cur->_next!=cur)*/
    	CQNode* cur = obj->_head;
    	CQNode* next = NULL;
    
    	for (int i = 0; i < obj->size; i++)
    	{
    		next = cur->_next;
    		free(cur);
    		cur = next;
    	}
    	free(obj);
    }
    

    更多相关内容
  • 本文讲的是循环队列,首先我们必须明白下面几个问题 循环队列的基础知识 1.循环队列需要几个参数来确定 循环队列需要2个参数,front和rear 2.循环队列各个参数的含义 (1)队列初始化时,front和rear值都为零;...
  • 数据结构循环队列的基本操作,分享一下,欢迎大家批评指正!
  • 淮海工学院计算机科学系 实验报告书 课程名 数据结构 题 目 数据结构实验 链队列和循环队列 班 级 学 号 姓 名 评语 成绩 指导教师 批阅时间 年 月 日 数据结构 实验报告 - 1 - 线性数据结构算法实现与应用报告要求 ...
  • 循环队列数据结构

    2017-07-03 14:59:42
    本代码在visual studio enterprise 2015 测试通过,请用户自行调试。若在其它编译器上调试,请将里面的scanf_s改回scanf。
  • 为了解决假溢出,我们将存储队列的数组头尾相接,从而产生了循环队列。 如何判断循环队列队空? 队空:front=rear 如何盘对循环队列堆满? 队满:front=rear 那么问题就来了,队空和队满的判断条件相同,为了...
  • 数据结构-基本算法-循环队列(学生时代源码,调试可运行)
  • 今天我们来到了循环队列这一节,之前的文章中,我介绍过了用python自带的列表来实现队列,这是最简单的实现方法。 但是,我们都知道,在列表中删除第一个元素和删除最后一个元素花费的时间代价是不一样的,删除列表...
  • 数据结构的作业,只有尾指针的循环队列,可以入队出队打印等
  • 数据结构循环队列

    千次阅读 2022-04-12 18:48:24
    循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。 环形队列可以使用数组实现,也可以使用循环链表实现。 重点:循环队列,无论使用数组实现还是链表实现,都要多开一个空间,也...

    目录

    一、循环队列的概念

    二、设计循环队列

    思路一:数组实现

     思路二:链表实现


    一、循环队列的概念

    为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。

    环形队列可以使用数组实现,也可以使用循环链表实现。
    重点:循环队列,无论使用数组实现还是链表实现,都要多开一个空间,也就意味着,要是一个存k个数据的循环队列,要开k+1个空间,否则无法实现判空和满

    数组实现:

     链表实现:

     

     

    二、设计循环队列

    622. 设计循环队列 - 力扣(LeetCode) (leetcode-cn.com)

    题目:设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
    循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

    你的实现应该支持如下操作:
    MyCircularQueue(k): 构造器,设置队列长度为 k 。
    Front: 从队首获取元素。如果队列为空,返回 -1 。
    Rear: 获取队尾元素。如果队列为空,返回 -1 。
    enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
    deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
    isEmpty(): 检查循环队列是否为空。
    isFull(): 检查循环队列是否已满。

    思路一:数组实现

    代码:

    typedef struct 
    {
        int* a;//数组
        int front;
        int tail;
        int k;
    } MyCircularQueue;
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj);
    bool myCircularQueueIsFull(MyCircularQueue* obj);
    
    MyCircularQueue* myCircularQueueCreate(int k) 
    {
        //创建一个循环队列
        MyCircularQueue* cq =  (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
        //将循环多列中的成员初始化
        cq->a = (int*)malloc(sizeof(int) * (k+1));//数组创建为k+1个空间
        cq->front = cq->tail = 0;//为空
        cq->k = k;
        return cq;
    }
    
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
    {
        //插入,首先要判断是否满
        if(myCircularQueueIsFull(obj))
        {
            return false;
        }
        //没满就插入数值
        obj->a[obj->tail] = value;
        obj->tail++;
        //如果为尾元素,则要模除
        obj->tail %= (obj->k+1);
        return true;
    }
    
    bool myCircularQueueDeQueue(MyCircularQueue* obj) 
    {
        //删除则要判断是否为空
        if(myCircularQueueIsEmpty(obj))
        {
            return false;
        }
        //删除front++
        obj->front++;
        //如果为尾元素,则要模除
        obj->front %= (obj->k+1);
        return true;
    }
    
    int myCircularQueueFront(MyCircularQueue* obj) 
    {
        if(myCircularQueueIsEmpty(obj))
        {
            return -1;
        }
        return obj->a[obj->front];
    
    }
    
    int myCircularQueueRear(MyCircularQueue* obj) 
    {
        if(myCircularQueueIsEmpty(obj))
        {
            return -1;
        }
        //tail指向的是队尾元素的前一个节点,当tail == 0时,则队尾元素是第k个,其他的都是前一个节点
        if(obj->tail == 0)
        {
            return obj->a[obj->k];
        }
        else
        {
            return obj->a[obj->tail-1];
        }
    }
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj)
    {
        if(obj->front == obj->tail)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    bool myCircularQueueIsFull(MyCircularQueue* obj) 
    {
        if((obj->tail+1)%(obj->k+1) == obj->front)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    void myCircularQueueFree(MyCircularQueue* obj) 
    {
        free(obj->a);
        free(obj);
    }
    
    /**
     * Your MyCircularQueue struct will be instantiated and called as such:
     * MyCircularQueue* obj = myCircularQueueCreate(k);
     * bool param_1 = myCircularQueueEnQueue(obj, value);
     
     * bool param_2 = myCircularQueueDeQueue(obj);
     
     * int param_3 = myCircularQueueFront(obj);
     
     * int param_4 = myCircularQueueRear(obj);
     
     * bool param_5 = myCircularQueueIsEmpty(obj);
     
     * bool param_6 = myCircularQueueIsFull(obj);
     
     * myCircularQueueFree(obj);
    */

    运行结果:

     思路二:链表实现

    代码:

    
    typedef struct Node
    {
        int data;
        struct Node* next;
    }Node;
    
    typedef struct 
    {
      Node* head;
      Node* tail;
    } MyCircularQueue;
    
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj);
    bool myCircularQueueIsFull(MyCircularQueue* obj);
    
    MyCircularQueue* myCircularQueueCreate(int k) 
    {
         MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
         cq->head = (Node*)malloc(sizeof(Node));
         //k个元素要创建k+1个节点,所以再创建出k个节点的空间
         Node* cur = cq->head;
         while(k--)
         {
           cur->next = (Node*)malloc(sizeof(Node));
           cur = cur->next;
         }
         //将收尾连接,形成循环链表
         cur->next = cq->head;
         //初始化tail
         cq->tail= cq->head;
         return cq;
    }
    
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
    {
        //如果满了就返回false
        if(myCircularQueueIsFull(obj))
        {
            return false;
        }
        //如果没满就进行插入数值
        obj->tail->data = value;
        obj->tail =obj->tail->next;
        return true;
    }
    
    bool myCircularQueueDeQueue(MyCircularQueue* obj) 
    {
        //如果为空,则返回false
        if(myCircularQueueIsEmpty(obj))
        {
            return false;
        }
        obj->head = obj->head->next;
        return true;
    }
    
    int myCircularQueueFront(MyCircularQueue* obj) 
    {
        if(myCircularQueueIsEmpty(obj))
        {
            return -1;
        }
        return obj->head->data;
    }
    
    int myCircularQueueRear(MyCircularQueue* obj) 
    {
       if(myCircularQueueIsEmpty(obj))
        {
            return -1;
        }
        //队尾元素为tail的前一个节点的元素
        Node* cur = obj->tail;
        while(cur->next != obj->tail)
        {
            cur = cur->next;
        }
        return cur->data;//返回队尾元素
    }
    
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj)
    {
        if(obj->head == obj->tail)
        {
            return true;
        }
        return false;
    }
    
    bool myCircularQueueIsFull(MyCircularQueue* obj) 
    {
        if(obj->tail->next == obj->head)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    void myCircularQueueFree(MyCircularQueue* obj) 
    {
        Node* cur = obj->head;
        Node* next = obj->head;
        while(cur->next != obj->head)
        {
            next = cur->next;
            free(cur);
            cur = next;
        }
        free(cur);
        free(obj);
    }
    
    /**
     * Your MyCircularQueue struct will be instantiated and called as such:
     * MyCircularQueue* obj = myCircularQueueCreate(k);
     * bool param_1 = myCircularQueueEnQueue(obj, value);
     
     * bool param_2 = myCircularQueueDeQueue(obj);
     
     * int param_3 = myCircularQueueFront(obj);
     
     * int param_4 = myCircularQueueRear(obj);
     
     * bool param_5 = myCircularQueueIsEmpty(obj);
     
     * bool param_6 = myCircularQueueIsFull(obj);
     
     * myCircularQueueFree(obj);
    */

    运行结果:

     本文为本人对于循环链表的学习,如有问题,请评论区多多评论哈^_^

    展开全文
  • 数据结构中队列源程序: 顺序队列.c 顺序循环队列.c 链式队列.c
  • - PAGE PAGE 2 欢迎下载 实验四 队列循环队列的创建添加和删除操作 1实验目的掌握循环队列的基本操作并对其进行简单应用 2实验内容 假设循环队列的最大长度为7现在依次将以下数据入队列{753924}接着进行3次出队列的...
  • 622. 设计循环队列 难度: 中等 题目分析: 看下面代码实现。参考的是裘宗燕的《数据结构与算法:Python语言描述》。此处不建议使用python内置的list的append, pop操作,使用了就违背设计循环队列的初衷:消除...
  • 数据结构循环队列.CPP

    2020-12-24 13:02:43
    循环队列
  • 数据结构循环队列的代码。。。。。。。。。。。。。。。
  • 本文实例讲述了JavaScript数据结构之优先队列与循环队列。分享给大家供大家参考,具体如下: 优先队列 实现一个优先队列:设置优先级,然后在正确的位置添加元素。 我们这里实现的是最小优先队列,优先级的值小...
  • 主要介绍了java数据结构与算法之双向循环队列的数组实现方法,结合实例形式分析了双向循环队列的原理与数组实现技巧,并附带说明了该算法的用途,需要的朋友可以参考下
  • /* 队列的顺序存储结构(循环队列) */ #define MAX_QSIZE 5 /* 最大队列长度+1 */ typedef struct { QElemType *base; /* 初始化的动态分配存储空间 */ int front; /* 头指针,若队列不空,指向
  • 如何实现循环队列

    2020-12-31 18:43:21
    静态队列一般用数组来实现,但此时的队列必须是循环队列,否则会造成巨大的内存浪费;链式队列是用链表来实现队列的。 #ifndef SQQUEUE_H_INCLUDED #define SQQUEUE_H_INCLUDED /* 防止重复包含 */ //////////////...
  • 数据结构 严蔚敏 C语言版 循环队列 很给劲哦 绝对不会令您失望的。
  • 数据结构循环队列的C语言实现
  • 循环队列的顺序存储结构Java

    千次阅读 2019-12-19 16:33:54
    循环队列的顺序存储结构 在上次,我们讲到的是,队列的顺序存储结构也是由ArrayList实现的,从此就可以看出,在入队时候的时间复杂度为O(1),但是在出队时候的时间复杂度为O(n),这是因为,每次在出队后要将数组后面...

    循环队列的顺序存储结构

    在上次,我们讲到的是,队列的顺序存储结构也是由ArrayList实现的,从此就可以看出,在入队时候的时间复杂度为O(1),但是在出队时候的时间复杂度为O(n),这是因为,每次在出队后要将数组后面的有效元素前移一位
    所以,这里就会用到循环队列,显然,这种队列也是顺序存储结构,在这个循环队列中也会去实现接口Queue。
    首先,我们要想到的是如何将一般的队列改变为循环队列。

    • 和之前一般的队列的顺寻存储结构一样,默认初始数组容量为10(循环队列的数组实际容量为11,这是因为要空出一个数组空间,至于为什么,将在后面进行解释);
    • 定义一个头指针front和尾指针rear,用这两个指针去维护循环队列中元素的入队和出队;
    • 定义一个size,去统计当前循环队列中的元素的有效个数;

    现在,我们先看一下循环队列是如何入队和出队的。
    初始时:
    在这里插入图片描述

    入队一个元素:
    在这里插入图片描述

    出队一个元素:
    在这里插入图片描述
    这样,front和rear指针就可以很轻松的去维护循环队列的入队和出队,并且它们的时间复杂度都为O(1),但是要注意特殊情况的存在,比如,当数组的0角标没有元素但7角标也有元素的时候,rear指针就要移动到front的前面,如下图所示:

    在这里插入图片描述

    这个时候很明显,循环队列已经满了,所以我们就会想到,如何判断循环队列什么时候为满,什么时候为空?

    其实,利用它的周期性可以很明显的得出结论:
    队列为满的时候:(rear+1)%n == front; (n为数组的总长度;如上图:(0+1)%8等于1也就是等于front指向的位置)
    如果出现这种情况,如下图示:
    在这里插入图片描述

    因为,我们每次的出队,front指针都会向后面移动一位,而rear指针是不会移动的,如果我们将上图的两个元素全部出队列,会出现这样的情况:
    在这里插入图片描述

    很显然,判断队列为空也为:(rear+1)%n == front;

    这样的话就会重复,所以这就是我们之前说,为什么要在创建循环队列数组的时候多创建一个元素空间的原因了。
    因此,判断队列为空的条件就为:rear == front;
    如下图:
    在这里插入图片描述

    如上图,我们现在入队一个元素:
    在这里插入图片描述

    每次在入队的时候,将rear指针始终指向队尾最后一个元素的空间。
    并且每次入队的时候,rear的变化也要注意:rear = (rear+1)%n;

    说了这么多,我们就来看一下具体的代码实现。
    首先和我们之前一样,先来看看它的顺序存储结构:

    package DS01.动态数组;
    import java.util.Iterator;
    /**
     * @author 七夏
     * @param <E>
     * @version 1.0
     * 循环队列:如果我们默认创建一个为容量为10的的循环队列时,我们须在该循环队列容量的基础上再加1,
     * 这是为了在判断循环队列是否为空时,起到作用
     *
     * 循环队列为满时的条件:(rear+1)%data.length 等于 front
     * 循环队列为空时的条件:front == rear
     * 元素每次进队时,队头front每次更新:front = (front+1)%data.length
     * 元素每次出队时,队尾rear每次更新:rear = (rear+1)%data.length
     * 函数 E getRear() 在获取队尾元素时的方法为:data[(rear-1+data.length)%data.length]
     */
    public class ArrayQueueLoop<E> implements Queue<E>{
    	//设置默认初始容量(后面会加1)
        private static final int DEFAULT_CAPACITY = 10;
        private E[] data;
        private int front;
        private int rear;
        private int size;
    
        public ArrayQueueLoop(){
            this(DEFAULT_CAPACITY);
        }
        public ArrayQueueLoop(int capacity){
            if(capacity <= 0){
                throw new IllegalArgumentException("指定容量错误:"+capacity);
            }
            data = (E[])(new Object[capacity+1]);//加1,让数组多出一个空间
            front = 0;
            rear = 0;
            size = 0;
        }
    }
    

    现在,看一下入队代码:

    	@Override
        public void enqueue(E e) {
        	//判断队列是否满
            if((rear + 1)%data.length == front){
                //扩容
                resize(data.length*2-1);
            }
            data[rear] = e;
            //更新rear队尾指针位置
            rear = (rear+1)%data.length;
            size++;
        }
    

    出队:

    	@Override
        public E dequeue() {
            if(isEmpty()){
                throw new IllegalArgumentException("队列为空");
            }
            //拿出对头元素
            E res = data[front];
            //更新front对头指针位置
            front = (front+1)%data.length;
            size--;
            //缩容
            if(size <= (data.length-1)/4 && (data.length-1)/2 >= 10){
                resize(data.length/2+1);
            }
            return res;
        }
    

    扩容:

    	private void resize(int newLen) {
            E[] newData = (E[])(new Object[newLen]);
            int p = front;
            int i = 0;
            while(true){
                newData[i] = data[p];
                i++;
                p = (p+1)%data.length;
                //如果p指针等于rear队尾指针时,结束循环
                if(p == rear){
                    break;
                }
            }
            /*
            上述while循环相当于下述for循环
            for(int i = 0,p = front;p != rear;i++,p = (p+1)%data.length){
    			newData[i] = data[p];
    		}
            */
            front = 0;
            rear = size;
            data = newData;
        }
    

    实现iterator方法:
    和之前都大致类似,在这里,我们在内部类中首先定义一个p指针,用来遍历循环队列,在hasNext函数中,只要p指针不等于rear队尾指针,说明该循环队列“尚不为空”(当前指向的元素后面还有元素);next函数中,创建res变量获取当前元素,之后将更新p指针的位置,最终返回res。

    	@Override
        public Iterator<E> iterator() {
            return new ArrayQueueLoopIterator();
        }
        private class ArrayQueueLoopIterator implements Iterator<E>{
            int p = front;
            @Override
            public boolean hasNext() {
                return p != rear;
            }
    
            @Override
            public E next() {
                E res = data[p];
                //更新p指针的指向位置
                p = (p+1)%data.length;
                return res;
            }
        }
    

    其他方法:
    在这些方法中,我们要注意toString方法和getRear方法,在getRear方法中,我们直接返回data[(rear-1+data.length)%data.length]。

    	@Override
        public int getSize() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0 && front == rear;
        }
        @Override
        public E getFront() {
            if(isEmpty()){
                throw new IllegalArgumentException("队列为空");
            }
            return data[front];
        }
    
        @Override
        public E getRear() {
            if(isEmpty()){
                throw new IllegalArgumentException("队列为空");
            }
            return data[(rear-1+data.length)%data.length];
        }
    
        @Override
        public void clear() {
            data = (E[])(new Object[DEFAULT_CAPACITY+1]);
            front = 0;
            rear = 0;
            size = 0;
        }
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(String.format("ArrayQueue: %d/%d \n",getSize(),data.length-1));
            sb.append('[');
            if(isEmpty()){
                sb.append(']');
            }else{
                for (int i = front; i != rear; i = (i+1)%data.length) {
                    sb.append(data[i]);
                    if((i+1)%data.length == rear){
                        sb.append(']');
                    }else{
                        sb.append(',');
                    }
                }
            }
            return sb.toString();
        }
    
    展开全文
  • 数据结构与算法C++实现 循环顺序队列的初始化,求长度,入队,出队 适合大二初学数据结构与算法 程序有详细备注,可直接运行 顺序表
  • 队列文档之循环队列

    千次阅读 2022-05-09 22:28:50
    循环队列就是将顺序队列臆造成一个环状的空间(实际上不是,只是把它看成是环状的),即把存储队列元素的顺序表从逻辑上视为一个环。

    循环队列

    定义

    概念

    为了解决顺序队列“假溢出”的缺陷,所以引入了循环队列。

    关于顺序队列请参考:顺序队列

    循环队列就是将顺序队列臆造成一个环状的空间(实际上不是,只是把它看成是环状的),即把存储队列元素的顺序表从逻辑上视为一个环。当队头指针 queue.front==MAXSIZE-1 时(即到数组的最后一个位置了),再前进一个位置就自动到 0,这可以利用除法取余运算(%)来实现。

    在这里插入图片描述

    通常采用数组来实现,当然也可以通过链表来实现循环队列。

    关于循环队列的状态和操作如下:

    • 初始化:queue.front=0; queue.rear=0;

    在这里插入图片描述

    • 入队操作:先将新元素赋予队尾指针所指向的位置,然后队尾指针加一。但循环队列中加一操作与顺序队列有所不同:queue.rear=(queue.rear+1)%MAXSIZE。是为了当达到 MAXSIZE-1 位置后下一个位置自动到 0 去。
    • 出队操作:取出队头指针所指向的位置的元素,然后队头指针加一。但循环队列中加一操作与顺序队列有所不同:queue.front=(queue.front+1)%MAXSIZE
    • 队列长度:也跟顺序队列求队列长度有所不同,是:(queue.rear-queue.front+MAXSIZE)%MAXSIZE

    循环队列最大的问题就是如何判断队空和队满。之前顺序队列判断队空的条件 queue.front==queue.rear 是无法判断循环队列是队空还是队满的,因为循环队列队空和队满时 queue.front==queue.rear 条件都成立。如图:

    在这里插入图片描述

    为什么循环队列队满时,队头指针 front 和队尾指针 rear 会重合呢?如图所示,因为队头指针始终指向队头元素,而队尾指针指向队尾元素的下一个位置,所以当队满时,它们会重合。所以 queue.front==queue.rear 是无法作为单独判断队空和队满条件。

    因此,为了区分是队空还是队满的清空,有三种处理方式:

    • 第一种,牺牲一个单元来区分队空和队满,入队时少用一个队列单元,这是一种比较普通的做法,本篇也是采用的这种做法。约定以队头指针在队尾指针的下一位置作为队满的标志。如图所示:
      • 队满条件:(queue.rear+1)%MAXSIZE==queue.front
      • 队空条件:queue.front==queue.rear
      • 队列种的元素个数:(queue.rear-queue.front+MAXSIZE)%MAXSIZE

    在这里插入图片描述

    • 结构体类型中增设表示元素个数的数据成员 size。这两种情况都有 queue.front==queue.rear,但不再作为判空或判满的条件。

      • 队满条件:queue.size==MAXSIZE
      • 队空条件:queue.size==0
    • 结构体类型中增设 tag 数据成员,用来区分是队满还是队空。约定 tag 等于 0 时,若因删除导致 queue.front==queue.rear 则为队空;当 tag 等于 1 时,若因插入导致 queue.front==queue.rear 则为队满。有一道练习题就是实现该队列:Example004-设计一个循环队列,用 front 和 rear 分别作为队头和队尾指针,另外用一个标志 tag 表示队列是空还是不空

      • 队满条件:queue.tag==1 && queue.front==queue.rear
      • 队空条件:queue.tag==0 && queue.front==queue.rear

    结构体

    /**
     * 循环队列结构体定义
     */
    typedef struct {
        /**
         * 数据域,存储循环队列中的数据
         */
        int data[MAXSIZE];
        /**
         * 指针域,存储循环队列中队头元素的位置
         */
        int front;
        /**
         * 指针域,存储循环队列中队尾元素的位置
         */
        int rear;
    } CircularQueue;
    

    特点

    • front 表示队头指针,实际上就是数组下标,指向顺序队列的队头元素;rear 表示队尾指针,指向顺序队列的队尾元素的下一个位置。
    • 如果队尾指针 rear 到达 MAXSIZE-1 位置,则会自动跳到 0 位置。
    • 循环队列能充分利用队列中的空余空间,直到队列中所有空间(除了用来判断队空或队满的一个空间)都被使用。

    基本操作

    注,完整代码请参考:

    概述

    循环队列的常见操作如下:

    • void init(CircularQueue *queue):初始化循环队列。其中 queue 表示循环队列。
    • int isEmpty(CircularQueue queue):判断循环队列是否为空。其中 queue 表示循环队列。如果循环队列为空则返回 1,否则返回 0。
    • int isFull(CircularQueue queue):判断循环队列是否已满。其中 queue 表示循环队列。如果循环队列已满则返回 1,否则返回 0。
    • int enQueue(CircularQueue *queue, int ele):将元素入队。其中 queue 表示循环队列;ele 表示待入队的元素。如果循环队列已满则不能入队,返回 0 表示入队失败;否则如果入队成功则返回 1。
    • int deQueue(CircularQueue *queue, int *ele):将元素出队。其中 queue 表示循环队列;ele 用来保存出队的元素。如果循环队列为空则不能出队,返回 0 表示出队失败;否则如果出队成功则返回 1。
    • int size(CircularQueue queue) :获取循环队列中的元素个数。其中 queue 表示循环队列。返回循环队列中的元素个数。
    • int getFront(CircularQueue queue, int *ele):读取循环队列中的队头元素。其中 queue 表示循环队列;ele 用来保存队头的元素。如果队列为空则无法获取队头元素则返回 0,否则返回 1。
    • int getRear(CircularQueue queue, int *ele):读取循环队列中的队尾元素。其中 queue 表示循环队列;ele 用来保存队尾的元素。如果队列为空则无法获取队尾元素则返回 0,否则返回 1。
    • void clear(CircularQueue *queue):清空循环队列中所有元素。其中 queue 表示循环队列。
    • void print(CircularQueue queue):打印循环队列中所有元素。其中 queue 表示循环队列。

    init

    初始化循环队列。

    在这里插入图片描述

    实现步骤:

    • 将队头指针 front 和队尾指针 rear 都指向 0,表示空队列。

    实现代码如下:

    /**
     * 初始化循环队列
     * @param queue 待初始化的循环队列
     */
    void init(CircularQueue *queue) {
        // 循环队列初始时,队头指针和队尾指针仍然都指向 0,表示是空队列
        queue->front = 0;
        queue->rear = 0;
    }
    

    isEmpty

    判断循环队列是否为空。如果为空则返回 1,否则返回 0 表示非空。

    在这里插入图片描述

    实现步骤:

    • 判断队头指针 front 和队尾指针 rear 是否指向同一位置,即 queue.front==queue.rear

    实现代码如下:

    /**
     * 判断循环队列是否为空
     * @param queue 循环队列
     * @return 如果循环队列为空则返回 1,否则返回 0 表示非空
     */
    int isEmpty(CircularQueue queue) {
        // 只要队头指针和队尾指针相等,那么表示循环队列为空,无论指针在哪个位置
        if (queue.rear == queue.front) {
            return 1;
        } else {
            return 0;
        }
    }
    

    isFull

    判断循环队列是否已经满队。如果已满则返回 1,否则返回 0 表示未满。

    在这里插入图片描述

    实现步骤:

    • 如果满足条件 (queue.rear+1)%MAXSIZE==queue.front,那么就认为队满。

    实现代码如下:

    /**
     * 判断循环队列是否已满
     * @param queue 循环队列
     * @return 如果循环队列已满则返回 1,否则返回 0 表示队列非满
     */
    int isFull(CircularQueue queue) {
        // 队尾指针再加上一,然后对 MAXSIZE 取余,如果等于队头指针,那么表示队满
        if ((queue.rear + 1) % MAXSIZE == queue.front) {
            return 1;
        } else {
            return 0;
        }
    }
    

    enQueue

    将元素入队。如果队未满才能入队,否则返回 0 表示入队失败。如果入队成功则返回 1。以 queue=[a, b, c]; ele=x 为例如图:

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果队满则不能入队。返回 0 表示入队失败。
    • 先进行赋值,将队尾指针所指向的位置赋予 ele 值。
    • 接着队尾指针加一,指向队尾元素的下一个位置。保证队尾指针始终指向队尾元素的下一位置。
    • 返回 1 表示入队成功。

    实现代码如下:

    /**
     * 将元素入队
     * @param queue 循环队列
     * @param ele 指定元素
     * @return 如果队列已满则不能入队返回 0 表示入队失败;否则返回 1 表示入队成功
     */
    int enQueue(CircularQueue *queue, int ele) {
        // 0.参数校验,如果队满则不能入队
        if ((queue->rear + 1) % MAXSIZE == queue->front) {
            return 0;
        }
        // 1.将元素入队
        // 1.1 先进行赋值,即将新元素填充到队尾指针指向的位置。因为队尾指针指向队尾元素的下一个位置
        queue->data[queue->rear] = ele;
        // 1.2 然后将队尾指针加一。因为是循环队列,如果到了队尾,那么又要从 0 开始,所以加一后需要对 MAXSIZE 进行取余
        queue->rear = (queue->rear + 1) % MAXSIZE;
        return 1;
    }
    

    deQueue

    将元素出队。如果队空则不能出队,返回 0 表示出队失败。将出队元素保存到 ele,并返回 1 表示出队成功。以 queue=[a, b, c, d, e, f, g] 为例如图所示:

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果队空,则不能出队。返回 0 表示出队失败。
    • 将元素出队。用 ele 保存队头指针所指向的元素。
    • 然后将队头指针加一,保证队头指针始终指向队头元素。
    • 返回 1 表示出队成功。

    实现代码如下:

    /**
     * 将元素出队
     * @param queue 循环队列
     * @param ele 用来保存出队的元素
     * @return 如果队空则不能出队则将返回 0 表示出队失败;否则返回 1 表示出队成功
     */
    int deQueue(CircularQueue *queue, int *ele) {
        // 0.参数校验,如果队空则不能出队
        if (queue->rear == queue->front) {
            return 0;
        }
        // 1.将队头元素出队
        // 1.1 用 ele 保存队头指针所指向的元素
        *ele = queue->data[queue->front];
        // 1.2 将队头指针加一,表示删除队头元素。因为是循环队列,所以要对 MAXSIZE 取余
        queue->front = (queue->front + 1) % MAXSIZE;
        // 1.3 返回 1 表示出队成功
        return 1;
    }
    

    size

    获取循环队列中实际的元素个数。

    在这里插入图片描述

    实现步骤:

    • 循环队列的元素个数即 (rear-front+MAXSIZE)%MAXISZE

    实现代码如下:

    /**
     * 获取循环队列中的元素个数
     * @param queue 循环队列
     * @return 队列中的元素个数
     */
    int size(CircularQueue queue) {
        // 如果是顺序队列,则元素个数是 rear-front
        // 如果是循环队列,则元素个数是 (rear-front+MAXSIZE)%MAXSIZE
        return (queue.rear - queue.front + MAXSIZE) % MAXSIZE;
    }
    

    getFront

    读取队头元素,但并不出队。如果队空则不能读取,则返回 0,否则用 ele 保存队头元素,返回 1 表示读取成功。

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果队空则没有队头元素,自然也无法获取。返回 0 表示读取失败。
    • 直接读取队头指针所指向的元素。因为队头指针始终指向队头元素。

    实现代码如下:

    /**
     * 获取循环队列的队头元素
     * @param queue 循环队列
     * @param ele 用来保存队头元素
     * @return 如果队列为空则返回 0 表示获取失败;否则返回 1 表示获取成功。
     */
    int getFront(CircularQueue queue, int *ele) {
        // 0.参数校验,如果队列为空则没有队头元素,自然无法获取,所以返回 0 表示获取失败
        if (queue.rear == queue.front) {
            return 0;
        }
        // 1.用 ele 保存队头元素,即队头指针所指向的元素
        *ele = queue.data[queue.front];
        return 1;
    }
    

    getRear

    读取循环队列的队尾元素。如果循环队空为空则返回 0 表示读取失败。否则用 ele 保存队尾元素,并返回 1 读取成功。

    在这里插入图片描述

    实现步骤:

    • 参数校验,如果队空,则不能读取队尾元素。返回 0 表示读取失败。
    • 读取队尾指针所指向位置的前一个位置的元素,用 ele 保存。因为队尾指针始终指向队尾元素的下一个位置,所以要读取队尾元素,需要读取到队尾指针的前一个位置的元素。但并不是队尾指针单纯的减一,因为是循环队列。
    • 返回 1 表示读取成功。

    实现代码如下:

    /**
     * 获取循环队列中的队尾元素
     * @param queue 循环队列
     * @param ele 用来保存队尾元素
     * @return 如果队列为空则返回 0 表示获取失败;否则返回 1 表示获取成功。
     */
    int getRear(CircularQueue queue, int *ele) {
        // 0.参数校验,如果队列为空则没有队尾元素,自然无法获取,所以返回 0 表示获取失败
        if (queue.rear == queue.front) {
            return 0;
        }
        // 1.用 ele 保存队尾元素,由于队尾指针指向队尾元素的下一个位置,所以要队尾指针减一
        *ele = queue.data[(queue.rear - 1 + MAXSIZE) % MAXSIZE];
        return 1;
    }
    
    

    clear

    清空循环队列。

    在这里插入图片描述

    实现步骤:

    • 将双端队列的队头指针 front 和队尾指针 rear 都指向 0,表示空队列。但实际上队列中原有的元素仍然存在,并没有被重置为某个值。

    实现代码如下:

    /**
     * 清空循环队列
     * @param queue 循环队列
     */
    void clear(CircularQueue *queue) {
        // 即将队头指针和队尾指针都指向 0,表示恢复循环队列的初始状态,即空表
        queue->front = 0;
        queue->rear = 0;
    }
    

    print

    打印循环队列中的所有有效元素。

    在这里插入图片描述

    实现步骤:

    • 从队头指针开始扫描整个循环队列,直到队尾指针结束,但不包括队尾指针所指向的元素。

    实现代码如下:

    /**
     * 打印循环队列中从队头到队尾的所有元素
     * @param queue 循环队列
     */
    void print(CircularQueue queue) {
        printf("[");
        int front = queue.front;
        while (front != queue.rear) {
            printf("%d", queue.data[front]);
            if (front != (queue.rear - 1 + MAXSIZE) % MAXSIZE) {
                printf(", ");
            }
            front = (front + 1) % MAXSIZE;
        }
        printf("]\n");
    }
    

    注意事项

    无。

    练习题

    展开全文
  • 描述了C语言环境下循环队列的初始化以及所有常见的函数,包括入队出队对队列进行统计等等,对学习和理解循环队列,了解数据结构具有很大的作用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 270,699
精华内容 108,279
热门标签
关键字:

循环队列属于什么结构