关于循环队列的问题

关于循环队列的问题

今天有位老师出了一个问题，关于数组的循环队列。   我在网上看相关的实现代码，虽然懂相应的出队和入队规则，但是不懂实现的原理，麻烦老师解答下。头脑有点乱。  以下是循环队列的各种方法；/* * 循环队列 * @param <E> */public class CircleDeQueue<E> {    /**     * 数组容器     */    private E [] elements;    //尾队列指针    private int rear = 0;    //头队列指针    private int front = 0;    //数组元素个数    private int size = 0;    /**     * 默认容量长度     */    private int CAPATICY_LENGTH = 10;    /**     * -1 未查询到元素     */    private static final int ELEMENT_NOT_FOUND = -1;    public CircleDeQueue(){        elements = (E[])new Object[CAPATICY_LENGTH];    }    /**     * 获取元素长度     * @return     */    public int size(){        return this.size;    }    /**     * 判断数组容器是否为空，空返回true     * @return     */    public boolean isEmpty(){        return size == 0;    }    /**     * 尾部入队     * @param element     */    public void enQueueRear(E element){        ensureCapacity(size);        int index = index(size);        elements[index] = element;        rear = index;        size++;    }    /**     * 头部入队     * @param element     */    public void enQueueFront(E element){        ensureCapacity(size);        front = index(-1);        elements[front] = element;        size++;    }    /**     * 头部出队     * @return     */    public E deQueueFront(){        if(!isEmpty()){            E element = elements[front];            elements[front] = null;            front = index(1);            size--;　　　　　　  clear();　　　　　　　return element;        }else{            throw new NullPointerException("size: "+size);        }    }     /**      * 尾部出队      * @return      */    public E deQueueRaer(){        if(!isEmpty()){            E element = elements[rear];            elements[rear] = null;            rear = index(size - 2);            size--;　　　　　　　clear();　            return element;        }else{            throw new NullPointerException("size: "+size);        }    }    /**     * 返回队头元素     * @return     */    public E frontQueue(){        return elements[front];    }　　 /** 　　 * 返回队尾部元素 　　 * @return 　　 */　　 public E rearQueue(){    　　 return elements[rear];　　 }    /**     * 清空数据     */    private void clear(){        if(size == 0){            front = 0;            rear = 0;            elements = (E[]) new Object[DEFAULT_CAPACITY];        }    }    public String toString(){        StringBuilder sb = new StringBuilder();        sb.append("capacity: "+ elements.length);        sb.append(" ,size: "+ size);        sb.append(" ,front: " + front);        sb.append(" ,rear: " + rear);        sb.append("\nCircleQueue"+Arrays.toString(elements));        return sb.toString();    }    /**     * 数组扩容     */    public void ensureCapacity(int minCapacity){        if(minCapacity >= elements.length){            int length = (elements.length >> 1) + elements.length;            E [] newArr = (E[])new Object[length];            for (int i = 0; i < minCapacity; i++) {                newArr[i] = elements[index(i)] ;            }            front = 0;            rear = minCapacity-1;            elements = newArr;        }    }    /**     * 操作循环队列的下标     * @param index     * @return     */    private int index(int index){        index += front;        if(index < 0){            return index + elements.length;        }        return index % elements.length;    }}
慕哥8310336 2021-01-04
源自：Java输入输出流   1-1 概述
20
收起

正在回答 回答被采纳积分+1

登陆购买课程后可参与讨论，去登陆吧

2回答
好帮手慕阿慧 2021-01-05 10:31:10

同学你好，

1、CircleDeQueue类的构造方法中elements = (E[]) new Object[CAPATICY_LENGTH];是创建指定类型的数组。例如创建String类型的数组，如下：

1
CircleDeQueue<String> queue = new CircleDeQueue<String>();

size()方法是获得elements数组中元素的个数。

头部入队enQueueFront()方法：是往数组后面新增数据。尾部入队enQueueRear()方法：往数组前面新增数据。

尾部出队deQueueRaer()方法：按照尾部入队的顺序移除元素。头部出队deQueueFront()方法：按照头部入队的顺序移除元素。

返回队头元素frontQueue()方法：返回头队列指针front所指向的元素。

返回队尾部元素rearQueue()方法：返回尾队列指针rear所指向的元素。

清空数据clear()方法：新建一个数组赋值给elements，并重置front和rear值。

toString()方法：打印elements数组的容量，elements数组中元素的个数，尾队列指针和头队列指针，并输出数组中元素。

2、同学可以新建一个测试类，运行试试。

例如：

http://img1.sycdn.imooc.com//climg/5ff3cf280949965906900814.jpg

CircleDeQueue类整理好格式，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
package demo;
 
import java.util.Arrays;
 
/* * 循环队列 * @param <E> */
public class CircleDeQueue<E> {
    /**     * 数组容器     */
    private E[] elements;
    // 尾队列指针
    private int rear = 0;
    // 头队列指针
    private int front = 0;
    // 数组元素个数
    private int size = 0;
    /**     * 默认容量长度     */
    private int CAPATICY_LENGTH = 10;
    /**     * -1 未查询到元素     */
    private static final int ELEMENT_NOT_FOUND = -1;
 
    private int DEFAULT_CAPACITY = 10;
 
    public CircleDeQueue() {
        elements = (E[]) new Object[CAPATICY_LENGTH];
    }
 
    /**     * 获取元素长度     * @return     */
    public int size() {
        return this.size;
    }
 
    /**     * 判断数组容器是否为空，空返回true   */
    public boolean isEmpty() {
        return size == 0;
    }
 
    /**     * 尾部入队     * @param element     */
    public void enQueueRear(E element) {
        ensureCapacity(size);
        int index = index(size);
        elements[index] = element;
        rear = index;
        size++;
    }
 
    /**     * 头部入队     * @param element     */
    public void enQueueFront(E element) {
        ensureCapacity(size);
        front = index(-1);
        System.out.println("CircleDeQueue.enQueueFront() "+front);
        elements[front] = element;
        size++;
    }
 
    /**     * 头部出队     * @return     */
    public E deQueueFront() {
        if (!isEmpty()) {
            E element = elements[front];
            elements[front] = null;
            front = index(1);
            size--;
            clear();
            return element;
        } else {
            throw new NullPointerException("size: " + size);
        }
    }
 
    /**      * 尾部出队      * @return      */
    public E deQueueRaer() {
        if (!isEmpty()) {
            E element = elements[rear];
            elements[rear] = null;
            rear = index(size - 2);
            size--;
            clear();
            return element;
        } else {
            throw new NullPointerException("size: " + size);
        }
    }
 
    /**     * 返回队头元素     * @return     */
    public E frontQueue() {
        return elements[front];
    }
 
    /** 　　 * 返回队尾部元素 　　 * @return 　　 */
    public E rearQueue() {
        return elements[rear];
    }
 
    /**     * 清空数据     */
    private void clear() {
        if (size == 0) {
            front = 0;
            rear = 0;
            elements = (E[]) new Object[DEFAULT_CAPACITY];
        }
    }
 
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("capacity: " + elements.length);
        sb.append(" ,size: " + size);
        sb.append(" ,front: " + front);
        sb.append(" ,rear: " + rear);
        sb.append("\nCircleQueue" + Arrays.toString(elements));
        return sb.toString();
    }
 
    /**     * 数组扩容     */
    public void ensureCapacity(int minCapacity) {
        if (minCapacity >= elements.length) {
            int length = (elements.length >> 1) + elements.length;
            E[] newArr = (E[]) new Object[length];
            for (int i = 0; i < minCapacity; i++) {
                newArr[i] = elements[index(i)];
            }
            front = 0;
            rear = minCapacity - 1;
            elements = newArr;
        }
    }
 
    /**     * 操作循环队列的下标     * @param index     * @return     */
    private int index(int index) {
        index += front;
        if (index < 0) {
            return index + elements.length;
        }
        return index % elements.length;
    }
 
    public E[] getElements() {
        return elements;
    }
 
    public void setElements(E[] elements) {
        this.elements = elements;
    }
 
}

