자바 순환 대기 열 원리 와 용법 상세 설명

본 고의 실례 는 자바 순환 대기 열의 원리 와 용법 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
본 격 적 으로 순환 대기 열 학습 을 진행 하기 전에 순서 대기 열 에서 팀 의 첫 번 째 요 소 를 삭제 하 는 문제 부터 살 펴 보 겠 습 니 다.
(1)용량 은 capacity=8,size=5(a,b,c,d,e)의 배열 을 설정 하고 왼쪽 은 팀 의 우두머리,오른쪽 은 팀 의 꼬리 이다.

(2)한 원소 가 나 온 후,전체적으로 한 자 리 를 앞으로 이동 해 야 한다.
출대
  
\#2 전체 한 자리 앞으로 이동

이 조작 방식 에 대하 여 우 리 는 시간 복잡 도 를 O(n)로 쉽게 얻 을 수 있다.
이때 우 리 는 팀 요소 가 나 온 후에 전체적인 요 소 를 앞으로 이동 하지 않 고 배열 에서 팀 의 첫 번 째 front 가 누구 인지 기록 할 수 있 을 까 생각 했다.동시에 팀 의 꼬리 tail 은 다음 요소 가 입대 할 때의 위 치 를 가리 키 고 있다.그러면 팀 이 나 올 때 front 의 방향 만 유지 하면 되 고 요 소 를 이동 하지 않 아 도 된다.이렇게 해서 우 리 는 순환 대열 의 상황 이 생 겼 다.

2.순환 대기 행렬 원리
(1)초기 에 배열 이 전체적으로 비어 있 을 때 팀 의 첫 번 째 front,팀 의 꼬리 tail 은 같은 위치(배열 색인 이 0 인 곳),즉 front==tail 시 대기 열 이 비어 있 습 니 다.

 
(2)배열 에 요 소 를 추가 하면,

(3)하나의 요 소 를 내 고 front 는 새로운 위 치 를 가리킨다.

(4)입대 원소,tail 중첩

(5)tail 이 더 이상 증가 할 수 없 을 때 배열 앞 에 여유 가 있 습 니 다.이때 순환 대기 열 이 등장 해 야 합 니 다.
 
이 때 배열 은 이렇게 바 뀌 어야 합 니 다.

 배열 에 요 소 를 추가 합 니 다:

이렇게 배열 이 가득 찼 습 니 다(tail+1=front 대기 열 이 가득 찼 습 니 다).확장 작업 을 시작 합 니 다.[capacity 에서 공간 을 낭비 합 니 다.
tail 이 배열 의 앞 위치 로 돌아 갈 수 있 도록 대기 열 이 가득 찬 표현 식 을[(tail+1)%c=front]로 바 꾸 면 배열 이 순환 적 으로 이동 할 수 있 습 니 다.
3.순환 대기 열 코드 구현
클래스 LoopQueue 를 새로 만 들 고 인터페이스 Queue 를 실현 합 니 다.
\#1:인터페이스 큐 코드 는 다음 과 같 습 니 다:

package Queue;

public interface Queue<E> {
  //         
  int getSize();

  //         
  boolean isEmpty();

  //   
  void enqueue(E e);

  //   
  E dequeue();

  //      
  E getFront();
}

\#2:LoopQueue 관련 코드:

package Queue;

//    
public class LoopQueue<E> implements Queue<E> {
  private E[] data;
  private int front, tail;
  private int size;//       

  //    ，       capacity    
  public LoopQueue(int capacity) {
    data = (E[]) new Object[capacity + 1];//       
    front = 0;
    tail = 0;
    size = 0;
  }

  //      ，       capacity=10
  public LoopQueue() {
    this(10);
  }

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

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

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

  //     
  @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 ret = data[front];
    data[front] = null;//    
    front = (front + 1) % data.length;
    size--;
    if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
      resize(getCapacity() / 2);
    }
    return ret;
  }

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

  //    
  private void resize(int newCapacity) {
    E[] newData = (E[]) new Object[newCapacity + 1];
    for (int i = 0; i < size; i++) {
      newData[i] = data[(front + i) % data.length];//        
    }
    data = newData;
    front = 0;
    tail = size;
  }


  @Override
  public String toString() {
    StringBuilder res = new StringBuilder();
    res.append(String.format("Queue:size=%d, capacity=%d
", 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();
  }



}

LoopQueue 클래스 에서 주의해 야 할 것:
(1)11 번 째 줄 의+1 은 capacity 로 한 공간 을 낭비 해 야 하기 때문에 실례 화 는 1 을 더 하 는 것 이다.

 data = (E[]) new Object[capacity + 1];//       

(2)지 24 줄 의 진정한 용량 은 data.length-1 인 데 이것 은 공간 이 낭비 되 기 때문이다.

data.length - 1;

(3)입단 중 46 번 째 줄 tail 값 에 대한 설명
입대 가 순환 작업 임 을 보장 하기 위해 tail 값 의 변화 규칙 은?

 tail = (tail + 1) % data.length;

(4)82 줄 의 데이터 이전 작업 에 대해 나머지 작업 은 순환 배열 의 경 계 를 넘 는 것 을 방지 하기 위해 서 이다.

  newData[i] = data[(front + i) % data.length];//        

\#3 은 LoopQueue 에 main 함 수 를 직접 추가 하여 테스트 합 니 다.관련 코드 는 다음 과 같 습 니 다.

  //    
  public static void main(String[] args) {
    LoopQueue<Integer> queue = new LoopQueue<Integer>();
    for (int i = 0; i < 10; i++) {
      queue.enqueue(i);
      System.out.println(queue);

      if(i%3==2){//   3        
        queue.dequeue();
        System.out.println(queue);
      }

    }

  }

결 과 는:
 
4.순환 대기 열 시간 복잡 도

여기 서 우 리 는 순환 대기 열 작업 을 실현 하여 순서 대기 열 에서 팀 을 나 갈 때의 시간 복잡 도가 O(n)인 상황 을 해결 하고 순환 대기 열 에서 팀 을 나 갈 때의 시간 복잡 도 는 O(1)이다.
원본 주소
자바 알고리즘 과 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.