Java는 순환 대기열을 구현합니다.

순환 대기열의 장점

일반 대기열 대기열 작업에는 오버헤드가 높습니다. 대기열 제거 작업 중에는 모든 요소가 인덱스 0 이후에는 한 위치만큼 앞으로 이동해야 하며, 요소가 많을수록 시간이 더 많이 소모되고 시간 복잡도는 O(N)입니다.

순환 큐의 논리:

1 요소가 적을 때(꼬리 위치가 앞쪽에 있음), 순환 큐와 일반 큐. Dequeuing 작업은 동일하며, enqueue된 요소는 tail 위치에 배치되고 tail++ 작업이 수행됩니다. dequeuing 시 앞쪽 위치의 요소는 null로 설정되고 front++ 작업이 수행됩니다. 이때, 테일 위치는 계속 유지될 수 있습니다.

2 추가되면 마지막 요소가 인덱스 7 위치에 배치됩니다. 이때 tail 위치는 대기열 헤드 앞의 인덱스 0 위치로 이동합니다. 이때 배열의 tail 인덱스는 다음과 같습니다. : (tail+ 1)% 용량, 아래 그림과 같이:

🎜🎜##🎜🎜 #

3 요소가 계속 추가되면 요소가 추가됩니다. 꼬리 위치가 바뀌면 꼬리는 아래 그림과 같이 계속 뒤로 이동합니다.

# 🎜🎜#

4. 및 앞 부분은 여전히 ​​한 단위 떨어져 있습니다. 즉, 배열에는 여전히 여유 저장 공간이 있지만 현재 배열은 루프로 인해 대기열이 다음과 같다고 판단하는 조건으로 인해 더 이상 순환 대기열의 삽입 작업을 구현할 수 없습니다. 공백은 앞 == 꼬리이므로 이때 확장 작업이 필요하므로 여기서는 의도적으로 공간을 낭비합니다.

여기서 순환 큐 요소가 가득 차기 위한 조건은 다음과 같이 추론할 수 있습니다. tail +1 == front (예비 결론, (tail + 1) % 용량 ==으로 개선됩니다. front)#🎜🎜 #

5. 적절한 상황에서 dequeue 작업이 계속되면 front의 위치도 배열의 오른쪽 끝에서 배열의 왼쪽 끝으로 이동합니다. 이때 배열의 front 인덱스는 다음과 같습니다. (front + 1)%capacity

Codeimplementation

: (관련 영상 튜토리얼 공유:

java 비디오 튜토리얼

)

package dataStructure.chapter3;

/**
 * @Author: zjtMeng
 * @Date: 2019/12/28 20:13
 * @Version 1.0
 */
public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front,tail;
    private int size;

    public LoopQueue(int capacity){
        data = (E[]) new Object[capacity+1];
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length-1;
    }

    /**
     * 循环队列入队操作
     * @param e
     */
    @Override
    public void enqueue(E e) {
        //循环队列元素满的判断条件,如果满了就进行扩容操作，扩大两倍
        if ((tail+1)%data.length == front)
            resize(2 * getCapacity());
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size ++;

    }

    /**
     * 循环队列扩容
     * @param newCapacity
     */
    private void resize(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity+1];
        //循环队列第一种遍历方式
        for (int i = 0 ; i < size ; i++ ){
//newData[]中的元素与data[]中的元素，一方面存在着front的偏移量，另一方面，data[]中的元素，
//可能在有部分处于front前面，因此此处采用对数组长度取余，来判断元素的位置
            newData[i] = data[(i+front)%data.length];
        }
        data = newData;
        front =0;
        tail = size;

    }

    @Override
    public E dequeue() {
        //首先判断队列是否为空，如果为空则抛出异常
        if (isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        E ret = data[front];
        //引用地址需要置空，否则JVM不能及时回收空间，从而可能会出现OOM异常
        data[front] = null;
        front = (front + 1 )% data.length;
        size--;
        //如果元素数量达到队列容积的1/4，且队列容积/2 不等于0时，进行缩容操作
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0 )
            resize(getCapacity() / 2);
        return ret;
    }

    /**
     * 查看队首元素
     * @return
     */
    @Override
    public E getFront() {
        if (isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    /**
     * 判断循队列是否为空
     * @return
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d, capacity = %d\n",size, getCapacity()));
        res.append("front[");
        //循环队列遍历的第二种方法
        for (int i = front; i != tail; i = (i + 1) % data.length){
            res.append(data[i]);
            //循环队列未遍历到队尾的标志
            if ((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

추천 관련 기사 및 튜토리얼: java 입문 튜토리얼

위 내용은 Java는 순환 대기열을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!