자바 데이터 구조 - 대기 열, 우선 순위 대기 열
22307 단어 기타
대기 열 과 스 택 은 배열 에 대한 작업 을 밀봉 한 것 입 니 다.
두 개의 좌표 로 실현 (삽입 후, 삭제 후) 하여 선 입 선 출 을 실현 하고, 한 좌 표 는 선 입 후 출 만 을 가리킨다.
1. 대기 열: 스 택 의 상황 과 달리 대기 열 에 있 는 데이터 항목 은 항상 배열 아래 표 시 된 0 에서 시작 되 지 않 습 니 다. 데이터 항목 을 제거 한 후에 팀 헤드 포인터 가 아래 표 시 된 비교적 높 은 데이터 항목 을 가리 키 고 그 특징: 먼저 들 어가 서 먼저 나 옵 니 다.
2. 도해
3. 대기 열의 구현 코드:
3.1.Queue.java
1 package com.cn.queue;
2 /**
3 *
4 * @author Administrator
5 *
6 */
7 public class Queue {
8 private int maxsize;
9 private long[] queuearray;
10 private int front;
11 private int rear;
12 private int nItems;
13 public Queue(int s){
14 maxsize = s;
15 queuearray = new long[maxsize];
16 front = 0; ---
17 rear = -1; ---
18 nItems = 0; ---
19 }
20 public void insert(long j){
21 if (rear == maxsize - 1) ---
22 rear = -1;
23 queuearray[++ rear] = j;
24 nItems ++;
25 }
26 public long remove(){
27 long temp = queuearray[front ++];
28 if (front == maxsize) ---
29 front = 0;
30 nItems --;
31 return temp;
32 }
33 public long peekFront(){
34 return queuearray[front];
35 }
36 public boolean isEmpty(){
37 return (nItems == 0);
38 }
39 public boolean isFull(){
40 return (nItems == maxsize);
41 }
42 public int size(){
43 return nItems;
44 }
45
46 }
3.2.QueueTest.java
1 package com.cn.queue;
2
3 public class QueueTest {
4 public static void main(String[] args) {
5 Queue q = new Queue(100);
6 q.insert(100);
7 q.insert(200);
8 q.insert(300);
9 while (q.size()!=0){
10 System.out.print(q.remove()+" ");
11 }
12 System.out.println("");
13 System.out.println(q.isEmpty());
14 }
15 }
4. 대기 열 삽입 과 삭 제 된 시간 복잡 도 는 스 택 과 마찬가지 로 O (1) 입 니 다.
5. 우선 순위 대기 열: 우선 순위 대기 열 은 스 택 과 대기 열 보다 더 전용 적 인 데이터 구조 입 니 다. 그 는 한 팀 의 머리 와 팀 의 끝 이 있 고 팀 의 머리 에서 데이터 항목 을 제거 하지만 우선 순위 대기 열 에서 데이터 항목 은 키워드 의 값 에 따라 질서 가 있 습 니 다. 그러면 키워드 의 가장 작은 데이터 항목 은 항상 팀 의 머리 에 있 고 가장 큰 것 은 팀 의 끝 에 있 습 니 다.삽입 작업 을 할 때 대기 열의 순 서 를 확보 하기 위해 순서대로 적당 한 위치 에 삽입 합 니 다.최소 관건 값 의 데이터 항목 에 빠르게 접근 할 수 있 는 것 을 제외 하고 우선 대기 열 은 데이터 항목 을 매우 빨리 삽입 해 야 합 니 다. 따라서 우선 순위 대기 열 은 보통 쌓 인 데이터 구조 로 이 루어 집 니 다.이 프로그램 은 잠시 배열 을 사용 하여 이 루어 집 니 다. 이 실현 의 삽입 이 비교적 느 리 고 데이터 양 이 적 으 며 속도 에 대한 요구 가 높 지 않 습 니 다.
6. 우선 순위 대기 열의 실현:
6.1.PriorityQ.java
1 package com.cn.queue;
2 /**
3 *
4 * @author Administrator
5 *
6 */
7 public class PriorityQ {
8 private int maxsize;
9 private long[] queuearray;
10 private int nItems;
11 public PriorityQ(int s){
12 maxsize = s;
13 queuearray = new long[maxsize];
14 nItems = 0;
15 }
16 public void insert(long item){
17 int k;
18 if (nItems == 0)
19 queuearray[nItems ++] = item;
20 else{
21 for(k = nItems - 1;k >= 0;k --){
22 if (item > queuearray[k])
23 queuearray[k + 1] = queuearray[k];
24 else
25 break;
26 }
27 queuearray[k + 1] = item;
28 nItems ++;
29 }
30 }
31 public long remove(){
32 return queuearray[-- nItems];
33 }
34 public long peekmin(){
35 return queuearray[nItems - 1];
36 }
37 public boolean isEmpty(){
38 return (nItems == 0);
39 }
40 public boolean isFull(){
41 return (nItems == maxsize);
42 }
43 }
6.2 도해
7. 우선 순위 대기 열의 효율: 작업 시간 복잡 도 비트 O (N) 를 삽입 하고 작업 시간 복잡 도 를 O (1) 로 삭제 하 며 후속 데이터 구 조 는 그 를 개선 할 것 입 니 다.
참고:
https://www.cnblogs.com/g177w/p/8444750.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
요구사항 정의요구사항 정의 작성 방법 개요 ・목적 표시되고 있는 텍스트를 가변으로 한다 · 과제 표시된 텍스트가 변경되지 않음 ・해결 표시되고 있는 텍스트가 가변이 된다 사양 · 표시 정의 각 편집 화면 ○○ 표시되고 있는 텍스...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.