美文网首页
数组实现固定长度的循环队列

数组实现固定长度的循环队列

作者: HWilliamgo | 来源:发表于2018-04-27 13:55 被阅读38次

只要指定了初始大小之后就都还能用,后进后出,就是不能动态扩容,也不能指定了一次容量之后再变更容量,由于水平原因,在尝试复制数组的时候因为头指针和尾指针不知道如何处理,没能实现循环队列的动态扩容功能。
而官方的ArrayDeque是动态扩容的双端队列,可以去看那个的实现方法。

package DataStructure;
import java.util.NoSuchElementException;

public class MyLoopQueue<T> {
    private T[] array;

    private int front;

    private int len;

    private int rear;

    @SuppressWarnings("unchecked")
    public MyLoopQueue(int capacity) {
        array = (T[]) new Object[capacity];
        len = capacity;
        front = 0;
        rear = 0;
    }
    public MyLoopQueue(){
        this(10);
    }

//    @SuppressWarnings("unchecked")
//    private void ensureCapacity(int capacity) {
//        T[] newArray = (T[]) new Object[capacity];
//
//        System.arraycopy(array, 0, newArray, 0, len);
//        array = newArray;
//        //以上,array指向了新建的对象,并且成功完成赋值。
//        len = capacity;
//    }



    public void add(T element) {
        if (isFull()) {
            throw new NoSuchElementException("队列已满!");
        }
        array[rear++] = element;
        rear = rear == len ? 0 : rear;  //不能在add(element)里面直接动态扩容的原因:
                                        //问题出在这一句,如果添加到最后一个下标,rear将==0。但是下一次调用add(element)时,
                                        // 会将element放入0的位置,并覆盖之前的所有数据。
    }

    public T remove() {
        if (isEmpty()) {
            throw new NoSuchElementException("队列已空!");
        }
        T answer = array[front];
        array[front++]=null;

        front = front == len ? 0 : front;
        return answer;
    }

    public boolean isEmpty() {
        return size()==0;
    }

    public boolean isFull() {
        return size()==len;
    }

    public int size() {
        if (rear == front) {
            return array[front] == null ? 0 : len;
        } else if (rear > front) {
            return rear - front;
        } else {
            return rear + len - front;
        }
    }

    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("队列为空!");
        }
        return array[front];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        if (isEmpty()) {
            sb.append("]");
            return sb.toString();
        }

        for (int i = 0; i < size(); i++) {
            T a = array[((front + i) % len)];
            sb.append(a.toString());
            if (i!=size()-1){
                sb.append(" , ");
            }
        }
        sb.append("]");

        return sb.toString();
    }
}

相关文章

  • 数组实现固定长度的循环队列

    只要指定了初始大小之后就都还能用,后进后出,就是不能动态扩容,也不能指定了一次容量之后再变更容量,由于水平原因,在...

  • Java队列

    阻塞队列 ArrayBlockingQueue 一个用循环数组实现的有界阻塞队列。必须指定队列长度,按 FIFO(...

  • 1.数组队列

    数组实现单队列 数组实现循环队列

  • 数组实现队列之循环队列

    对于链表实现方式,队列的入队、出队操作和栈是大同小异的。但对于数组实现方式来说,因为数组的长度固定,队列的入队和出...

  • 基于数组的队列

    1.对于基于数组实现的队列,要使用循环队列,否则会出现假溢出。 2.队列中的元素要比数组的长度少一个,用来判断队列...

  • 线程安全8 - 可阻塞的队列

    队列包含固定长度的队列和不固定长度的队列 什么是阻塞队列,阻塞队列的作用与实际应用,阻塞队列的实现原理 Array...

  • 用数组实现循环队列

    用数组实现循环队列!

  • 队列

    基于数组的循环队列 Java实现 基于链表的队列实现 Java实现

  • 有关“队列”的总结

    队列 定义 分类 链式队列 (用链表实现) 静态队列 (用数组实现)图静态队列通常都必须是循环队列循环队列的讲解:...

  • 数据结构(三) -- 单链表

    前面我们介绍了栈与队列的 ADT,并利用数组加以实现。遗憾的是,尽管这种实现简单明了,但由于数组长度必须固定,在空...

网友评论

      本文标题:数组实现固定长度的循环队列

      本文链接:https://www.haomeiwen.com/subject/tpvblftx.html