Java 순환 큐 소개(코드 예)

이 기사는 Java 순환 대기열(코드 예제)에 대한 소개를 제공합니다. 이는 특정 참조 가치가 있으므로 도움이 될 수 있습니다.

배열 큐로 인해 발생하는 문제를 해결하기 위해 이 문서에서는 순환 큐를 소개합니다.

아이디어 분석 일러스트레이션

죄송합니다. 게시된 사진에 요소를 이동하거나 삭제하는 등의 애니메이션 효과를 적용하는 데는 그다지 능숙하지 않기 때문에(결국 이렇게 보는 것이 모든 사람에게 더 직관적입니다) ), 저자는 여기에서 정적 방법만 사용할 수 있습니다. 그림은 모든 사람이 구현 원리를 이해하는 데 도움이 되도록 사용됩니다. 이를 수행하는 방법을 아는 사람이 있으면 댓글 영역에서 지혜를 공유하십시오.

여기서 용량이 8인 배열을 선언하고 인덱스 0-7을 표시한 다음 front 및 tail를 사용하여 각각 대기열, 헤드를 나타냅니다. 그리고 tail of the team; 아래 그림에서 front와 tail의 위치는 처음에 인덱스 0의 위치를 ​​가리키며, 이는 front = = tai <font color="red"></font> 대기열이 비어 있을 때 다음 소개를 구별하려면 누구나 이 점을 명심해야 합니다. 대기열이 거의 가득 차면 심각한 상황front和tail分别来表示队列的，队首和队尾；在下图中，front和tail的位置一开始都指向是了索引0的位置，这意味着当front == tai的时候 <font color="'red'"></font>队列为空 大家务必牢记这一点，以便区分后面介绍队列快满时的临界条件

为了大家更好地理解下面的内容，在这里，我简单做几点说明

front：表示队列队首，始终指向队列中的第一个元素（当队列空时，front指向索引为0的位置）

tail：表示队列队尾，始终指向队列中的最后一个元素的下一个位置

元素入队，维护tail的位置，进行tail++操作

元素出队，维护front的位置，进行front++操作上面所说的，元素进行入队和出队操作，都简单的进行++操作，来维护tail和front的位置，其实是不严谨的，正确的维护tail的位置应该是(tail + 1) % capacity，同理front的位置应该是(front + 1) % capacity，这也是为什么叫做循环队列的原因，大家先在这里知道下，暂时不理解也没关系，后面相信大家会知晓。

下面我们看一下，现在如果有一个元素a入队，现在的示意图：

我们现在看到了元素a入队，我们的tail指向的位置发生了变化，进行了++操作，而front的位置，没有发生改变，仍旧指向索引为0的位置，还记得笔者上面所说的，front的位置，始终指向队列中的第一个元素，tail的位置，始终指向队列中的最后一个元素的下一个位置

现在，我们再来几个元素b、c、d、e进行入队操作，看一下此时的示意图：

想必大家都能知晓示意图是这样，好像没什么太多的变化（还请大家别着急，笔者这也是方便大家理解到底是什么循环队列，还请大家原谅我O(∩_∩)O哈！）

看完了元素的入队的操作情况，那现在我们看一下，元素的出队操作是什么样的？

元素a

다음 내용을 모두가 더 잘 이해할 수 있도록 몇 가지 간단한 설명을 하겠습니다.

front: 대기열의 선두를 나타냅니다. 항상 대기열을 가리키는 첫 번째 요소(큐가 비어 있는 경우 앞쪽은 인덱스 0의 위치를 ​​가리킴)

tail: 대기열의 꼬리를 나타내며 항상 다음 위치를 가리킵니다. 대기열의 마지막 요소요소는 대기열에 들어가고 tail의 위치를 ​​유지하며 tail++ 작업을 수행합니다.

요소는 대기열에서 제외되고 의 위치를 ​​유지합니다. front를 수행하고 front++를 수행합니다. 위에서 언급한 것처럼 요소가 대기열에 추가되고 대기열에서 제거될 때 ++ 작업은 단순히 tail 및 front입니다. 예, 꼬리를 유지하기 위한 올바른 위치는 (tail + 1)% 용량이어야 합니다. 마찬가지로 앞쪽 위치도 (front + 1)% 용량이어야 합니다. 여기서부터 먼저 알아두세요. 지금은 이해하지 못하셔도 괜찮습니다.

아래에서 a 요소가 대기열에 추가되면 현재 다이어그램을 살펴보겠습니다.

