Java에서 순환 대기열을 구현하는 방법

1. 일반 대기열의 문제점은 무엇인가요?

대기열에는 몇 가지 중요한 속성이 있다는 것은 누구나 알고 있습니다.

• rear: 마지막 요소가 있는 대기열의 꼬리를 가리키며 초기 값은 -1입니다.

• front: 대기열의 꼬리를 가리킵니다. head of the queue 의 이전 위치도 -1

• capacity: 대기열의 용량

대기열에 들어갈 때 빈 대기열의 뒤쪽과 앞쪽은 모두 -1입니다. , 앞쪽은 움직이지 않고, 뒤쪽++은 rear == capacity - 1时，队列已满；出队时，rear不动，front++，当front == rear时，队列为空。看起来很完美，但实际上有问题。假如一个队列capacity = 3，入队了三个元素，此时front = -1; rear = 2，然后再将三个元素都出队，此时front = 2, rear = 2。这时队列明明是空的，但是却不能再入队元素的，因为满足rear = capacity - 1 즉, 이 대기열이 일회용인 것과 동일합니다. 사용 후에는 비어 있어도 다시 사용할 수 없습니다. 다시 대기열을 생성하여 공간 낭비를 초래하므로 순환 대기열이 나타납니다.

2. 링 큐 구현 아이디어:

링 큐의 여러 중요한 속성:

• rear: 큐의 꼬리 뒤의 위치를 ​​가리키며, 초기 값은 0입니다.

• front: 포인트 대기열의 선두로 초기 값은 0

• capacity: 대기열의 용량

다음은 링 대기열에 대한 일부 알고리즘입니다.

• 대기열이 비어 있는 경우: ​ front == rear

• 큐가 가득 찬 경우: ​ (rear + 1) % capacity == front

• 큐 요소 수를 가져옵니다. ​ (rear + capacity - front) % capacity

• 팀에 합류할 때: ​ rear = (rear + 1) % capacity

• 대기열 밖에서 운영하는 경우: front = (front + 1) % 용량;front = (front + 1) % capacity;

判断队列是否已满是环形队列中最重要也是最难理解的地方。假如有一个队列capacity = 3

• 큐가 꽉 찼는지 확인하는 것은 순환 큐의 가장 중요하면서도 이해하기 어려운 부분입니다. 대기열 capacity = 3이 있는 경우 대기열 추가 작업은 다음과 같습니다.

  front = 0(rear + 1) % capacity = 1 % 3 != frontrear = 1첫 번째 요소가 대기열에 추가됩니다. ​

  왜냐하면
요소를 대기열에 추가할 수 있도록 요소가 대기열에 추가된 후 ​
• ;

  front = 0(rear + 1) % capacity = 2 % 3 != frontrear = 2두 번째 요소가 대기열에 추가됩니다. ​

  왜냐하면
요소를 대기열에 추가할 수 있도록 요소가 대기열에 추가된 후 ​
• ;

  front = 0(rear + 1) % capacity = 3 % 3 == front

  세 번째 요소가 팀에 합류합니다. ​
왜냐하면 ​​

, 요소를 대기열에 추가할 수 없으므로 대기열이 가득 찼습니다.

대기열 용량은 당연히 3인데 대기열에 요소 2개만 추가되므로 대기열이 가득 찼다는 뜻인가요? 예, 대기열이 가득 찼는지 확인하는 이 알고리즘은 배열의 공간을 희생해야 합니다.

• 이제 대기열 제거 작업을 수행합니다.

  front = 1rear = 2(rear + 1) % capacity = 3 % 3 = 0 != front첫 번째 요소가 대기열에서 제거됩니다. ​

  , ​
,

.

요소가 대기열에서 제거되면 대기열에 합류하기 위한 조건을 충족하므로 배열 공간을 재사용할 수 있다는 것을 알 수 있습니다.

3. 코드 연습: 🎜

<code>public class CircleQueue<E> {<br>    private int capacity;<br>    private int front;<br>    private int rear;<br>    private Object[] arr;<br><br>    public CircleQueue(int capacity){<br>        this.capacity = capacity;<br>        this.arr = new Object[capacity];<br>        this.front = 0;<br>        this.rear = 0;<br>    }<br><br>    public boolean isFull(){<br>        return (rear + 1) % capacity == front;<br>    }<br><br>    public boolean isEmpty(){<br>        return rear == front;<br>    }<br><br>    public void addQueue(E e){<br>        if (isFull()){<br>            throw new RuntimeException("队列已满，入队失败");<br>        }<br>        arr[rear] = e;<br>        // rear指针后移<br>        rear = (rear + 1) % capacity;<br>    }<br><br>    public E getQueue(){<br>        if (isEmpty()){<br>            throw new RuntimeException("队列为空，出队失败");<br>        }<br>        E val = (E) arr[front];<br>        front = (front + 1) % capacity;<br>        return val;<br>    }<br><br><br>    public int getSize(){<br>        return (rear + capacity - front) % capacity;<br>    }<br><br>    // 遍历<br>    public void showQueue(){<br>        if (isEmpty()){<br>            return;<br>        }<br>        for (int i = front; i < front + getSize(); i++) {<br/>            System.out.printf("arr[%d]=%d\n", i%capacity, arr[i%capacity]);<br/>        }<br/>    }<br/><br/>    public static void main(String[] args){<br/>        CircleQueue<Integer> queue = new CircleQueue<>(3);<br>        queue.addQueue(1);<br>        queue.addQueue(2);<br>        queue.showQueue();<br>        //queue.addQueue(3);<br>        System.out.println(queue.getSize());<br>        System.out.println(queue.getQueue());;<br>        queue.addQueue(3);<br>        queue.showQueue();<br>    }<br>}</code>

🎜🎜

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