자바 배열 대기 열 개념 및 용법 사례 분석

본 논문 의 사례 는 자바 배열 의 개념 과 용법 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
대열 의 개념 
(1)대열 도 일종 의 선형 구조 이다
(2)배열 에 비해 대기 열 에 대응 하 는 동작 은 배열 의 부분 집합 이다.
(3)한 끝 에 만 데 이 터 를 삽입 할 수 있 고 다른 한 끝 에서 데 이 터 를 삭제 하 는 작업 을 할 수 있 습 니 다.삽입 작업 을 하 는 한 끝 을 팀 끝(대기 열 에 들 어 가 는 것)이 라 고 하고 삭제 작업 을 하 는 한 끝 을 팀 머리(대기 열 밖으로 나 가 는 것)라 고 합 니 다.
(4)대기 열 은 선진 적 인 데이터 구조(FIFO)이다.
 여기 서 우선 순서 대열 을 배 워 보도 록 하 겠 습 니 다. ，순서 대기 열 바로 배열 로 이 루어 지 는 것 입 니 다.예 를 들 어 n 개의 요소 가 있 는 대기 열 입 니 다.배열 아래 에 0 을 표시 하 는 한 끝 은 팀 의 머리 입 니 다.가입 작업 은 배열 아래 에 표 시 된 순서대로 추가 하 는 것 입 니 다.요 소 를 이동 할 필요 가 없습니다.그러나 팀 의 머리 요 소 를 삭제 하면 뒤의 요 소 는 앞으로 이동 해 야 합 니 다.대응 하 는 시간 복잡 도 는 바로 O(n)입 니 다.

대기 열 에 대해 우리 가 주목 하 는 것 은 다음 과 같다.

코드 구현
이 절의 관련 코드 에 대해 서 는 패키지(Queue)를 새로 만 들 고 이해 하기 편 하도록 동적 배열 관련 코드 를 이 가방 에 복사 합 니 다.
1.먼저 Queue 인 터 페 이 스 를 만 들 고 위 에서 설명 한 방법 을 정의 합 니 다.

package Queue;

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

  //         
  boolean isEmpty();

  //   
  void enqueue(E e);

  //   
  E dequeue();

  //      
  E getFront();
}

2.클래스 Array Queue 를 만 들 고 Queue 인터페이스 와 Object 클래스 를 다시 쓰 는 toString()방법

package Queue;

public class ArrayQueue<E> implements Queue<E> {
  private DynamicArray<E> array;


  //    ，       capacity    
  public ArrayQueue(int capacity) {
    array = new DynamicArray<E>(capacity);
  }

  //      ，       capacity=10
  public ArrayQueue() {
    array = new DynamicArray<E>();
  }

  //             
  @Override
  public boolean isEmpty() {
    return array.isEmpty();
  }

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

  //       
  public int getCapacity() {
    return array.getCapacity();
  }

  //    
  @Override
  public void enqueue(E e) {
    array.addLast(e);
  }

  //    
  @Override
  public E dequeue() {
    return array.removeFirst();
  }

  //      
  @Override
  public E getFront() {
    return array.getFirst();
  }

  //  object  toString  
  @Override
  public String toString() {
    StringBuilder res = new StringBuilder();
    res.append("Queue:");
    res.append("front [");//       
    for (int i = 0; i < array.getSize(); i++) {
      res.append(array.get(i));
      if (i != array.getSize() - 1) {
        res.append(",");
      }
    }
    res.append("] tail");//       
    return res.toString();
  }
}

3.테스트
TestMain 클래스 를 새로 만 듭 니 다.우리 가 작성 한 Array Queue 클래스 를 테스트 하기 위해 main 함 수 를 추가 합 니 다.
관련 코드 는 다음 과 같 습 니 다.

package Queue;

public class TestMain {
  public static void main(String[] args) {
    ArrayQueue<Integer> queue = new ArrayQueue<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);
      }

    }

  }
}

7 번 째 줄 코드 는 대기 열 에 들 어 가 는 동작 을 테스트 하 는 것 입 니 다.10 번,11 번 째 줄 코드 는 3 개의 요 소 를 추가 할 때마다 하나의 요 소 를 출력 한 다 는 뜻 입 니 다.결 과 는:

3.배열 대열 의 복잡 도 분석

팀 을 나 가 는 시간의 복잡 도가 O(n)라 는 설명:
 배열 대기 열 을 실현 하 는 바 텀 은 동적 배열 이기 때문에 가입 작업 은 배열 아래 에 표 시 된 순서대로 추가 하 는 것 입 니 다.요 소 를 이동 할 필요 가 없 지만 팀 헤드 요소(removeFirst()방법)를 삭제 하면 뒤의 요 소 는 앞으로 이동 해 야 합 니 다.대응 하 는 시간 복잡 도 는 O(n)입 니 다.이렇게 하면 배열 에 대량의 데이터 가 있 을 때 성능 이 좋 지 않 을 것 이다.다음 절 에 우 리 는 개선 을 해서 팀 의 시간 복잡 도 를 O(1)로 만 들 것 이다.
원본 주소
자바 알고리즘 과 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.