이제 요소 a가 대기열에 추가되고 꼬리가 가리키는 위치가 변경되었으며 ++ 연산이 수행되었으며 front 의 위치는 변경되지 않았으며 여전히 인덱스 0의 위치를 ​​가리킵니다. 작성자가 위에서 말한 것을 기억하세요. front 의 위치는 항상 대기열의 첫 번째 요소를 가리키고 tail 의 위치는 항상 다음 요소를 가리킵니다. 위치

이제 대기열에 합류하기 위해 몇 가지 요소 b, c, d 및 e를 추가해 보겠습니다.

🎜🎜🎜🎜모두가 알고 있다고 믿습니다 회로도가 이렇다고 해서 변경 사항은 많지 않은 것 같습니다. (또한 문의해 주세요. 걱정하지 마세요. 여러분, 이것은 순환 대기열이 무엇인지 모두가 이해하기 위한 것입니다. 양해해 주시기 바랍니다. O(∩_∩)O !)🎜🎜🎜큐에 요소를 추가하는 작업을 읽은 후, 이제 요소의 대기열 제거 작업이 어떻게 생겼는지 살펴보겠습니다. 🎜🎜🎜요소 a가 대기열에서 제거되었습니다. 회로도는 다음과 같습니다. 🎜🎜🎜🎜🎜이제 요소 a가 대기열에서 제거되었으며 전면 위치는 인덱스 1의 위치를 ​​가리킵니다. 한 위치 앞으로 이동 🎜🎜이것은 배열 대기열과 완전히 다릅니다(배열 대기열에서는 요소를 대기열에서 빼야 하며 후속 요소는 한 위치 앞으로 이동해야 합니다). 이전 O(n) 연산에서 O(1) 연산이 되었습니다🎜🎜🎜요소 b를 다시 대기열에서 제거합니다. 회로도는 다음과 같습니다.🎜🎜🎜🎜🎜🎜이 시점에서 몇몇 친구들은 왜 순환 대기열이라고 불리는지 물어볼 수도 있습니다. 이제 시도해 보겠습니다. 요소 f와 g를 각각 대기열에 추가합니다. 이때 다이어그램은 다음과 같습니다. 🎜🎜🎜🎜🎜🎜 이때 육안 검사에서는 여전히 변화가 없습니다. 요소 h 큐 작업에 참여하면 다음과 같은 질문이 발생합니다. 꼬리의 위치를 ​​어떻게 지정해야 합니까? 개략도는 다음과 같습니다. 🎜

앞서 말한 대로 요소 인큐: tail의 위치를 ​​유지하고 tail++ 연산을 수행합니다. 이때 tail은 인덱스 7의 위치를 ​​가리킵니다. 이때 tail에 ++ 연산을 수행하면 됩니다. , 분명히 불가능합니다(범위를 벗어난 배열)

조심스러운 친구들은 현재 대기열이 가득 차지 않았으며 여전히 두 자리가 남아 있다는 것을 알게 될 것입니다(이는 요소가 대기열에서 제거된 후에도 현재 공간이 후속 요소)), 배열을 링으로 상상하면 인덱스 7 이후의 위치는 인덱스 0

인덱스 7 위치에서 인덱스 0 위치까지 어떻게 계산할 수 있습니까? 이전에 tail++ 연산에 대해 이야기했습니다. , 그리고 저자도 처음에 지적했듯이 이것은 (tail + 1) % 용량이어야 하며 이는 (7 + 1) % 8이 0

이 됩니다. 따라서 요소 h가 추가되면 이때 꼬리는 인덱스 0의 위치를 ​​가리킵니다. 개략도는 다음과 같습니다.

이제 새 요소 k가 큐에 추가된다고 가정하면 꼬리의 위치는 다음과 같습니다. (꼬리 + 1) % 용량, 즉 (0 + 1) % 8은 1과 같고 인덱스 1의 위치를 ​​가리킵니다

그러면 문제는 순환 대기열이 여전히 요소를 대기열에 넣을 수 있느냐는 것입니다. 이를 분석해 보면, 이전 논리에 따르면 이제 새 요소를 넣을 수 있다고 가정할 때 인덱스가 0인 빈 공간 위치가 여전히 남아 있음을 알 수 있습니다. , tail (tail +1) % 용량 계산을 수행하고 결과는 2입니다(요소가 대기열에 성공적으로 추가된 경우 현재 대기열은 가득 찼습니다). 이때 앞쪽이 head를 나타내는 것을 알 수 있습니다. 큐도 인덱스 2의 위치를 ​​가리킵니다

