精华内容
下载资源
问答
  • 上一篇中基于数组实现了一个普通的队列手写java数据结构(普通队列-数组)这个普通队列的出队操作时间复杂度是O(n)级别的我们一个容量为8的数组data来实现一个队列,此时队列中已经入队a,b,c,d,e五个元素,a处于队首...

    上一篇中基于数组实现了一个普通的队列手写java数据结构(普通队列-数组)这个普通队列的出队操作时间复杂度是O(n)级别的

    24ac26338571bcfbe5c43d287ba31c8e.png

    我们用一个容量为8的数组data来实现一个队列,此时队列中已经入队a,b,c,d,e五个元素,a处于队首位置,e处于队尾位置。此时我们将a元素进行出队操作,那么剩余的元素则需要向左移动。所以这个普通队列的出队操作时间复杂度是O(n)级别的

    d5bb0c1cefbc08dc1ce6ed50ec1094d1.png

    对于这种情况我们可能会想,我们能不能不移动剩余元素,实现一个性能更好的队列呢?

    接下来我们就实现一个循环队列来解决这个问题。

    我们先来分析一下如何实现一个循环队列:

    仍旧以上面的图示进行分析,当队首元素a出队以后,剩余元素此时不进行移动。我们定义两个标识front 和 tail

    1. front:标识队首位置,如下图元素b此时为队首元素
    2. tail:标识下次入队时元素插入的位置,如下图下次入队时元素插入位置为索引5的位置
    b67e8d6f259a168ab03d4140395bec80.png

    那么之后进行出队、入队操作后我们只需要维护front、tail就可以了。

    1. 出队:front往后移动一个位置
    2. 入队:tai往后移动一个位置

    接下来我们在分析一下特殊情况:

    1. 初始情况下,队列中没有任何元素时,front和tail都指向同一个位置,也就是说如果front == tail队列为空
    dd2fb857e99098b39497f9c6fd465568.png

    2.

    03d2244bed695aeddb23225d7e27c170.png

    如果此时再次入队一个元素h,根据我们前面说的,tail需要往后移动一个位置。而此时tail++就会造成新的tail值超出了data数组的索引范围。既然我们要实现的是循环队列,那么对于此时这种情况我们肯定要让它循环起来。我们就要判断这个数组实现的队列是否已满,如果没有满的话说明front前面有空余的位置,我们需要将tail指向front前面的位置。

    2430f61a17b649928208108ecf6768ed.png

    tail的值我们总结出计算方式为:tail = (tail + 1) % data.length

    比如对于上面的情况tail = 7,此时入队元素h,tail = (7 + 1) % 8; tail = 0

    3.

    20ac1011270bfcc57b405982e4b03e9c.png

    如上这种情况,如果此时再次入队一个元素,tail元素再次往后移动一个位置时那么此时tail == front,而之前我们分析过tail == front时队列为空。而此时tail == front时队列是满的,这就会产生冲突。因此当(tail + 1)%data.leng == front的时候我们可以判定队列是满的,此时我们将tail位置闲置,浪费掉这个空间不再插入元素。此时,队列已满。

    下面我们用代码实现一下:

    public interface Queue { void enqueue(E e); E dequeue(); E getFront(); int getSize(); boolean isEmpty();}public class LoopQueue implements Queue {//声明一个数组data用于保存数据 private E[] data;//声明队首和队尾指针变量 private int front,tail;//size用于表示队列元素个数 private int size;//指定容量的构造函数 public LoopQueue(int capacity){ //加一是因为循环队列会浪费一个空间位置 data = (E[]) new Object[capacity + 1]; front = 0; tail = 0; size = 0; }//无参构造函数,默认容量为10 public LoopQueue() { this(10); }//扩容方法 private void resize(int newCapacity){ //新建一个扩容后的数组 E[] newData = (E[]) new Object[newCapacity+1]; //将原数组data变量保存到新数组中,这里要注意按照队列的顺序进行保存 for(int i = 0;i < size; i++){ newData[i] = data[(i+front) % data.length]; } data = newData; front = 0; tail = size; }//入队 @Override public void enqueue(E e) { //首先判断队列是否已满,如果已满我们对其进行扩容 if((tail + 1) % data.length == front){ //扩容原来两倍 resize(getCapacity()*2); } //将新元素插入到tail的位置 data[tail] = e; //更新tail的值 tail = (tail + 1) % data.length; size++; }//出队 @Override public E dequeue() { if(isEmpty()){ throw new IllegalArgumentException("empty"); } //获取队首元素 E ret = data[front]; //内存回收 data[front] = null; //更新front值 front = (front + 1) % data.length; size--; //缩容 if(size == (getCapacity()/4) && getCapacity() / 2 != 0){ resize(getCapacity()/2); } return ret; }//查看队首元素 @Override public E getFront() { if(isEmpty()){ throw new IllegalArgumentException("empty"); } return data[front]; }//队列长度 @Override public int getSize() { return size; }//队列是否为空 @Override public boolean isEmpty() { return front == tail; }//队列容量 public int getCapacity(){ return data.length - 1; }  @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("loopqueue:"); sb.append("front["); for(int i = front;i != tail;i = (i + 1) % data.length){ sb.append(data[i]); if((i + 1) % data.length != tail){ sb.append(","); } } sb.append("]end"); return sb.toString(); }}
    展开全文
  • 上一篇中基于数组实现了一个普通的队列手写java数据结构(普通队列-数组)这个普通队列的出队操作时间复杂度是O(n)级别的我们一个容量为8的数组data来实现一个队列,此时队列中已经入队a,b,c,d,e五个元素,a处于队首...

    上一篇中基于数组实现了一个普通的队列手写java数据结构(普通队列-数组)这个普通队列的出队操作时间复杂度是O(n)级别的

    3ab58fd001fbf5e1e816051da058a6f3.png

    我们用一个容量为8的数组data来实现一个队列,此时队列中已经入队a,b,c,d,e五个元素,a处于队首位置,e处于队尾位置。此时我们将a元素进行出队操作,那么剩余的元素则需要向左移动。所以这个普通队列的出队操作时间复杂度是O(n)级别的

    45a66cce6880b3ba72f74d83cc668dba.png

    对于这种情况我们可能会想,我们能不能不移动剩余元素,实现一个性能更好的队列呢?

    接下来我们就实现一个循环队列来解决这个问题。

    我们先来分析一下如何实现一个循环队列:

    仍旧以上面的图示进行分析,当队首元素a出队以后,剩余元素此时不进行移动。我们定义两个标识front 和 tail

    1. front:标识队首位置,如下图元素b此时为队首元素
    2. tail:标识下次入队时元素插入的位置,如下图下次入队时元素插入位置为索引5的位置
    0cc859f07a5cf087431be1725f44113d.png

    那么之后进行出队、入队操作后我们只需要维护front、tail就可以了。

    1. 出队:front往后移动一个位置
    2. 入队:tai往后移动一个位置

    接下来我们在分析一下特殊情况:

    1. 初始情况下,队列中没有任何元素时,front和tail都指向同一个位置,也就是说如果front == tail队列为空
    9da20b501975cd161ca8e80d709973a0.png

    2.

    ec17399adc84728ec594d14705498d1f.png

    如果此时再次入队一个元素h,根据我们前面说的,tail需要往后移动一个位置。而此时tail++就会造成新的tail值超出了data数组的索引范围。既然我们要实现的是循环队列,那么对于此时这种情况我们肯定要让它循环起来。我们就要判断这个数组实现的队列是否已满,如果没有满的话说明front前面有空余的位置,我们需要将tail指向front前面的位置。

    6c62c5157f35deff1569295bb046eded.png

    tail的值我们总结出计算方式为:tail = (tail + 1) % data.length

    比如对于上面的情况tail = 7,此时入队元素h,tail = (7 + 1) % 8; tail = 0

    3.

    e42f0c377ec9323a746b62ec80f76a27.png

    如上这种情况,如果此时再次入队一个元素,tail元素再次往后移动一个位置时那么此时tail == front,而之前我们分析过tail == front时队列为空。而此时tail == front时队列是满的,这就会产生冲突。因此当(tail + 1)%data.leng == front的时候我们可以判定队列是满的,此时我们将tail位置闲置,浪费掉这个空间不再插入元素。此时,队列已满。

    下面我们用代码实现一下:

    public interface Queue { void enqueue(E e); E dequeue(); E getFront(); int getSize(); boolean isEmpty();}public class LoopQueue implements Queue {//声明一个数组data用于保存数据 private E[] data;//声明队首和队尾指针变量 private int front,tail;//size用于表示队列元素个数 private int size;//指定容量的构造函数 public LoopQueue(int capacity){ //加一是因为循环队列会浪费一个空间位置 data = (E[]) new Object[capacity + 1]; front = 0; tail = 0; size = 0; }//无参构造函数,默认容量为10 public LoopQueue() { this(10); }//扩容方法 private void resize(int newCapacity){ //新建一个扩容后的数组 E[] newData = (E[]) new Object[newCapacity+1]; //将原数组data变量保存到新数组中,这里要注意按照队列的顺序进行保存 for(int i = 0;i < size; i++){ newData[i] = data[(i+front) % data.length]; } data = newData; front = 0; tail = size; }//入队 @Override public void enqueue(E e) { //首先判断队列是否已满,如果已满我们对其进行扩容 if((tail + 1) % data.length == front){ //扩容原来两倍 resize(getCapacity()*2); } //将新元素插入到tail的位置 data[tail] = e; //更新tail的值 tail = (tail + 1) % data.length; size++; }//出队 @Override public E dequeue() { if(isEmpty()){ throw new IllegalArgumentException("empty"); } //获取队首元素 E ret = data[front]; //内存回收 data[front] = null; //更新front值 front = (front + 1) % data.length; size--; //缩容 if(size == (getCapacity()/4) && getCapacity() / 2 != 0){ resize(getCapacity()/2); } return ret; }//查看队首元素 @Override public E getFront() { if(isEmpty()){ throw new IllegalArgumentException("empty"); } return data[front]; }//队列长度 @Override public int getSize() { return size; }//队列是否为空 @Override public boolean isEmpty() { return front == tail; }//队列容量 public int getCapacity(){ return data.length - 1; }  @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("loopqueue:"); sb.append("front["); for(int i = front;i != tail;i = (i + 1) % data.length){ sb.append(data[i]); if((i + 1) % data.length != tail){ sb.append(","); } } sb.append("]end"); return sb.toString(); }}
    展开全文
  • 队列_数组实现

    2020-07-24 08:57:17
    目录 【数组队列】 简易数组队列实现 循环数组队列实现 【数组队列】 简介:队列类似于排队,...1,需要先初始化front与rear为-1,后续front指向第一个数据,rear指向最后一个数据,在创建一个maxSize大小的数组a.

    目录

    【数组队列】

    简易数组队列实现

    循环数组队列实现


    【数组队列】

    简介:队列类似于排队,其遵循先入先出的规律,队列需要头索引(front)与尾索引(rear),在不同的实现思路里头尾索引初始值不同,每添加一个数据尾索引向后一位,每取出一个数据头索引向后一位。是一个有序列表,可以用数组或链表为核心存储介质实现。

     

    简易数组队列实现

    结构分析:

    1,需要先初始化front与rear为-1,后续front指向第一个数据,rear指向最后一个数据,在创建一个maxSize大小的数组arr

    2,isEmpty方法通过front==rear判断,isFull方法通过rear==maxSize-1判断

    3,add方法先判断isFull,再通过arr[++rear]来实现添加数据和尾索引向后一位

    4,get方法先判断isEmpty,再通过返回arr[++front]来实现返回数据和头索引向后一位

    5,show方法先判断IsEmpty,再通过从front到arr.length循环遍历输出arr中数据

    6,head方法先判断IsEmpty,再通过arr[front+1]数据,输出!=取出。

    package cn.dataStructure.demo;
    
    import javax.sound.midi.Soundbank;
    import java.util.Scanner;
    
    class ArrayQueue{
        private int maxSize;//队列数组最大值存储空间
        private int front;//头索引,保存头数据的前一个索引
        private int reer;//尾索引,保存尾数据的后一个索引
        private int arr[];//保存数据
        public ArrayQueue(int maxSize){
            front=-1;//初始化front与reer为-1
            reer=-1;
            this.maxSize=maxSize;
            arr=new int[maxSize];
        }
        public boolean isEmpty(){
            return this.front==this.reer;
        }
        public boolean isFull(){
            return this.reer==maxSize-1;
        }
        public void add(int data){
            if (isFull()){
                throw new RuntimeException("队列满,无法添加数据");
            }
            this.arr[++reer]=data;//reer向后一位
        }
        public int get(){
            if (isEmpty()){
                throw new RuntimeException("队列空,无法获取数据");
            }
            return this.arr[++front];//front向后一位
        }
        public void show(){
            if (isEmpty()){
                System.out.println("队列空");
                return;
            }
            for (int i=front+1;i<arr.length;i++){//从有数据的开始展示
                System.out.printf("arr[%d]=%d\n",i,arr[i]);
            }
        }
        public int head(){//展示头数据,不是取出数据,front不加一
            if (isEmpty()){
                throw new RuntimeException("队列空");
            }
            return arr[front+1];
        }
    }
    public class 队列_queue {
        public static void main(String[] args) {
            ArrayQueue queue=new ArrayQueue(3);
            boolean flag=true;//循环判据
            char key;//用户输入
            Scanner scan=new Scanner(System.in);
            while (flag){
                System.out.println("s(show):显示队列");
                System.out.println("a(add):添加数据");
                System.out.println("g(get):取出数据");
                System.out.println("h(head):查看头数据");
                System.out.println("e(exit):退出程序");
                key=scan.next().charAt(0);//接收一个字符
                switch (key){
                    case 's':
                        queue.show();
                        break;
                    case 'a':
                        System.out.print("输入一个数:");
                        int data=scan.nextInt();
                        queue.add(data);
                        break;
                    case 'g':
                        try {
                            System.out.println(queue.get()); 
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h':
                        try {
                            System.out.println(queue.head());
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e':
                        flag=false;
                        scan.close();//关闭输入流
                        break;
                }
            }
            System.out.println("已退出程序");
    
        }
    }
    
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序
    a
    输入一个数:1
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序
    a
    输入一个数:2
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序
    s
    arr[0]=1
    arr[1]=2
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序
    h
    1
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序

     简易版本的最大不足之处在于无法复用,数组用过一遍,由于reer与front直加,超出数组范围,数组失效。采用循环数组(环状数组)的形式可实现复用

     

    循环数组队列实现

    结构分析:

    1,需要先初始化front与rear为1,后续front指向第一个数据,rear指向最后面一个数据之后一个索引(这是为了空出最后一个一个数组空间,这个空闲空间很有用,后续会讲),再创建一个maxSize大小的数组arr

    2,队列满判据:(rear+1)%maxSize==front (reer是索引,maxSize是个数,索引从0开始,个数从1开始,所以rear+1后获得与个数对应的值,再与maxSize求模得到循环过程中一个周期的真实位置索引,当其等于front时,说明周期完成,即数据满了)这里不好理解,可画图验证。

    3,队列空判据:rear==front

    4,队列中有效值个数:(rear+maxSize-front)%maxSize(不好说清楚,画图理解)

    5,通过以上判据,方法对简易数组队列进行修改,注意循环数组中数据在循环周期里的真实位置索引,要通过n%length的形式来获取。

    package cn.dataStructure.demo;
    
    import javax.sound.midi.Soundbank;
    import java.util.Scanner;
    
    class ArrayQueue{
        private int maxSize;//队列数组最大值存储空间
        private int front;//头索引,保存头数据的前一个索引
        private int rear;//尾索引,保存尾数据的后一个索引
        private int arr[];//保存数据
        public ArrayQueue(int maxSize){
            front=0;//初始化front与rear为0
            rear=0;
            this.maxSize=maxSize;
            arr=new int[maxSize];
        }
        public boolean isEmpty(){
            return this.front==this.rear;//空判据:front=rear
        }
        public boolean isFull(){
            return (rear+1)%maxSize==front;//满判据:(rear+1)%maxSize==front
        }
        public void add(int data){
            if (isFull()){
                throw new RuntimeException("队列满,无法添加数据");
            }
            this.arr[rear]=data;//rear从0开始
            rear=(rear+1)%maxSize;//rear向后一位
        }
        public int get(){
            if (isEmpty()){
                throw new RuntimeException("队列空,无法获取数据");
            }
            int value=arr[front];//front从0开始
            front=(front+1)%maxSize;//front向后一位
            return value;
    
        }
        public void show(){
            if (isEmpty()){
                System.out.println("队列空");
                return;
            }
            for (int i=front;i<front+size();i++){
                System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);//i的真实位置索引需要求模计算
            }
        }
        public int size(){//计算有效值个数
            return (rear+maxSize-front)%maxSize;//有效值个数判据:(rear+maxSize-front)%maxSize
        }
        public int head(){//展示头数据,不是取出数据,front不加一
            if (isEmpty()){
                throw new RuntimeException("队列空");
            }
            return arr[front];
        }
    }
    public class 队列_queue {
        public static void main(String[] args) {
            ArrayQueue queue=new ArrayQueue(4);
            boolean flag=true;//循环判据
            char key;//用户输入
            Scanner scan=new Scanner(System.in);
            while (flag){
                System.out.println("s(show):显示队列");
                System.out.println("a(add):添加数据");
                System.out.println("g(get):取出数据");
                System.out.println("h(head):查看头数据");
                System.out.println("e(exit):退出程序");
                key=scan.next().charAt(0);//接收一个字符
                switch (key){
                    case 's':
                        queue.show();
                        break;
                    case 'a':
                        System.out.print("输入一个数:");
                        int data=scan.nextInt();
                        queue.add(data);
                        break;
                    case 'g':
                        try {
                            System.out.println(queue.get());
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h':
                        try {
                            System.out.println(queue.head());
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e':
                        flag=false;
                        scan.close();//关闭输入流
                        break;
                }
            }
            System.out.println("已退出程序");
    
        }
    }
    
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序
    a
    输入一个数:1
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序
    a
    输入一个数:2
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序
    s
    arr[0]=1
    arr[1]=2
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序
    h
    1
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序
    s
    arr[0]=1
    arr[1]=2
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序
    g
    1
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序
    a
    输入一个数:4
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序
    s
    arr[1]=2
    arr[2]=4
    s(show):显示队列
    a(add):添加数据
    g(get):取出数据
    h(head):查看头数据
    e(exit):退出程序

    可见,循环数组实现了数组的复用。但其困难之处在于%(求模)的理解,求模运算还是为了将多个循环周期里的索引压缩到一个周期中的索引,好与其他值比较。另外解答开始提出的循环数组队列中为什么要将数组最后一个位置空出,让rear指向?

    队列里有两个索引:
    一个指向队列头front,一个指向队列尾rear。每次增加一个队列元素,rear+1。每次出队一个元素 front +1。
    队列的长度大小就是rear-front。
    但是在循环队列中,如果还是用rear-front,就会有一个问题出现,就是两个指针指向同一个的时候,你无法区分是因为队列是空的,还是rear已经绕了一圈回来了(即队满的情况)。so我们要加一个空的位置,这个位置不放任何元素,作用就是为了区别队空和队满。如果队空的情况下,rear=front。
    队满的情况下,rear-front!=0,得出的答案是真正的队列长度。

    也就是说,若不空出此位置将导致无法用 rear==front 的判据来判定是否队列为空。(理解不了,画图吧)

     

    【数据结构与算法整理总结目录 :>】<-- 宝藏在此(doge)  

    展开全文
  • 1. 队列基础 Queue. A queue supports the insert and remove operations using a first-in first-out (FIFO) discipline. By convention, we name the queue insert operation enqueue and the remove operation ...

    1. 队列基础

    Queue. A queue supports the insert and remove operations using a first-in first-out (FIFO) discipline. By convention, we name the queue insert operation enqueue and the remove operation dequeue, as indicated in the following API.
    队列:是一种支持FIFO(First in First out)的数据结构,一般有入队列和出队列2种基本操作,循环队列实现是对空间的有效利用。

    2. 相关代码及说明

    //Queue.java
    package com.fqy.queue;
    
    import java.lang.reflect.Array;
    
    public class Queue<T> {
        private int size;
        private int total;
        private int front;
        private int rear;
        private T[] queue;
    
        @SuppressWarnings("unchecked")
        public Queue(int size) {
            this.size = size;
            total = 0;
            front = 0;
            rear = 0;
            total = 0;
            queue = (T[]) new Object[this.size];
        }
    
        // Why code like this? To produce 'generic' array
        public Queue(Class<T[]> cl, int size) {
            this.size = size;
            total = 0;
            front = 0;
            rear = 0;
            total = 0;
            queue = cl.cast(Array.newInstance(cl.getComponentType(), this.size));
        }
    
        public boolean enqueue(T item) {
            if (!isFull()) {
                queue[rear] = item;
                // Special case
                rear = (rear + 1) % size;
                total++;
                return true;
            } else {
                return false;
            }
        }
    
        public T dequeue() {
            if (!isEmpty()) {
                T item = queue[front];
                queue[front] = null;
                front = (front + 1) % size;
                total--;
    
                return item;
            } else
                return null;
        }
    
        public void traverseQueue() {
            int index = front;
            for (int i = 0; i < total; i++) {
                System.out.print(queue[index] + " ");
                index = (index + 1) % size;
            }
        }
    
        /*
         * 在循环队列结构下,当front==rear时为空队列,当front==(rear+1)%maxSize时为满队列。
         * 注意,满队列时,仍有一个元素空间未被使用。若不留该空间,则队尾指针rear指向该空间导致了, 满队列和空队列判定条件相同。
         */
        public boolean isFull() {
            // return total == size;
            return (rear + 1) % size == front;
        }
    
        public boolean isEmpty() {
            // return total == 0;
            return rear == front;
        }
    
        public int getTotal() {
            return total;
        }
    }
    
    
    //TestQueue.java
    package com.fqy.queue;
    
    import java.util.Random;
    
    public class TestQueue {
    
        public static void main(String[] args) {
            // The actual elements a queue can hold is 10-1;
            Queue<Integer> queue = new Queue<>(Integer[].class, 11);
            Random random = new Random();
    
            for (int i = 0; i < 10; i++) {
                int val = random.nextInt(100);
                System.out.print(val + " ");
                queue.enqueue(val);
            }
            System.out.println();
            queue.traverseQueue();
            System.out.println("\n" + queue.getTotal());
            while (!queue.isEmpty()) {
                System.out.print(queue.dequeue() + " ");
            }
        }
    
    }
    
    
    //Running result:
    48 55 95 82 31 5 18 80 25 92 
    48 55 95 82 31 5 18 80 25 92 
    10
    48 55 95 82 31 5 18 80 25 92 
    展开全文
  • 循环队列能充分利用空间,解决队列假上溢现象。 import java.io.*; public class QueueArray { Object[] a; /*对象数组,队列最多存储a.length-1个对象,浪费一个存储单元。这是因为如果将数组装满,则队列...
  • 我们在用数组实现队列的时候,发现当tail = n时,就会有数据搬移的操作,这样一来入队操作的性能就会受到影响。那我们可以使用循环队列来解决这一问题。 循环队列,顾名思义,它长得像一个环。如下图所示: 我们...
  • 循环数组

    千次阅读 2017-12-18 19:41:43
    循环数组也一般用队列来实现。例题:假设有n个人围坐着圆桌,他们的名字是A,B,C,D,……。给定一个名字,我们要做的就是打印出n个人的座次,从这个给定的人开始。 例如,假设有6个人ABCDEF,已知了D,那
  • Relax-and-Recover produces a bootable image. This image can repartition the system. Once that is done it initiates a restore from backup. Restores to different hardware are possible. Relax-and-Recover...
  • 循环队列

    2017-04-14 08:40:01
    话说其实这个算标题党,老师留的作业也确实叫循环队列,实际上就是一道用数组模拟的数学题,谁让老师限制了时间空间复杂度呢,活活弄没了数据结构该有的部分 上题:设计算法,将存有n(n>0)个数的数组A中的元素A[0]...
  • 循环队列元素个数

    万次阅读 多人点赞 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)...
  • 循环队列操作 C

    2020-03-21 11:25:25
    队列的出入条件 是先进先出,就是队头出,队尾入,根据这个特性,我们可以两个指针来代表队头的位置与队尾的位置,队头为front,队尾为 rear。 我们假设一个长度为5的数组,来模拟队列: 这时 rear和front 指针...
  • 队列通常可以用数组或者是链表实现。这里以数组举例,假设这儿有一个长度为5的数组,左端为头部,负责取出数据,右端为尾部,负责存入数据。 从尾部加入数据A 再从尾部加入数据B 再从尾...
  • 数组的题还是普遍比较简单的,这道题我取巧了,取巧的方法看看就行,没多大意义,了点循环队列的思想()  其实比赛的时候,无论怎么过的都无所谓,能过就行。我直接在读入数据的时候做了手脚……。让 i 从 step ...
  • 假设有数组 [a b c d e f g h ],一个大小为 3 的 滑动窗口 在其上滑动,则有:[a b c] [b c d] [c d e] [d e f] [e f g] [f g h]一般情况下就是使用这个窗口在数组的 合法区间 内进行滑动,同时 动态地 记录一些...
  • 队列 什么是队列 先进者先出,这就是典型的队列。 队列和栈一样,也是一种操作受限的线性表数据结构 ...循环队列、阻塞队列、并发队列 基于数组的实现方法 // 用数组实现的队列 public class A...
  • 队列

    2017-05-17 20:16:07
    循环数组队列(循环队列比一般数组队列实用,所以这里它举例子) 1.定义循环数组队列(计算机不会给你创建好) typedef struct node{ int shuzi[5]; int rear,front; }duilie; (英文不好,拼音) 2.置空队列...
  • 数组和广义表 2021-1-16

    2021-01-16 14:37:36
    用数组表示的循环队列中,front值一定小于等于rear值。 F 1-2 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用顺序表存储最节省时间。 T 1-3 若用链表来表示一个线性表,...
  • 线性结构的两种常见应用之二 队列 ...b)静态队列【数组队列】——用数组实现  静态队列通常都必须是循环队列。 3.循环队列的讲解: ① 静态队列为什么必须是循环队列  a) 非空队
  • java手写队列

    千次阅读 2019-02-12 13:55:14
    队列也可以用数组来实现,不过这里有个问题,当数组下标满了后就不能再添加了,但是数组前面由于已经删除队列头的数据了,导致空。所以队列我们可以用循环数组来实现,见下面的代码: package com.cn.test.queue; ...
  • 文章目录打造属于自己的栈和队列栈栈的应用实现一个栈的接口实现一个栈(基于数组)测试栈类队列实现一个数组队列实现一个循环队列数组队列与循环队列的比较 打造属于自己的栈和队列 ​ 前一篇博客介绍了如何打造...
  • 队列的实现

    2013-09-26 16:20:34
    一开始使用数组来表示队列,但是会造成很多的数据搬移,效率太低,所以考虑使用循环队列循环队列的约定如下: 用a[0] - a[maxsize - 1]来表示整个队列最开始是rear == front ==0空出一个字节,用来辨别空队列和...
  • 静态队列,用数组实现(必须是循环队列) 应用: 与时间有关的操作都与队列有关都有队列的影子 为了与栈的算法区分开, 这里要使用 的指针换个名字,其实也差不多滴, 那么这里的就叫rear 就叫font Q1: 静态队列为...
  • 这里不讲数组模拟的方法(毕竟多做点题的模拟功力足以暴力出这道题),而是讲一种单循环链的做法。...我们用数组来模拟这一链形结构:a[i]存放编号为i的节点的下一个节点的编号,(在本题中初始为a[...
  • 作业9-队列及其应用

    2020-12-11 21:35:12
    1-2 在用数组表示的循环队列中,front...如果循环队列用大小为m的数组表示,队头位置为front、队列元素个数为size,那么队尾元素位置rear为:D A.front+size B.front+size-1 C.(front+size)%m D.(front+size-1)%m ...
  • 循环队列: 题目链接:cf 792B  分析:这个题就是约瑟夫环的变形,考虑到n比较小,可以队列模拟。 code: #include const int MAXN=100+5; int Q[MAXN]; int a[MAXN]; int main(void){  int n,k;scanf...
  • 所谓“循环队列”是指单向循环链表或者循环数组表示的队列。 选择题 A. B. C. D. A. B. C. D. A. B. C. D. A. B. C. D. A. B. C. D. A. B. C. D. A. B. C...
  • 所谓“循环队列”是指单向循环链表或者循环数组表示的队列。 F错误。将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue) An algorithm to check ...
  • Java面试之手写队列

    2019-04-18 18:03:37
    用数组写一个队列。上代码 主要的功能巧在了循环数组的使用 public class RoundQueue { private long[] a; private int size; private int nItems; //实际存储数量 private int front; //头 private int rear;...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 157
精华内容 62
关键字:

循环队列用数组a