精华内容
下载资源
问答
  • 队列,循环队列为什么用空一个元素的位置 队列介绍 1)队列是一个有序列表,可以用数组或是链表表示。 2)遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出。 front及rear分别记录队列前后端...

    队列,循环队列为什么用空一个元素的位置

    队列介绍

    1)队列是一个有序列表,可以用数组或是链表表示。

    2)遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出。

    • front及rear分别记录队列前后端的下标,front随着数据的输出而改变,而rear则是随着数据输入而改变。
    image-20200708160054824

    代码实现

    import java.util.Scanner;
    
    public class ArrayQueueDemo {
        public static void main(String[] args) {
            //创建一个队列
            ArrayQueue arrayQueue = new ArrayQueue(3);
            char key = ' ';//接受用户输入
            Scanner scanner = new Scanner(System.in);
            boolean loop = true;
            //输出一个菜单
            while(loop){
                System.out.println("s(show):显示队列");
                System.out.println("e(exit):退出程序");
                System.out.println("a(add):添加数据到队列");
                System.out.println("g(get):从队列取出数据");
                System.out.println("h(head):查看队列头的数据");
                key = scanner.next().charAt(0);
                switch (key){
                    case 's':
                        arrayQueue.showQueue();
                        break;
                    case 'a':
                        System.out.println("请输入一个数字:");
                        int value = scanner.nextInt();
                        arrayQueue.addQueue(value);
                        break;
                    case 'g':
                        try {
                            int res = arrayQueue.getQueue();
                            System.out.println("取出数据:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h':
                        try {
                            int res = arrayQueue.headQueue();
                            System.out.println("队列头数据:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e':
                        scanner.close();
                        loop = false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出");
        }
    }
    
    class ArrayQueue{
        private int maxSize;
        private int front;
        private int rear;
        private int[] arr;//模拟队列,该数组用于存放数据
    
        //创建队列的构造器
        public ArrayQueue(int arrMaxSize){
            maxSize = arrMaxSize;
            arr = new int[maxSize];
            front = -1;//指向队列头部(第一个数据的前面)
            rear = -1;//指向队列尾部(最后一个数据)
        }
        //判断队列是否满
        public boolean isFull(){
            return rear == maxSize-1;
        }
        //判断队列是够为空
        public boolean isEmpty(){
            return front==rear;
        }
        //添加数据到队列
        public void addQueue(int n){
            if(isFull()){
                System.out.println("队列已满,不可加入数据");
                return;
            }
            rear++;
            arr[rear] = n;
        }
        //从队列中取出数据
        public int getQueue(){
            if(isEmpty()){
                throw new RuntimeException("队列为空,不可取出数据");
            }
            front++;
            return arr[front];
        }
        //显示队列的中的所有数据
        public void showQueue(){
            if(isEmpty()){
                System.out.println("队列为空");
                return;
            }
            for (int i = 0; i <arr.length ; i++) {
                System.out.print(i+":"+ arr[i]+"\n");
            }
        }
        //显示队列的头数据,不是取出数据
        public  int headQueue(){
            if(isEmpty()){
                System.out.println("队列为空");
                throw new RuntimeException("队列为空");
            }
            return arr[front+1];
        }
    }
    
    

    问题分析并优化:

    • 目前数组使用了一次就不能用了,没有达到复用的效果

    • 我们要使用算法,将目前的数组改成一个环形的队列 取模%

    数组环形队列思路:

    1、front变量的含义做一个调整:front就指向队列的第一个元素,就是是说arr[front]就是队列的第一个元素,front初始值为0;

    2、rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置,rear的初始值为0;

    3、队列满的条件:(rear+1)%maxSize ==front

    4、队列空的条件是:rear == front

    5、此时队列的有效长度是: (rear+maxSize-front)%maxSize

    遇到的问题(循环队列空一个元素的位置)

    在得到队列满的条件:(rear+1)%maxSize ==front时,我充满了疑惑,怎么算都觉得在rear已经表示最后元素的后一位了,这种情况下加一肯定是不对的,后来我查了一些资料。
    别人规定的循环队列

    那么,循环队列为什么用空一个元素的位置呢???

    这个是根据需要来用的
    循环队列中,由于入队时尾指du针向前追赶头指针;zhi出队时头指针向前追赶尾指针,造成dao队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是"空"还是"满"。
    解决这个问题的方法至少有三种:
    ①另设一布尔变量以区别队列的空和满;
    ②少用一个元素的空间。约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:rear所指的单元始终为空);
    ③使用一个计数器记录队列中元素的总数(即队列长度)。

    代码实现(循环队列)

    import java.util.Scanner;
    
    public class CicleArrayQueueDemo {
        public static void main(String[] args) {
    
            System.out.println("测试数组模拟环形数据");
            CircleArray queue = new CircleArray(4);//空出一个位置,其队列有效数据为3;
            char key = ' ';
            Scanner scanner = new Scanner(System.in);
            boolean loop = true;
            while(loop){
                System.out.println("s(show):显示队列");
                System.out.println("e(exit):退出程序");
                System.out.println("a(add):添加数据到队列");
                System.out.println("g(get):从队列取出数据");
                System.out.println("h(head):查看队列头的数据");
                key = scanner.next().charAt(0);
                switch (key){
                    case 's':
                        queue.showQueue();
                        break;
                    case 'a':
                        System.out.println("请输入一个数字:");
                        int value = scanner.nextInt();
                        queue.addQueue(value);
                        break;
                    case 'g':
                        try {
                            int res = queue.getQueue();
                            System.out.println("取出数据:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h':
                        try {
                            int res = queue.headQueue();
                            System.out.println("队列头数据:"+res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e':
                        scanner.close();
                        loop = false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出");
    
        }
    
        static class CircleArray{
            private int maxSize;
            private int front;//front就指向队列的第一个元素,就是是说arr[front]就是队列的第一个元素,front初始值为0;
            private int rear;//rear指向队列的最后一个元素的后一个位置,rear的初始值为0;
            private int[] arr;//模拟队列,该数组用于存放数据
    
            public CircleArray(int arrMaxSize){
                maxSize = arrMaxSize;
                arr = new int[maxSize];
            }
    
            //判断队列是否满
            public boolean isFull(){
                return (rear + 1)%maxSize ==front;
            }
            //判断队列是够为空
            public boolean isEmpty(){
                return front==rear;
            }
            //添加数据到队列
            public void addQueue(int n){
                if(isFull()){
                    System.out.println("队列已满,不可加入数据");
                    return;
                }
                arr[rear] = n;
                rear = (rear+1)%maxSize;
            }
            //从队列中取出数据
            public int getQueue(){
                if(isEmpty()){
                    throw new RuntimeException("队列为空,不可取出数据");
                }
                int value = arr[front];
                front = (front+1) % maxSize;
                return value;
            }
            //求出当前队列的个数
            public int arrCount(){
                return (rear+maxSize-front)%maxSize;
            }
            //显示队列的中的所有数据
            public void showQueue(){
                if(isEmpty()){
                    System.out.println("队列为空");
                    return;
                }
                for (int i = front; i <front+arrCount(); i++) {
                    System.out.print((i%maxSize)+":"+ arr[i%maxSize]+"\n");
                }
            }
            //显示队列的头数据,不是取出数据
            public  int headQueue(){
                if(isEmpty()){
                    System.out.println("队列为空");
                    throw new RuntimeException("队列为空");
                }
                return arr[front];
            }
    
        }
    }
    
    展开全文
  • 循环队列元素个

    万次阅读 多人点赞 2017-06-17 08:30:14
    1. 设有一个用数组Q[1..m]表示的环形队列,约定f为当前队头元素在数组中的位置,r为队尾元素的后一位置(按顺时针方向),若队列非空,则计算队列元素个数的公式应为() A、 (m+r-f)mod m B、 r-f C、 (m-r-f)...

    1. 设有一个用数组Q[1..m]表示的环形队列,约定f为当前队头元素在数组中的位置,r为队尾元素的后一位置(按顺时针方向),若队列非空,则计算队列中元素个数的公式应为()

     

    A、  (m+r-f)mod m

    B、  r-f

    C、  (m-r-f)mod m

    D、  (m-r+f)mod m

     

    答案为: A 

    分析: 

     

          对于顺序队列,头指针和尾指针开始时刻都指向数组的0下标元素。当加入新元素以后,尾指针向后移动,指向最后一个元素的下一个位置。

    但是尾指针不能超过数组的最大范围。当有元素删除时,头指针向后移动。但是头指针不能低于数组的0下标。这样就会引入一种“假溢出”现象,

    数组中存在空余的空间,但是由于尾指针已经在最大位置,不能加入元素。

        循环队列就可以用来解决 假溢出 问题, 当队列后面的满了,就从头在开始,形成头尾相接的循环. 

        出现的问题:  front=rear即头指针和尾指针相等,但是对应两种情况:一种是队列是空,一种是队列是满。

        所以,我们定义循环队列中空出一个位置为满队列状态。front指向头元素,rear指向尾元素的下一个位置。

        那么循环队列的长度如何计算呢? 

         情况一:  当rear大于front时,循环队列的长度:rear-front

        情况二:  当rear小于front时,循环队列的长度:分为两部分计算 0+rear   和   Quesize-front  ,  将两部分的长度合并到一起即为: rear-front+Quesize

     

        所以将两种情况合为一种,即为:  总长度是(rear-front+Quesize)%Quesize

     

    展开全文
  • 循环队列添加删除元素

    千次阅读 2017-11-14 10:51:11
    #include using namespace std; const int Maxsize = 12; struct QNode { int *Data; int front, rear; int Maxsize; }; typedef struct QNode * Queue; Queue CreatQueue(int Maxsize) ... Queue Q = new struct
    #include<iostream>
    using namespace std;
    const int Maxsize = 12;
    struct QNode {
    	int *Data;
    	int front, rear;
    	int Maxsize;
    };
    typedef struct QNode * Queue;
    
    Queue CreatQueue(int Maxsize)
    {
    	Queue Q = new struct QNode;
    	Q->Data = new int[Maxsize];
    	Q->front = Q->rear = 0;
    	Q->Maxsize = Maxsize;
    	return Q;
    }
    bool Isfull(Queue Q)
    {
    	return((Q->rear - 1) % (Q->Maxsize) ==Q->front);  
    }
    bool IsEmpty(Queue Q)
    {
    	return(Q->front == Q->rear);
    }
    Queue AddQ(Queue Q,int a)
    {
    	if (Isfull(Q))
    	{
    		return Q;
    	}
    	else
    	{
    		Q->rear = (Q->rear + 1) % Q->Maxsize;
    		Q->Data[Q->rear] = a;
    		return Q;
    	}
    }
    Queue Delete(Queue Q)
    {
    	if (IsEmpty(Q))
    	{
    		return Q;
    	}
    	else
    	{
    		Q->front = (Q->front + 1) % Q->Maxsize;		//front位序低,要加才能使对列减少
    		return Q;
    	}
    }
    void main()
    {
    	Queue Q;
    	Q = CreatQueue(Maxsize);
    	for (int i = 0; i < 10; i++)
    		Q->Data[i] = i;
    	Q->rear = 9;
    	Queue k = AddQ(Q, 100);
    	if (k->rear >= k->front)				//如果尾指针大于头指针,直接输出
    	{
    		for (int j = k->front; j <= k->rear; j++)
    			cout << Q->Data[j] << " ";
    	}
    	else							//如果尾指针小于头指针,线输出到Maxsize,再从头输出
    	{
    		for (int j = k->front; j <= k->Maxsize; j++)
    			cout << Q->Data[j] << " ";
    		for (int j = 0; j <= k->rear; j++)
    			cout << Q->Data[j] << " ";
    	}
    	cout << endl;
    	Queue m = Delete(Q);
    
    
    	if (m->rear >= m->front)
    	{
    		for (int j = m->front; j <= m->rear; j++)
    			cout << Q->Data[j] << " ";
    	}
    	else
    	{
    		for (int j = m->front; j <= m->Maxsize; j++)
    			cout << Q->Data[j] << " ";
    		for (int j = 0; j <= m->rear; j++)
    			cout << Q->Data[j] << " ";
    	}
    	cin.get();
    }

    展开全文
  • 结论: 某元素前方的个数 = (元素index - 首指针+ 数组长度)% 数组长度 和求元素的总数思路一样,你可以认为求当前元素的前方元素(不包含当前元素)的...尾指针指向最后插入元素的下一个位置,在我的循环队列中留一...

     

    结论:

        某元素前方的个数 = (元素index - 首指针  + 数组长度)% 数组长度

    和求元素的总数思路一样,你可以认为求当前元素的前方元素(不包含当前元素)的个数, 即为求尾指针rear = index时的元素个数,而这就是求元素总数. 

    换句话说, 我就是想知道插入index元素的时候的总数(就算有出队操作).

    尾指针指向最后插入元素的下一个位置,在我的循环队列中留一个位置用以判断队满.

     

    图示:

                              

    JAVA 实现:

    循环队列类.

    package run;
    
    public class Queue {
    	private static int MAXLen = 10;  //队列长度
    	
    	private int front ; //指向队头
    	
    	private int rear;  //指向队尾的下一个位置。
    
    	private int num; //当前元素数量
    	private Object queueList[];
    	public Queue() {
    		this(MAXLen);
    	}
    	public Queue(int MaxLen) {
    		queueList = new Object[MaxLen];
    	}
    	/**判空 */
    	public boolean isEmpty() {   
    		if(front == rear) {
    			return true;
    		}
    		return false;
    	}
    	/**判满 */
    	public boolean isFull() {  
    		if(front==(rear+1)%queueList.length) { // 0 == (2+1) % 3==0			
    			System.out.println("队列已满");
    			return true;
    		}
    		return false;
    	}
    	/**添加元素*/
    	public boolean enqueue(Object obj) {
    		if(isFull()) {	
    			return false;
    		}
    		queueList[rear]=obj;
    		System.out.println("添加的对象为:"+obj.toString());
    		rear = (rear+1)%queueList.length;
    		num ++;
    		return true;
    	}
    	/**取出头部元素   注意非空判断*/
    	public Object dequeue() {
    		if(isEmpty()){
    			return null;  
    		}	
    		Object o = queueList[front];
    		//queueList[front] =null;
            front=(front+1)%queueList.length;
            num--;
            return o;
    	}
    	/**获得队列已有元素总数*/
    	public int getNum() {
    		return num;
    	}
    	/**获取头指针*/
    	public int getFront() {
    		return front;
    	}
    	/**获取尾指针*/
    	public int getRear() {
    		return rear;
    	}
    	/**获取指定元素的前面元素总数*/
    	public int getYourFront(Object obj) {
    		int index = getYourIndex(obj);
    		if(index==-1) {
    			return 0;
    		}
    		int numbers = (index-this.front+Queue.MAXLen)% Queue.MAXLen;
    		return numbers;	
    	}
    	/**获取指点元素的下标**/
    	public int getYourIndex(Object obj) {
    		int index=getIndex(queueList,obj);
    		return index;	
    	}
    	public static int getIndex(Object[] arr, Object value) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i].equals(value)) {
                    return i;
                }
            }
            return -1;//如果未找到返回-1
        }
    
    }
    

    主函数

    package run;
    
    
    public class test {
    
    	public static void main(String[] args) {
    		Queue que = new Queue();	
        	        que.enqueue("1");
        	        que.enqueue("2");
        	        que.enqueue("3");
        	        que.enqueue("4");
        	        //队列中剩余
        	        que.enqueue("5");
        	        que.enqueue("6");
        	        que.enqueue("7");
        	        que.enqueue("8");
        	        que.enqueue("9");
        	        que.enqueue("10"); //满
        	        System.out.println("取出头对象:"+que.dequeue().toString());
    		System.out.println("取出头对象:"+que.dequeue().toString());
    		System.out.println("取出头对象:"+que.dequeue().toString());
    		System.out.println("取出头对象:"+que.dequeue().toString());
    		A a = new A();
    		a.setName("xiong");
    		a.setPassword("aaa");
    		a.setSex("222");
    		A b = new A();
    		b.setName("xiong");
    		b.setPassword("bbbbb");
    		b.setSex("222");
    		A C = new A();
    		C.setName("JJJJJJ");
    		C.setPassword("cccc");
    		C.setSex("222");
    		que.enqueue(a);
    		que.enqueue(b);
    		System.out.println("队列总数:"+que.getNum());
    		System.out.println("首指针:"+que.getFront());
    		System.out.println("尾指针:"+que.getRear());
    		//获取元素前面的位置
    		System.out.println("a对象的位置是:"+que.getYourIndex(a));
    		System.out.println("a对象前方元素个数:"+que.getYourFront(a));
    		System.out.println("b对象的位置是:"+que.getYourIndex(b));
    		System.out.println("b对象前方元素个数:"+que.getYourFront(b));
    		System.out.println("c对象的位置是:"+que.getYourIndex(C));
    		System.out.println("C对象前方元素个数:"+que.getYourFront(C));
    		System.out.println("9 的位置是"+que.getYourIndex("9"));
    		System.out.println("9对象前方元素个数:"+que.getYourFront("9"));
    	}
    
    }
    

    结果展示 

                                                     

    展开全文
  • CircularPriorityQueue:循环优先级队列结构的实现及其基本功能,例如添加和删除元素,显示第一个元素,容量和当前元素
  • 循环队列

    2017-07-10 20:25:37
    为了解决顺序队列中的“假溢出”现象,充分利用数组的存储空间,可将顺序队列的头尾相连,构成一个循环队列循环队列一般都是用数组来实现的。 在循环队列中,front和rear都是可以移动的。 当队列为空或满时,...
  • 循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。中文名循环队列外文名Circular Queue领域实现方式有关术语特点大小固定循环队列简介编辑语音循环队列就是将队列存储空间的最后...
  • 循环队列在我们传递数据的过程中经常会用到,相对于直线队列来讲,直线队列在元素出队后,头指针向后移动,导致删除元素后的空间无法在利用,当变成循环队列之后,删除元素后的空间仍然可以利用。 声明块RAM空间 ...
  • C语言实现循环队列

    2021-01-19 23:53:05
    本文实例为大家分享了C语言实现循环队列的具体代码,供大家参考,具体内容如下 注意事项: 1、循环队列,是队列的顺序...4、在每一个指针递增的表达式中,都要加上一个% MAXQUEUE已使得一次增值都在范围内。 #inclu
  • Java实现循环队列

    2021-06-05 17:30:41
    Java实现循环队列什么是循环队列循环队列...循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,称为循环队列 2.添加一个元素:(queue.rear+1) % queue.length //为什么取余? 3.删除一个元素
  • 循环队列和链式结构队列

    千次阅读 2017-02-27 13:22:04
    一、循环队列的基础知识 ...(2)当队列不为空时,front指向队列的第一个元素,rear指向队列最后一个元素的下一个位置; (3)当队列为空时,front与rear的值相等,但不一定为零; 3.循环队列入队的
  • 循环队列实现

    2019-09-12 17:23:33
    因为是尾进头出,所以和顺序栈不同的是需要将顺序队列臆造成一个环状的空间,以便在尾部添加满之后从头部空位开始插入。 也可以使用数组队列,也就是不能动态增长的顺序队列,这样不需要每次取模最大值来构成环形...
  • 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为环形缓冲器。 循环队列一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里...
  • 循环队列

    2015-03-05 22:55:41
    队列可以使用数组或者链表实现,这里介绍种使用数组实现的循环队列。 所谓循环队列,是指当尾指针超过数组索引界限时,通过取余运算返回数组起始端,只要保证尾指针和头指针不相遇,就可以继续存储元素。 首先...
  • 假设以带头结点的循环链表(看清楚了是链表,不是循环队列,小编一开始就看错了,浪费了挺多时间)表示队列,并且只设一个指针指向队尾元素结点(注意:不设头指针),试编写相应的置空队列、判断队列是否为空、入队和出...
  • 泛型循环队列

    2021-06-12 20:01:54
    循环队列结构中,当存储空间的最后一个位置已被使用而再要进入队运算时,只需要存储空间的第一个位置空闲,便可将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生,...
  • 数组模拟循环队列

    2019-09-05 16:16:28
    .循环队列各个参数的含义 (1)队列初始化时,front和rear值都为零;...假设数组的存数空间为7,此时已经存放1,2,3,4,5,6六个元素了,如果在往数组中添加一个元素,则rear=front;此时,队列满与队列空的判断条件fr...
  • 设计一个循环队列-python.md

    千次阅读 2018-09-23 16:12:08
    循环队列包括两个指针, front 指针指向队头元素, rear 指针指向队尾元素的下一个位置。 队列为空的判断条件是: &amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;front
  • 在 FIFO 数据结构中,将首先处理添加队列中的第一个元素。 如上图所示,队列是典型的 FIFO 数据结构。插入(insert)操作也称作入队(enqueue),新元素始终被添加队列的末尾。 删除(delete)操作也被称为出队...
  • 队列一个基本的数据结构,类似排队那样先进先出,加入队列的大小是有限制的,最后一个元素进队时需要将第一个元素进行出队操作,并且队列还得有序 1. 迭代 #!/usr/bin/env python3 # -*- coding: UTF-8 -*- ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 107,052
精华内容 42,820
关键字:

循环队列每加入一个元素