새 요소가 큐에 성공적으로 합류하면 tail도 2가 되고 tail == front가 됩니다. 처음에 큐가 다음과 같다고 언급했습니다. 비어 있음, tail == front. 이제 큐가 가득 차면 tail도 앞과 같으므로 큐가 가득 찼을 때의 컬렉션과 큐가 비어 있을 때의 컬렉션을 구별할 수 없습니다

따라서 순환 큐에서는 항상 큐가 가득 찼을 때와 큐가 비어 있을 때를 구별하기 위해 공간을 낭비합니다. 즉, (tail + 1) % 용량 == front인 경우 큐가 가득 찼음을 의미하고 front == tail인 경우를 의미합니다. , 이는 대기열이 비어 있음을 의미합니다.

순환 큐의 구현 원리를 이해한 후 코드로 구현해 보겠습니다.

코드 구현

인터페이스 정의: Queue

public interface Queue<e> {
    /**
     * 入队
     *
     * @param e
     */
    void enqueue(E e);

    /**
     * 出队
     *
     * @return
     */
    E dequeue();

    /**
     * 获取队首元素
     *
     * @return
     */
    E getFront();

    /**
     * 获取队列中元素的个数
     *
     * @return
     */
    int getSize();

    /**
     * 判断队列是否为空
     *
     * @return
     */
    boolean isEmpty();
}</e>

인터페이스 구현: LoopQueue

public class LoopQueue<e> implements Queue<e> {
    /**
     * 承载队列元素的数组
     */
    private E[] data;
    /**
     * 队首的位置
     */
    private int front;
    /**
     * 队尾的位置
     */
    private int tail;
    /**
     * 队列中元素的个数
     */
    private int size;

    /**
     * 指定容量，初始化队列大小
     * (由于循环队列需要浪费一个空间，所以我们初始化队列的时候，要将用户传入的容量加1)
     *
     * @param capacity
     */
    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];
    }

    /**
     * 模式容量，初始化队列大小
     */
    public LoopQueue() {
        this(10);
    }


    @Override
    public void enqueue(E e) {
        // 检查队列为满
        if ((tail + 1) % data.length == front) {
            // 队列扩容
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }


    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空");
        }
        // 出队元素
        E element = data[front];
        // 元素出队后，将空间置为null
        data[front] = null;
        // 维护front的索引位置(循环队列)
        front = (front + 1) % data.length;
        // 维护size大小
        size--;

        // 元素出队后，可以指定条件，进行缩容
        if (size == getCapacity() / 2 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return element;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空");
        }
        return data[front];
    }

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

    @Override
    public boolean isEmpty() {
        return front == tail;
    }


    // 队列快满时，队列扩容；元素出队操作，指定条件可以进行缩容
    private void resize(int newCapacity) {
        // 这里的加1还是因为循环队列我们在实际使用的过程中要浪费一个空间
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i <p>테스트 클래스: LoopQueueTest</p>
<pre class="brush:php;toolbar:false">public class LoopQueueTest {
    @Test
    public void testLoopQueue() {
        LoopQueue<integer> loopQueue = new LoopQueue();
        for (int i = 0; i <p>테스트 결과: </p>
<pre class="brush:php;toolbar:false">原始队列: LoopQueue{【队首】data=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, front=0, tail=10, size=10, capacity=10}
元素0出队: LoopQueue{【队首】data=[null, 1, 2, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, front=1, tail=10, size=9, capacity=10}
元素1出队: LoopQueue{【队首】data=[null, null, 2, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, front=2, tail=10, size=8, capacity=10}
元素2出队: LoopQueue{【队首】data=[null, null, null, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, front=3, tail=10, size=7, capacity=10}
元素3出队: LoopQueue{【队首】data=[null, null, null, null, 4, 5, 6, 7, 8, 9, null]【队尾】, front=4, tail=10, size=6, capacity=10}
元素4出队,发生缩容: LoopQueue{【队首】data=[5, 6, 7, 8, 9, null]【队尾】, front=0, tail=5, size=5, capacity=5}
队首元素：5

전체 버전 코드 GitHub 창고 주소:

Java 버전 데이터 구조 - 큐(원형 큐)

이 기사는 여기서 끝났습니다. 더 흥미로운 콘텐츠를 보려면 PHP 중국어 웹사이트의

Java Video Tutorial

칼럼을 주목하세요!

위 내용은 Java 순환 큐 소개(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!