데이터 구조 와 알고리즘 | 대기 열의 실현 및 응용
8098 단어 데이터 구조 와 알고리즘
앞에서 우 리 는 스 택 의 실현 과 응용 을 배 웠 습 니 다. 이 편 에서 우 리 는 마지막 선형 표 인 대열 을 배 웠 습 니 다.
대기 열 은 우리 가 일상 개발 에서 자주 사용 하 는 데이터 구조 로 우 리 는 대기 열 을 사용 하여 비동기 처리, 시스템 디 결합, 데이터 동기 화, 데이터 삭 봉, 버퍼, 흐름 제한 등 을 자주 사용 합 니 다.예 를 들 어 모든 업무 가 실시 간 으로 처리 되 어야 하 는 것 이 아니 라 모든 요구 가 실시 간 으로 결 과 를 사용자 에 게 피드백 해 야 하 는 것 이 아니 라 모든 요구 가 100% 성공 해 야 하 는 것 이 아니 라 누가 '나' 의 처리 결과 에 의존 하 는 지 모 르 고 다른 시스템 이 후속 업 무 를 어떻게 처리 하 는 지 에 관심 이 없고 강 한 일치 성 이 필요 하지 않 으 며 최종 일치 성 만 확보 하면 된다.데이터 처리 의 질서 성 을 확보 하려 면 이 문제 들 은 모두 대기 열 을 사용 하여 해결 하 는 것 을 고려 해 야 한다.
대열
정의.
대기 열 은 스 택 과 마찬가지 로 조작 이 제 한 된 선형 표 데이터 구조 입 니 다.대기 열 은 한 끝 에서 데 이 터 를 삽입 한 다음 다른 한 끝 에서 데 이 터 를 꺼 냅 니 다.데 이 터 를 삽입 하 는 한 끝 을 '팀 끝' 이 라 고 부 르 고 데 이 터 를 꺼 내 는 한 끝 을 '팀 머리' 라 고 부 릅 니 다. 그림 과 같 습 니 다.
특징.
스 택 과 마찬가지 로 대기 열 도 순서 대기 열 과 체인 대기 열 로 나 뉘 어 각각 배열 과 링크 를 사용 하여 이 루어 집 니 다.
체인 큐
체인 대기 열 실현 이 비교적 간단 합 니 다. 단일 체인 표를 사용 하면 실현 할 수 있 습 니 다. 만약 에 다음 과 같 으 면:
코드 구현
package one.wangwei.algorithms.datastructures.queue.impl;
import one.wangwei.algorithms.datastructures.queue.IQueue;
import java.util.NoSuchElementException;
/**
*
*
* @param
* @author https://wangwei.one
* @date 2019/03/27
*/
public class LinkedQueue implements IQueue {
private int size = 0;
private Node head;
private Node tail;
public LinkedQueue() {
}
/**
*
*
* @param value
* @return
*/
@Override
public boolean offer(T value) {
Node last = tail;
Node newNode = new Node<>(value, null);
tail = newNode;
if (last == null) {
head = newNode;
} else {
last.next = newNode;
}
size++;
return true;
}
/**
*
*
* @return
*/
@Override
public T poll() {
if (head == null) {
throw new NoSuchElementException("Queue underflow");
}
Node tmpHead = head;
head = head.next;
tmpHead.next = null;
size--;
if (head == null) {
tail = null;
}
return tmpHead.element;
}
/**
*
*
* @return
*/
@Override
public T peek() {
if (head == null) {
throw new NoSuchElementException("Queue underflow");
}
return head.element;
}
/**
*
*/
@Override
public void clear() {
for (Node x = head; x != null; ) {
Node next = x.next;
x.element = null;
x.next = null;
x = next;
}
head = tail = null;
size = 0;
}
/**
*
*/
@Override
public int size() {
return size;
}
/**
* Node
*
* @param
*/
private static class Node {
private T element;
private Node next;
private Node(T element) {
this.element = element;
}
private Node(T element, Node next) {
this.element = element;
this.next = next;
}
}
}
소스 코드
링크 의 실현 방식 을 바탕 으로 무한 대기 열 을 지원 하 는 무한 대기 열 (unbounded quue) 을 실현 할 수 있 으 나 너무 많은 요청 대기 열 을 초래 할 수 있 습 니 다. 요청 처리 응답 시간 이 너무 길 어 질 수 있 습 니 다.따라서 응답 시간 이 비교적 민감 한 시스템 에 대해 링크 를 바탕 으로 하 는 무한 줄 서 는 스 레 드 탱크 는 적합 하지 않다.
순서 대기 열
순서 대기 열 은 배열 로 이 루어 지고 배열 의 실현 은 두 가지 방식 이 있 으 며 하 나 는 순서 식 이 고 하 나 는 순환 배열 로 이 루어 진다.
순서 대기 열
대기 열 끝 에 남 은 공간 이 없 으 면 데이터 이전 공간 을 집중 적 으로 진행 해 야 입 대 를 계속 할 수 있 습 니 다.그림 에서 보 듯 이:
순환 대기 열
순서 대기 열 에 데이터 이전 문제 가 존재 하여 입대 작업 에 성능 적 인 영향 을 줄 수 있 습 니 다.우 리 는 순환 배열 의 방식 으로 이 문 제 를 해결 할 수 있다. 그림 과 같다.
팀 의 끝 에 저장 공간 이 없고 대기 열 이 가득 하지 않 을 때, 우 리 는 그것 을 배열 의 앞부분 에 남 은 공간 으로 저장 할 수 있다.
코드 구현
순환 대기 열의 실현 관건 은 대기 열 이 비어 있 고 만 료 되 었 을 때의 상태 판단 에 있다.
rear == front
front == (rear + 1) % array.length
대기 열 이 가득 찼 을 때 한 배열 의 저장 공간 을 낭비 합 니 다.코드 는 다음 과 같 습 니 다:
package one.wangwei.algorithms.datastructures.queue.impl;
import one.wangwei.algorithms.datastructures.queue.IQueue;
import java.util.NoSuchElementException;
/**
*
*
* @param
* @author https://wangwei.one
* @date 2019/02/04
*/
public class ArrayQueue implements IQueue {
/**
* default array size
*/
private static final int DEFAULT_SIZE = 1024;
/**
*
*/
private T[] array;
/**
*
*/
private int front = 0;
/**
*
*/
private int rear = 0;
public ArrayQueue() {
this(DEFAULT_SIZE);
}
public ArrayQueue(int capacity) {
array = (T[]) new Object[capacity];
}
/**
*
*
* @param value
* @return
*/
@Override
public boolean offer(T value) {
if (isFull()) {
grow();
}
array[rear % array.length] = value;
rear++;
return true;
}
/**
* grow queue size doubly
*/
private void grow() {
int growSize = array.length << 1;
T[] tmpArray = (T[]) new Object[growSize];
int adjRear = rear % array.length;
int endIndex = rear > array.length ? array.length : rear;
if (adjRear < front) {
System.arraycopy(array, 0, tmpArray, array.length - adjRear, adjRear + 1);
}
System.arraycopy(array, front, tmpArray, 0, endIndex - front);
array = tmpArray;
rear = (rear - front);
front = 0;
}
/**
*
*
* @return
*/
@Override
public T poll() {
if (isEmpty()) {
throw new NoSuchElementException("Queue underflow");
}
T element = array[front % array.length];
array[front % array.length] = null;
front++;
if (isEmpty()) {
// remove last element
front = rear = 0;
}
int shrinkSize = array.length >> 1;
if (shrinkSize >= DEFAULT_SIZE && size() < shrinkSize) {
shrink();
}
return element;
}
/**
*
*/
private void shrink() {
int shrinkSize = array.length >> 1;
T[] tmpArray = (T[]) new Object[shrinkSize];
int adjRear = rear % array.length;
int endIndex = rear > array.length ? array.length : rear;
if (adjRear <= front) {
System.arraycopy(array, 0, tmpArray, array.length - front, adjRear);
}
System.arraycopy(array, front, tmpArray, 0, endIndex - front);
array = null;
array = tmpArray;
rear = rear - front;
front = 0;
}
/**
*
*
* @return
*/
@Override
public T peek() {
if (isEmpty()) {
throw new NoSuchElementException("Queue underflow");
}
return array[front % array.length];
}
/**
*
*/
@Override
public void clear() {
array = null;
front = rear = 0;
}
/**
*
*/
@Override
public int size() {
return rear - front;
}
/**
*
*
* @return
*/
private boolean isFull() {
return !isEmpty() && (front == (rear + 1) % array.length);
}
/**
*
*
* @return
*/
private boolean isEmpty() {
return size() <= 0;
}
}
소스 코드
배열 을 기반 으로 한 경계 대기 열 (bounded quue) 은 대기 열의 크기 가 제한 되 어 있 습 니 다. 요청 수량 이 대기 열 을 초과 하면 다음 요청 이 거부 되 며, 이러한 방식 은 응답 시간 에 민감 한 시스템 에 있어 서 상대 적 으로 합 리 적 입 니 다.하지만 합 리 적 인 대기 열 크기 를 설정 하 는 것 도 중요 하 다.대기 열 이 너무 커서 대기 요청 이 너무 많 고 대기 열 이 너무 작 으 면 시스템 자원 을 충분히 이용 하지 못 하고 최대 성능 을 발휘 할 수 있 습 니 다.
참고 자료
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[JAVA] 배열 회전 출력요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.