이 편 을 다 보고 도 너 는 아직 이 대열 들 을 모 르 니, 나 는 이 그림 들 을 헛되이 만 들 었 다.
11292 단어 우선 순위 대기 열대열데이터 구조
대열 에는 두 가지 중요 한 개념 이 있 는데 하 나 는 팀 의 머리 라 고 하고 하 나 는 팀 의 꼬리 라 고 하 며 팀 의 머리 는 첫 번 째 요 소 를 가리 키 고 팀 의 꼬리 는 마지막 요 소 를 가리킨다.대기 열 은 스 택 과 마찬가지 로 접근 이 제한 되 어 있 기 때문에 대기 열 도 두 가지 주요 동작 만 있 습 니 다. 입 대 (enqueue) 작업 과 출 대 (dequeue) 작업 입 니 다.입단 작업 은 하나의 요 소 를 팀 의 끝 에 추가 하 는 것 이 고, 팀 에서 나 오 는 작업 은 팀 의 머리 에서 하나의 요 소 를 꺼 내 는 것 이다.
대기 열 의 바 텀 실현 은 배열 과 링크 를 사용 할 수 있 습 니 다. 배열 을 바탕 으로 하 는 대기 열 을 순서 대기 열 이 라 고 부 릅 니 다. 링크 를 바탕 으로 하 는 대기 열 을 체인 대기 열 이 라 고 부 릅 니 다. 다음은 배열 과 링크 로 이 두 가지 대기 열 을 간단하게 실현 합 니 다.
배열 기반 대기 열
그런 방식 으로 대열 을 실현 하 든 두 개의 지침 이 각각 팀 의 머리 와 팀 의 꼬리 를 가리 키 는 것 을 정의 해 야 한다. 본 고 에서 우 리 는
head 으로 팀 의 머리 를 가리 키 고 tail 팀 의 꼬리 를 가리 키 며 뒤의 예제 에서 이것 을 기본 으로 사용 할 것 이다. 특별한 부분 이 있 으 면 내 가 설명 할 것 이다. 먼저 순서 대열 의 입 대 · 출 대 조작 을 살 펴 보 자.그림 에서 알 수 있 듯 이 팀 에 들 어 갈 때 팀 의 꼬리 는 뒤로 이동 하고 팀 의 머리 는 변 하지 않 으 며 팀 의 머리 는 뒤로 이동 하고 팀 의 꼬리 는 변 하지 않 는 다.팀 에 들 어가 거나 팀 을 나 가 조작 하 는 논 리 는 모두 비교적 간단 하 다. 아마도 당신 이 의문 이 있 는 것 은 팀 을 나 갈 때 왜 팀 의 머리 가 배열 아래
0 로 표 시 된 위 치 를 가리 키 지 않 고 뒤로 이동 해 야 하 는 지 하 는 것 일 것 이다.왜 일 까요?만약 에 우리 가 팀 의 머리 가 배열 아래 0 로 표 시 된 위 치 를 계속 가리 키 면 팀 에서 작업 할 때마다 뒤의 데 이 터 는 한 자 리 를 앞으로 옮 겨 야 한다. 다시 말 하면 팀 에서 작업 할 때마다 데이터 이전 을 해 야 하고 데이터 이전 의 대가 가 비교적 크다. 매번 데이터 이전 의 시간 복잡 도 는 O (n) 이 므 로 대열 의 사용 성능 에 큰 영향 을 줄 수 있다.만약 에 우리 가 팀 을 나 갈 때 팀 의 머리 가 한 명 뒤로 이동 하면 우 리 는 팀 을 나 갈 때마다 데이터 이전 을 하지 않 을 것 이다. 우 리 는 tail 이 배열 의 크기 와 head 가 같 지 않 을 때 만 데이터 이전 을 하고 이미 팀 을 나 와 남 긴 공간 을 계속 팀 에 들 어 갈 때 사용 해 야 한다.다음 그림 은 데이터 이동 과정 입 니 다.데이터 가 이동 할 때
0 위치 에서 시 작 된 데 이 터 는 모두 앞으로 이동 head 해 야 한다. 그러면 팀 에서 나 온 후의 공간 을 비 워 서 후속 입대 작업 에 사용 할 수 있다.배열 기반 대기 열 구현 코드:
/**
*
*/
public class ArrayQueue {
//
private String[] items;
//
private int size = 0;
//
private int head = 0;
//
private int tail = 0;
//
public ArrayQueue(int size){
this.size = size;
items = new String[size];
}
/**
*
* @param data
* @return
*/
public int enqueue(String data){
// ，
/**
* ，tail = size,head = 0,
*/
if (tail == size && head == 0) return -1;
/**
* tail = size， head != 0, ， ，
*/
if (tail == size){
// head head
for (int i= head;i< size;i++){
items[i-head] = items[i];
}
// head
tail -=head;
// 0
head = 0;
}
//
items[tail] = data;
tail++;
return 1;
}
/**
*
* @return
*/
public String dequeue(){
// ，
if (head == tail) return null;
String result = items[head];
// ，
head ++ ;
return result;
}
}체인 큐
체인 대기 열 이 실현 되 는 것 은 상대 적 으로 순서 대기 열 에 있어 서 매우 간단 하 다. 우 리 는 먼저 체인 대기 열의 입대, 출 대 조작 을 살 펴 보 자.
그림 에서 알 수 있 듯 이 체인 대열 의 입단 작업 은
head 의 tail 을 새로 추 가 된 노드 를 가리 키 고 next 을 새로 추 가 된 노드 를 가리 키 며 팀 을 나 갈 때 tail 노드 를 head 노드 로 가리킨다.체인 대기 열 은 순서 대기 열 에 비해 데이터 의 이전 이 필요 하지 않 지만 체인 대기 열 은 저장 원 가 를 증가 시 켰 다.링크 기반 대기 열 구현 코드
/**
*
*/
public class LinkQueue {
//
private Node head;
//
private Node tail;
/**
*
* @param data
* @return
*/
public int enqueue(String data){
Node node = new Node(data,null);
//
if (tail == null) {
tail = node;
head = node;
}else {
tail.next = node;
tail = node;
}
return 1;
}
/**
*
* @return
*/
public String dequeue(){
if (head==null) return null;
String data = head.data;
head = head.next;
// ， ， ，tail
if (head == null){
tail = null;
}
return data;
}
class Node{
private String data;
private Node next;
public Node(String data,Node node){
this.data = data;
next = node;
}
}
}순환 대기 열
순환 대기 열 은 순서 대기 열 에 대한 개선 입 니 다. 순서 대기 열 이 데이터 이전 작업 을 피 할 수 없 기 때문에 데이터 이전 작업 은 대기 열의 성능 을 떨 어 뜨 릴 수 있 습 니 다. 이 문 제 를 피하 기 위해 대기 열 을 순환 으로 바 꾸 었 습 니 다.
head.next 배열 의 최대 아래 표 시 를 도 착 했 을 때 배열 아래 표 시 된 tail 위 치 를 다시 가리 키 면 데이터 이전 을 피 할 수 있 습 니 다.먼저 순환 대열 의 출 대, 입 대 조작 을 살 펴 보 자.대열 은 순환 대열 이기 때문에 입 대 · 출 대 작업 을 할 때 순서 대열 처럼
0, tail 에 대해 간단 한 더하기 head 조작 을 할 수 없다. 우 리 는 1, tail 더하기 head 후 배열 의 크기 와 나머지 조작 을 해서 1, tail 의 값 을 얻어 야 순환 작업 을 할 수 있다.순환 대기 열 은 하나의 저장 공간 을 희생 해 야 합 니 다. 하나의 저장 공간 head 인 순환 대기 열 에 서 는 데이터 n 만 저장 할 수 있 습 니 다. 하나의 저장 공간 을 희생 하지 않 으 면 n-1 팀 이 비어 있 거나 팀 이 꽉 찬 상황 이 존재 할 수 있 기 때 문 입 니 다.순환 대기 열의 실현 코드
/**
* , ，
*/
public class CircularQueue {
//
private String[] items;
//
private int size = 0;
//
private int head = 0;
//
private int tail = 0;
//
public CircularQueue(int size){
this.size = size;
items = new String[size];
}
/**
*
* @param data
* @return
*/
public int enqueue(String data){
/**
* ，(tail+1) head
*/
if ((tail+1)%size == head) return -1;
//
items[tail] = data;
// ，
tail= (tail+1)%size;
return 1;
}
/**
*
* @return
*/
public String dequeue(){
// ，
if (head == tail) return null;
String result = items[head];
// ，
head = (head+1)% size ;
return result;
}
}양 끝 대기 열
2 단 대기 열 은 팀 의 머리, 팀 의 끝 에서 모두 입 대 · 출 대 작업 을 할 수 있 는 대기 열 로 2 단 대기 열 은 양 방향 링크 로 이 루어 집 니 다. 먼저 2 단 대기 열의 입 대 · 출 대 작업 을 살 펴 보 겠 습 니 다.
동적 그림 에서 볼 수 있 듯 이 양 끝 대기 열의 모든 끝 은 하나의 스 택 이 고 스 택 이 선진 적 인 후에 나 오 는 특성 에 부합 합 니 다. 만약 에 우리 가 양 끝 대기 열 에 대해 팀 의 입 대 를 금지 하고 팀 의 꼬리 에서 나 오 는 작업 을 제한 하면 양 끝 대기 열 은 하나의 체인 대기 열 이 되 었 습 니 다. 양 끝 대기 열 은 다기 능 데이터 구조 이 므 로 우 리 는 이 를 사용 하여 대기 열과 스 택 두 가지 기능 을 제공 할 수 있 습 니 다.
2 단 대기 열의 실현 코드
/**
* ，
*/
public class DoubleEndsQueue {
private static class Node {
String item;
Node next;
Node prev;
Node(Node prev, String element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
//
private Node first;
//
private Node last;
/*
*
*/
public void enqueueFirst(String e) {
final Node f = first;
final Node newNode = new Node(null, e, f);
//
first = newNode;
if (f == null)
//
last = newNode;
else
//
f.prev = newNode;
}
/**
*
* @param e
*/
public void enqueueLast(String e) {
final Node l = last;
final Node newNode = new Node(l, e, null);
//
last = newNode;
if (l == null)
//
first = newNode;
else
//
l.next = newNode;
}
/**
*
* @return
*/
public String dequeueFirst() {
if (first == null) return null;
final Node f = first;
String element = f.item;
Node next = f.next;
f.item = null;
f.next = null;
// next
first = next;
if (next == null)
//
last = null;
else
next.prev = null;
return element;
}
/**
*
* @return
*/
public String dequeueLast() {
final Node l = last;
if (last == null) return null;
String element = l.item;
Node prev = l.prev;
l.item = null;
l.prev = null;
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
return element;
}
//
public void displayAll() {
while (first !=null){
System.out.print(first.item+" ");
first = first.next;
}
System.out.println("===============");
}
}
우선 순위 대기 열
우선 대기 열 은 대기 열 이 먼저 나 가 는 (FIFO) 특성 을 따 르 지 않 아 도 되 는 특수 대기 열 입 니 다. 우선 대기 열 은 일반 대기 열 과 마찬가지 로 한 팀 의 머리 와 한 팀 의 꼬리 만 있 고 팀 의 머리 에서 나 가 고 팀 의 꼬리 에서 들 어 갑 니 다. 그러나 우선 대기 열 에 들 어 갈 때마다 입 대 된 데이터 항목 의 관건 값 에 따라 정렬 합 니 다 (큰 것 에서 작은 것, 작은 것 에서 큰 것 까지).이렇게 하면 키워드 가 가장 작 거나 가장 큰 항목 은 항상 팀 에 있 고 팀 을 나 갈 때 우선 순위 가 가장 높 은 사람 이 가장 먼저 팀 을 나 갈 수 있 습 니 다. 이것 은 우리 병원 에서 치 료 를 받 는 것 처럼 응급 환 자 는 일반 환자 보다 먼저 진 료 를 받 아야 합 니 다.우선 대열 의 출 대, 입 대 를 함께 살 펴 보 자.
예 를 들 어, 우 리 는 수치 가 작 을 수록 우선 순위 가 높다 고 규정 한다.우리 가 팀 에 들 어 갈 때마다 작은 요 소 는 첫 번 째 팀 에 가 까 워 지고 팀 을 나 갈 때 요소 가 작은 것 도 먼저 팀 을 나 간다.
우선 대기 열의 코드 구현
여기 서 사용 하 는 배열 은 우선 대기 열 을 실현 하고 배열 로 실현 하 는 주요 원인 은 우선 대기 열의 사상 을 잘 이해 하 는 것 이다.일반적으로 무 더 기 를 사용 하여 우선 대기 열 을 실현 합 니 다. 배열 이 삽입 할 때 데이터 에 대한 정렬 대가 가 비교적 크기 때 문 입 니 다.
/**
*
*/
public class PriorityQueue {
//
private Integer[] items;
//
private int size = 0;
//
private int head = 0;
//
public PriorityQueue(int size){
this.size = size;
items = new Integer[size];
}
/**
*
* @param data
* @return
*/
public int enqueue(Integer data){
int j;
if (head == 0){
items[head++] = data;
}
else {
for (j=head-1;j>=0;j--){
//
if (data > items[j]){
items[j+1] = items[j];
}else {
break;
}
}
items[j+1] = data;
head++;
}
return 1;
}
public Integer dequeue(){
return items[--head];
}
}총결산
마지막.
작은 광 고 를 하 겠 습 니 다. 스 캔 코드 가 위 챗 의 대중 번호 에 관심 을 가 지 는 것 을 환영 합 니 다. '평 두 형의 기술 박문', 같이 발전 합 시다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
색인 우선 대기 열: 최소 색인 우선 대기 열많은 응용 프로그램 에서 우선 대기 열 에 있 는 데 이 터 를 참조 할 수 있 습 니 다. 우 리 는 이러한 데이터 구 조 를 최소 요소 에 빠르게 접근 할 수 있 는 배열 로 볼 수 있 습 니 다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
