자바 배열 시 뮬 레이 션 우선 순위 대기 열 데이터 구조의 인 스 턴 스

우선 순위 대기 열 이 모든 요소 에 하나의 숫자 를 할당 하여 우선 순 위 를 표시 한다 면 작은 숫자 가 비교적 높 은 우선 순 위 를 가 집 니 다. 그러면 우 리 는 한 집합 에서 우선 순위 가 가장 높 은 요 소 를 방문 하여 이 를 찾 고 삭제 할 수 있 습 니 다.이렇게 해서 우 리 는 우선 순위 대기 열 이라는 데이터 구 조 를 도입 했다.우선 순위 대기 열 (priority quue) 은 0 개 이상 의 요소 의 집합 입 니 다. 모든 요 소 는 하나의 우선권 을 가지 고 있 습 니 다. 우선 순위 대기 열 에서 실 행 된 작업 은 (1) 검색 (2) 새 요 소 를 삽입 (3) 삭제 하 는 일반적인 상황 에서 검색 작업 은 우선권 이 가장 큰 요 소 를 검색 하고 삭제 작업 은 이 요 소 를 삭제 합 니 다.우선권 이 같은 요 소 는 선진 적 인 선착순 으로 처리 하거나 임 의 우선권 에 따라 진행 할 수 있다.
자바 배열 시 뮬 레이 션 대기 열 은 표 의 전단 에서 만 삭제 작업 을 할 수 있 고 표 의 백 엔 드 에 만 삽입 작업 을 할 수 있 는 특수 한 선형 표 입 니 다.삽입 작업 을 하 는 끝 을 팀 꼬리 라 고 하고 삭제 작업 을 하 는 끝 을 팀 머리 라 고 합 니 다.이것 이 바로 우리 가 평소에 자주 사용 하 는 선진 선 출 원칙 (FIFO) 이다.자바 의 List 는 대기 열 로 사용 할 수 있 으 며, 대기 열 끝 에 요 소 를 추가 하면 list. add 방법 을 사용 하고, 대기 열 머리 에서 요 소 를 삭제 하면 list. remove 방법 을 사용 합 니 다.
자바 배열 시 뮬 레이 션 우선 순위 대기 열 구조 인 스 턴 스:

package datastruct; 
 
import java.util.Arrays; 
import java.util.Comparator; 
 
/** 
 *                    、         
 *           TreeSet、TreeMap 
 */ 
public class SimulatePriorityQueue { 
   
  public static void main(String[] args) { 
    SimulatePriorityQueue queue = new SimulatePriorityQueue(4); 
//   SimulateQueue queue = new SimulateQueue(); 
//   System.out.println("    ：" + queue.remove()); 
    queue.insert(1); 
    queue.insert(3); 
    queue.insert(2); 
    queue.insert(5); 
    queue.insert(4); 
    System.out.println("size:" + queue.size()); 
    System.out.println("peek:" + queue.peek()); 
    System.out.println("    ：" + queue.remove()); 
    System.out.println("    ：" + queue.remove()); 
    System.out.println("    ：" + queue.remove()); 
    System.out.println("    ：" + queue.remove()); 
//   System.out.println("    ：" + queue.remove()); 
    System.out.println("size:" + queue.size()); 
    System.out.println(); 
  } 
 
  private int mSize = 3;     //   
  private int[] mArray;    //   
  private int mNextItem;     //     ，            
   
  public SimulatePriorityQueue() { 
    mArray = new int[mSize]; 
    mNextItem = 0; 
  } 
  public SimulatePriorityQueue(int size) { 
    this.mSize = size; 
    mArray = new int[mSize]; 
    mNextItem = 0; 
  } 
  /** 
   *      
   * @param item 
   */ 
  public void insert(int item) { 
    if (!isFull()) { 
      mArray[mNextItem++] = item; 
      for (int i = 0; i < mNextItem; i++) {//     
        for (int j = 0; j < mNextItem - 1; j++) { 
          if (mArray[j] > mArray[j + 1]) { 
            mArray[j] = mArray[j + 1] + 0 * (mArray[j + 1] = mArray[j]); 
            System.out.println(Arrays.toString(mArray)); 
          } 
        } 
      } 
      System.out.println(Arrays.toString(mArray)); 
    } else { 
      System.out.println("----       ，    ----"); 
    } 
  } 
  /** 
   *           
   * @return 
   */ 
  public int remove() { 
    if (!isEmpty()) { 
      return mArray[--mNextItem]; 
    } else { 
      throw new IllegalArgumentException("         "); 
    } 
  } 
  /** 
   *         
   * @return 
   */ 
  public int peek() { 
    return mArray[mNextItem - 1]; 
  } 
  /** 
   *      
   * @return 
   */ 
  public boolean isEmpty() { 
    return mNextItem == 0; 
  } 
  /** 
   *     
   * @return 
   */ 
  public boolean isFull() { 
    return mNextItem == mSize; 
  } 
  /** 
   * size 
   * @return 
   */ 
  public int size() { 
    return mNextItem; 
  } 
   
} 

출력 결과:

[1, 0, 0, 0]
[1, 3, 0, 0]
[1, 2, 3, 0]
[1, 2, 3, 0]
[1, 2, 3, 5]
----       ，    ----
size:4
peek:5
    ：5
    ：3
    ：2
    ：1
size:0