祝学习愉快

0
收起回答
  • 提问者 慕哥8310336 #1

    头部入队的方法当中涉及到一个数组扩容，它的实现流程是怎样的

    2021-01-05 12:21:20
  • 好帮手慕阿慧 回复 提问者 慕哥8310336 #2

    同学你好，ensureCapacity()方法的实现流程。如下：

    当elements中元素个数>=elements的长度时，对数组进行扩容。否则，不扩容。数组扩容就是先创建一个新数组，新数组的长度=原数组长度/2+原数组长度。其中，elements.length >> 1等同于elements.length/2。再将原数组中数据复制到新数组中。

    如下：

    http://img1.sycdn.imooc.com//climg/5ff40ada0928465f06000249.jpg

    祝学习愉快~

    2021-01-05 14:50:21
  • 提问者 慕哥8310336 回复 好帮手慕阿慧 #3

    老师，我想知道的是为啥在头部入队当中要把数组扩容的这个方法也放在里面。

    2021-01-05 21:37:38
点开查看后面1条评论
慕哥8310336 提问者 2021-01-04 21:12:04

除了判断数组容器是否为空之前的代码，后面的所有方法中的代码就理解的很迷糊了。 麻烦老师解答下！另外有个element＝（E［］）new object［CAPATICY_LENGTH］;这段代码有点不明白，是将object强转为E［］数组，可是为什么要这样操作呢

0
收起回答
问题已解决，确定采纳
还有疑问，暂不采纳

恭喜解决一个难题，获得1积分~

来为老师/同学的回答评分吧

0 星

相似问题

关于队列的问题
18 0 5
关于双端队列设计问题
20 0 6
双端队列位置确定问题
19 1 6
绑定队列的问题
17 0 3
老师，关于循环的问题
13 0 3

登录后可查看更多问答，登录/注册

java工程师2020版
  • 参与学习           人
  • 提交作业       9404    份
  • 解答问题       16556    个

综合就业常年第一，编程排行常年霸榜，无需脱产即可学习，北上广深月薪过万 无论你是未就业的学生还是想转行的在职人员，不需要基础，只要你有梦想，想高薪

了解课程

本课精华内容

问答 作业

安装了MySQL 之后有时候自己会跳出来个黑窗口是为什么呢？

80 1

什么时候用List中的ArrayList呢，什么时候用HashSet，什么时候应该用HashMap

81 1

创建字符串的过程理解

62 1

如何干净的卸载数据库

135 1

请教一下没太懂

48 3

查看更多本课问答
请稍等 ...
微信客服

购课补贴
联系客服咨询优惠详情

 帮助反馈 APP下载

慕课网APP
您的移动学习伙伴

 公众号

扫描二维码
关注慕课网微信公众号

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码，添加
你的专属老师
插入代码