精华内容
下载资源
问答
  • 队列的顺序存储结构和基本定义的实现 #include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct { ElemType data[MaxSize]; int front,rear; //队首...

         环形队列的存储结构和基本定义的实现

          为了能够充分地使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为环形队列或循环队列。

           用rear==MaxSize-1作为队满的条件有缺陷。可能队列为空,但仍满足该条件。这时进队时出现“上溢出”,这种溢出并不是真正的溢出,在data数组中存在可以存放元素的空位置,所以这是一种假溢出。

           在顺序队列中,由于产生了队满上溢出和队空下溢出,使得这两种假溢出影响了队列存储元素的过程,因此,采用环形队列将其进行改进。

    环形队列的四要素

    • 队空条件:front=rear
    • 队满条件:(rear+1)%MaxSize=front
    • 进队e操作:rear=(rear+1)%MaxSize; 将e放在rear处
    • 出队操作:front=(front+1)%MaxSize;取出front处元素e;

    环形队列的进队出队示意图

    #include <stdio.h>
    #include <malloc.h>
    #define MaxSize 100
    typedef char ElemType;
    typedef struct 
    {	
    	ElemType data[MaxSize];
    	int front,rear;		//队首和队尾指针
    } ClQueue;
    void InitQueue(ClQueue *&q)
    {	q=(ClQueue *)malloc (sizeof(ClQueue));
    	q->front=q->rear=0;
    }
    void DestroyQueue(ClQueue *&q)
    {
    	free(q);
    }
    bool QueueEmpty(ClQueue *q)
    {
    	return(q->front==q->rear);
    }
    bool enQueue(ClQueue *&q,ElemType e)
    {	if ((q->rear+1)%MaxSize==q->front)	//队满上溢出
    		return false;
    	q->rear=(q->rear+1)%MaxSize;
    	q->data[q->rear]=e;
    	return true;
    }
    bool deQueue(ClQueue *&q,ElemType &e)
    {	if (q->front==q->rear)		//队空下溢出
    		return false;
    	q->front=(q->front+1)%MaxSize;
    	e=q->data[q->front];
    	return true;
    }

     

    展开全文
  • 队列是一种“先进先出”(FIFO)的数据结构,队列有两端,一边只进,一边只出,即:数据从尾部进入,从头部出来,先进去的就会先出来,就像我们平时食堂打饭排队一样,先去排的先打到饭,后去排的后打到饭。...

    队列是一种“先进先出”(FIFO)的数据结构,队列有两端,一边只进,一边只出,即:数据从尾部进入,从头部出来,先进去的就会先出来,就像我们平时食堂打饭排队一样,先去排的先打到饭,后去排的后打到饭。

    队列通常可以用数组或者是链表实现。这里以数组举例,假设这儿有一个长度为5的数组,左端为头部,负责取出数据,右端为尾部,负责存入数据。

    从尾部加入数据A

    再从尾部加入数据B

    再从尾部加入数据C

    从头部取出数据A

    再从尾部加入数据D

    再从头部取出数据B

    再从尾部加入数据E

    这时加入数据F却失败了,可是数组的前两个位置明明就是空的,但是却由于数组的最后一个位置有数据导致新数据无法正常加入,这种情况就是“假溢出”。

    有人肯定会说,数组中的数据向前移动两位不久可以了吗?这确实可以,但是如果数组的长度很长,那么需要移动的数据量就会非常大,既消耗时间,又消耗性能,所以这种方法不太好。我这里介绍另外一种解决队列“假溢出”问题的方法:环形队列

    环形队列就是将顺序队列首尾相连形成环形结构的队列,这样环形结构的好处就是:只要队列没有真正的满,永远不会溢出

    比如上述顺序队列中的例子,若首位相连,那么F就会放到数组的第一个位置上去

    下面我使用Python的列表结构实现了该环形队列

    注意:环形队列在数据结构上它是一个环形结构,但是在本质上,它还是一个数组(Python中的列表)。

    用两个指针分别指向队列的头部(front)和尾部(rear),front和real初始值为-1,若每存入一个数据,则rear加一,若每取出一个数据,则front加一,当rear等于front的时候,表示队列为空,当rear和front之间的差值等于数组长度的时候,表示队列已满。

    具体实现如下(有详细注释):

    class CircularQueue:
        """环形队列"""
        def __init__(self):
            """初始化,定义队列容量,定义队列头部指针(front)和尾部指针(rear)"""
            self.max_queue = 5
            self.queue = [None] * self.max_queue
            self.front = self.rear = -1
    
        def is_empty(self):
            """判断队列是否为空"""
            if self.front == self.rear:
                return True
            else:
                return False
    
        def is_full(self):
            """判断队列是否已满"""
            if self.rear - self.front == self.max_queue:  # 用尾部指针和头部指针的距离来判断队列是否已满
                return True
            else:
                return False
    
        def enter_queue(self, data):
            """向队列中加入数据"""
            if self.is_full():  # 队列已满就不能加入数据
                print("队列已满,无法再加入")
            else:
                self.rear += 1  # 尾部指针向后移动一位
                data_index = (self.rear + 1) % self.max_queue - 1  # 根据尾部指针计算出新加入的数据应该在列表的哪个位置(索引)
                if data_index == -1:  # 如果data_index == -1,说明该新加入的数据应该在列表的最后一个索引位置
                    data_index = self.max_queue - 1  # 计算出列表的最后一个索引位置
                self.queue[data_index] = data  # 将数据放入队列(列表)中
                print("加入队列成功")
    
        def del_queue(self):
            """从队列中取出数据"""
            if self.is_empty():  # 队列已空就不能再取出数据了
                print("队列已空,无法再删除")
            else:
                self.front += 1  # 头部指针向后移动一位
                data_index = self.front % 5  # 计算出需要取出的数据所在列表中的索引位置
                data = self.queue[data_index]  # 拿到该数据
                print("取出数据:", data)
                self.queue[data_index] = None  # 取出后将队列(列表中的该位置重置为None)
    
        def show(self):
            """展示队列"""
            if self.is_empty():
                print("队列为空,无法显示")
                return
            num = 0  # 该变量用来计数,表示拿到第几个数据了
            while True:
                num += 1
                data_index = (self.front + num) % 5  # 获取当前数据索引
                data = self.queue[data_index]  # 拿到数据
                print(data, end=' ')
                if self.front + num == self.rear:  # 当前情况表示已经拿完了队列中的最后一个数据,所以要跳出循环
                    break
            print()
    
    
    if __name__ == '__main__':
        cir_queue = CircularQueue()
        while True:
            num = input("1.存入队列   2.取出队列   3.查看队列   4.退出\n请输入:")
            if num == '1':
                try:
                    data = int(input("输入存入数据:"))
                except ValueError:
                    print("输入数据错误")
                    continue
                cir_queue.enter_queue(data)
            elif num == '2':
                cir_queue.del_queue()
            elif num == '3':
                cir_queue.show()
            elif num == '4':
                print("成功退出")
                break
            else:
                print("输入选项错误,请重新输入")
    

    部分运行结果如下:

    展开全文
  • 环形队列的数组实现

    2020-05-03 16:45:42
    数据结构和算法不扎实,做啥程序员!学习搞起~~~ ... * 环形队列解决了数组队列假溢出,不能重复使用的问题 * front队首下标 * rear 队尾的后一个元素的下标 * 当front=0,rear指向最后一格空间时,rea...

    数据结构和算法不扎实,做啥程序员!学习搞起~~~

    这里有一篇图文并茂的文章写的很好,大家可以学习哈!
    数据结构 第7讲 循环队列

    java代码实现

    package com.base;
    
    /**
     * 环形队列的数组实现
     * 环形队列解决了数组队列假溢出,不能重复使用的问题
     * front队首下标
     * rear 队尾的后一个元素的下标
     * 当front=0,rear指向最后一格空间时,rear+1刚好等于maxSize
     */
    public class circleArrayList {
        private int front;
        private int rear;
        private int maxSize;
        private int[] arr;
    
        // 初始化
        public circleArrayList(int size) {
            this.maxSize = size;
            this.arr = new int[size];
            front = rear = 0;
        }
    
        // 判断队列是否已满
        public boolean isFull() {
            //  当(rear+1) % maxSize == front时,对列满了。之所以要%,是为了防止索引越界,让rear的取值又从0-(maxSize-1)开始实现循环
            if ((rear + 1) % maxSize == front) {
                System.out.println("队列已满,不能添加元素");
                return true;
            }
            return false;
        }
    
        // 查看队列所有元素
        public void listAll() {
            for (int i = front; i < front + size(); i++) {
                System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
            }
    
        }
    
        // 队列元素的个数(rear-front+maxSieze)%maxSize
        public int size() {
            return (rear - front + maxSize) % maxSize;
        }
    
        // 入队,在队尾加元素
        public void enq(int n) {
            // 如果队列已满,退出方法
            if (isFull()) {
                return;
            }
            arr[rear] = n;
            this.rear = (rear + 1) % maxSize;
        }
    
        // 出队,从队首取元素
        public int deq() {
            // 如果队列为空,则抛出异常
            if (front == rear) {
                throw new RuntimeException("队列为空");
            }
            int temp = arr[front];
            front++;
            return temp;
        }
    
    }
    

    测试代码

    package com.base;
    
    import java.util.Scanner;
    
    public class test {
        public static void main(String[] args) {
            circleArrayList queue = new circleArrayList(3);
            Scanner scanner = new Scanner(System.in);
            boolean loop = true;
            while (loop) {
                System.out.println("s:显示队列");
                System.out.println("e:退出程序");
                System.out.println("a:添加元素");
                System.out.println("g:取出一个元素");
                char key = scanner.next().charAt(0);
                switch (key) {
                    case 's':
                        queue.listAll();
                        break;
                    case 'a':
                        if (queue.isFull()) break;
                        System.out.println("输入一个数");
                        int i = scanner.nextInt();
                        queue.enq(i);
                        break;
                    case 'g':
                        try {
                            int deq = queue.deq();
                            System.out.printf("取出来的数是%d\n", deq);
                        } catch (Exception e) {
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e':
                        scanner.close();
                        loop = false;
                        break;
                    default:
                        break;
                }
            }
        }
    }
    

    如果不想看书的话,b站上的视频也不错哦!尚硅谷的韩老师讲的通俗易懂,话不多说,搞起来~~
    数据结构与算法-韩顺平

    展开全文
  • 环形队列的定义 在顺序队列的操作中,有时会发生假溢出的情况。假溢出就是队尾指针rear已经指向了data数组的最大下标,而另一端还有剩下空位置。为了解决这种问题,可以把数组的前端和后端连接起来,形成一个环形...

    环形队列的定义

    在顺序队列的操作中,有时会发生假溢出的情况。假溢出就是队尾指针rear已经指向了data数组的最大下标,而另一端还有剩下空位置。为了解决这种问题,可以把数组的前端和后端连接起来,形成一个环形数组,我们就称之为环形队列。

    顺序队列的假溢出

    在这里插入图片描述
    如上图所示,讲一个顺序队列添加元素至队满,然后再进行两次出队操作,这时队列中还有两个空余的位置,但是却无法再加入新的元素,这就是假溢出。

    环形队列的表述

    在这里插入图片描述
    环形队列就是如上图一样的环状队列,这就是一个MaxSize=8的空队。

    环形队列的实现思路

    1.front与rear指针

    front指针:front直接指向队列的第一个元素,初始值=0。
    rear指针:rear指向队列的最后一个元素的后一个位置,因为这样我们可以空出一个位置。初始值=0。
    为什么要空出一个位置?
    这个是根据需求来的,入队时尾指针追赶头指针;出队时头指针追赶尾指针,造成队空和队满时头尾指针均相等,这样就不能用front==rear来判断队列是"空"还是"满",所以才空出一个位置,使“空”和“满”能够区分开。

    2.判断队空

    因为入队与出队front与rear会分别增加,所以当front指针与rear指针相等时,入队数就与出队数相等,就是空队列。条件为front==rear

    3.判断队满

    判断队满就稍微复杂一点,因为它是环形的,会有复用,rear指针是有可能指向队的前面来的,所以它要取模才能准确的判断是否为满。条件为(rear + 1) % maxSize == front。rear+1是因为当队满的时候,rear与front是紧挨着的所以加1。

    4.size的值

    有效元素个数的算法为:(rear + maxSize - front) % maxSize,因为是环形的,rear是有可能走到front前面的,所以需要先加上maxSize,以防止rear-front是一个负数,然后在取模,就可以得到有效元素的个数。

    代码的实现

    1.定义变量与初始化
        private int maxSize;
        private int front;
        private int rear;
        private int[] arr;
    
        public Queue(int maxS){
            maxSize = maxS;
            arr = new int[maxSize];
            front = 0;
            rear = 0;
        }
    
    2.判空与判满
        public boolean isFull(){
            return (rear + 1) % maxSize == front;
        }
    
        public boolean isEmpty(){
            return rear == front;
        }
    
    3.添加数据
        public void addData(int n){
            if (isFull()){
                System.out.println("队列已满。。。");
                return;
            }
            arr[rear] = n;
            rear = (rear + 1) % maxSize;
        }
    
    4.取出数据
        public int getData(){
            if (isEmpty()){
                throw new RuntimeException("队列为空,无法取出数据。。。");
            }
            int a = arr[front];
            front = (front + 1) % maxSize;
            return a;
        }
    
    5.有效元素个数
        public int size(){
            return (rear + maxSize - front) % maxSize;
        }
    
    5.显示所有数据
    public void showData(){
            if (isEmpty()){
                System.out.println("队列为空。。。");
            }
            for (int i= front; i<front + size();i++){
                System.out.println(arr[i % maxSize]);
            }
        }
    

    注:因为有一个位置要空着的,所以当maxsize为5时,一共只有4个位置可用,以此类推。

    展开全文
  • java数据结构——环形队列

    千次阅读 2018-09-24 11:11:32
    这时候环形队列就解决了这样的一个问题,环形队列的front指针始终指向当前队列的最后位置;end指针始终指向第一个元素的前一个位置为-1,存储元素的时候头部和尾部都可以相互移动,而不必造成假溢出现象,节省了内存...
  • 队列: 1.只允许在一端进行插入数据操作...由于顺序队列在操作上有诸多不便,(出队列时,要进行元素的搬移,效率低下,还会出现假溢出的问题)在此我们可以创建循环的顺序队列,即环形队列环形队列的实现:
  • 避免假溢出现象(由于入队和出队的操作,头尾指针只增加不减少,致使被删元素的空间永远无法重新利用,当队列继续存储元素时,出现尾指针已经到达了队列尾,而实际头指针前面并未满的情况),可以将队列空间充
  • C++实现环形队列

    2020-10-29 14:44:05
    实现环形队列 线性队列原理图: 假设是长度为5的数组,初始状态,空队列如所示,front与 rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4, front指针依然指向下标为0位置,而rear指针指向下标为4的位置。 出...
  • 这篇写的是环形队列,上一篇顺序队列中也提到了,环形队列设计的初衷就是为了解决假溢出问题,那他是如何成为环形的呢?换句话说,指针是怎么从数组的后面回到前面来的呢?取余,环形队列的核心就是取余。 back=...
  • 数组模拟环形队列

    2021-06-12 13:37:39
    使用数组实现队列的顺序存储时会出现假溢出情况,使用循环队列可以解决这一问题。 初始时:front=rear; 队列头部改变:front=(front+1)%MaxSize; 队列尾部改变:rear=(rear+1)%MaxSize; 队列长度:(rear+...
  • 环形队列

    2017-09-23 13:46:00
    在网上看到一篇比较好的介绍队列的文章,地址为:http://www.cnblogs.com/kubixuesheng/p/4104802.html 特此感谢原创作者,以下均为摘抄。 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~...1、顺序队列 限制仅...
  • java中用数组实现环形队列 本篇文章主要讲述了使用数组实现环形队列的思路以及具体代码 一、队列是什么 我们先来看下百度百科的解释: 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除...
  • 1.因为实现队列时,当rear=maxsize-1时,队列中还有空位置,当因为队满条件设置不合理,而队列还有空位置的情况叫”假溢出“,而解决办法则是把前端和后端连接起来,变成一个环形队列,而首尾相连后,rear=maxzise-1...
  • /*循环队列*/ #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define MAX_QUEUE_CYCLE_SIZE 10 typedef struct queue_cycle{ int *base; //保存数组基地址 int f; int r; int queue_...
  • 环形队列_JAVA

    2019-09-06 20:52:24
    普通顺序队列存在的问题 ...尾指针rear已指到数组的最后有一个元素,即rear==MaxLen-1,此时若再数组的前面部分可能还有很多闲置空间,即这种溢出并非是真的没有可用的存储空间,故称这种溢出现象...
  • 【数据结构】环形队列的基本操作

    千次阅读 2018-09-24 17:01:28
    ####为了解决顺序队列的假溢出的问题,设计了环形队列 #pragma once #include &lt;assert.h&gt; #include &lt;stdio.h&gt; #define MAX_SIZE 8 typedef int DataType; typedef struct Queue { ...
  • 队列 该文是观看尚硅谷韩老师视频学习自己总结学习得,有的是来源于网络收集 队列引入 进的一端称为队尾(rear),出的一端称为队头(front)。队列可以用顺序存储,也可以用链式存储。 队列介绍 队列是一个**有序...
  • 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,队列是一种操作受限制的线性表,队列又称为先进先出(FIFO—first in first out)线性表。...
  • 实现环形队列各种基本运算的算法

    千次阅读 2019-01-15 14:15:35
    * 领会环形队列存储结构和掌握环形队列中各种基本运算算法设计 * 主要功能: * 1、初始化队列q * 2、判断队列q是否非空 * 3、依次进队元素a、b、c * 4、出队一个元素,输出该元素 * 5、依次进队元素d、e、f * 6、输出...
  • 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队...
  • 目录前言:环形队列代码分析如下:判断队列是否为空判断队列是否已满添加元素取出元素显示所有元素显示头数据显示尾数据源代码如下博主目前水平还有待提高,如果有更优解,欢迎评论区留言呦 前言: 本篇博客实在上一...
  • 在上篇《队列的C++实现》中已经介绍了一种假溢出的解决方案:当数据出队时,将数据整体向前移动,这样就会不会出现假溢出。 另一种方案是:将数组看成循环的,这样的话,即使尾端数据已经塞满,但是由于结构是循环...
  • 文章目录前言一、环形队列二、使用步骤1.引入库2.读入数据总结 前言 在上节课的学习中,使用数组实现了单向队列,单向队列不能复用,环形队列可以解决这个问题。 一、环形队列 示例:pandas 是基于NumPy 的一种...
  • 数据结构之环形队列

    2021-07-07 21:52:44
    队列是一种具有先进先出(FIFO)的数据类型,可以使用多种数据结构来实现队列:数组和链表。
  • 队列(Queue) 介绍 队列是一种有序列表,只允许对队尾(rear)进行删除操作,对队首(front)进行删除操作,即先入先出(FIFO)。 实现队列需要的内部元素 元素 含义 maxSize 代表能够存储的数据的个数 front ...
  • 队列是对头出、队尾入的先进先出线性表。 需要两个指针front和rear分别来指向队头和队尾。 front指向队头的前一个位置,rear总是指向队尾元素。 队空条件:front=rear 队满条件:rear = MaxSize - 1 进队:...
  • 顺序环形队列存储结构中的基本运算有如下几项: 1、初始化顺序环形结构  令front=rear=0 。 2、销毁顺序环形队列  用free()将其释放 。 3、判断顺序环形队列是否为空  通过front==rear 判断队列是否为空 ...
  • 队列使用front和rear两个指针分别指向队列的前端和末尾。 1.2 队列的基本操作 特性 ① 先进先出; ② 两种基本操作:加入与删除,而且使用front和rear两个指针分别指向队列的前端和末尾。 基本运算 ① Create:创建...
  • //返回 q->rear++; //队尾增1 q->data[q->rear]=e; //rear位置插入元素e return true; //返回真 } bool deQueue(SqQueue *&q,ElemType &e) //出队 { if (q->front==q->rear) //队空下溢出 return false; q->front...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 809
精华内容 323
关键字:

环形队列假溢出