Java 대기열 구현 원리
"큐"라는 단어는 영국이 "대기열"이라고 부르는 것입니다. 영국의 "천장"은 연속으로 서있는 것을 의미합니다. 컴퓨터 과학에서 큐는 데이터 구조이며, 큐에 삽입 된 첫 번째 데이터 항목이 먼저 제거되고 스택에서 삽입 된 마지막 데이터 항목이 먼저 제거된다는 점을 제외하고는 스택과 비슷합니다. 대기열은 영화관 앞에 서있는 사람들의 행처럼 작동합니다. 제휴사에 들어가는 첫 번째 사람은 팀의 머리에 도착하여 티켓을 구매합니다. 줄을서는 마지막 사람은 티켓을 살 수 있습니다.
대기열은 스택과 같은 프로그래머를위한 도구로도 사용됩니다. 또한 은행에서 기다리는 사람들을 시뮬레이션, 이륙을 기다리는 비행기 또는 인터넷 패킷이 전송되기를 기다리는 등 실제 환경을 시뮬레이션하는 데 사용될 수 있습니다.
컴퓨터 운영 체제에서는 다양한 줄이 조용히 작동하고 있습니다. 인쇄 작업은 인쇄 대기열에서 인쇄를 기다리고 있습니다. 키보드에 입력 할 때는 입력을 저장하는 대기열도 있습니다. 마찬가지로, 워드 프로세서를 사용하여 키가 탭되고 컴퓨터가 일시적으로 다른 작업을 수행 해야하는 경우, 탭핑 된 컨텐츠가 손실되지 않으며 Word 프로세서가 읽을 시간이있을 때까지 대기열에서 대기합니다. 큐는 처리시 타이핑 순서가 변경되지 않도록하는 데 사용됩니다.
대기열의 기본 작업
대기열의 두 가지 기본 작업은 데이터 항목을 삽입 (삽입)하고, 즉 하나의 데이터 항목을 큐의 꼬리에 넣고 다른 데이터 항목을 데이터 항목을 제거 (제거)하여 팀의 헤드의 데이터 항목을 제거하는 것입니다. 이것은 티켓을 구매하기 위해 대기열을 깎을 때 영화 애호가들이 줄 끝까지 대기하는 것과 유사합니다. 그런 다음 줄의 머리에 도착한 다음 대기열을 남겨 둡니다.
스택에 데이터 항목을 삽입하고 제거하는 방법의 이름은 Push and Pop이라는 매우 표준입니다. 큐 메소드는 지금까지 표준화되지 않았습니다. "삽입"을 put, add 또는 enque라고 할 수 있으며 "삭제"는 삭제, get 또는 deque라고 할 수 있습니다. 삽입 데이터 항목의 끝을 다시, 꼬리 또는 끝을 호출 할 수도 있습니다. 데이터 항목을 제거하는 팀장은 헤드라고도합니다. 삽입, 제거, 전면 및 후면은 아래에서 사용됩니다.
삽입 값을 큐의 꼬리에 삽입하면 큐 화살표의 꼬리가 새 데이터 항목을 가리키도록 추가됩니다.
데이터 항목을 제거한 후 팀의 헤드가 추가됩니다. 일반적으로 큐를 구현할 때 삭제 된 데이터 항목은 메모리에 저장되지만 큐 헤드가 다음 위치로 이동했기 때문에 액세스 할 수 없습니다.
스택의 경우와 달리 큐의 데이터 항목이 항상 배열의 0 첨자에서 시작되는 것은 아닙니다. 일부 데이터 항목을 제거한 후 헤더 포인터는 더 높은 첨자 위치를 가리 킵니다.
View Operation은 헤더 데이터 항목의 값을 반환하지만 팀에서 데이터 항목을 삭제하지는 않습니다.
빈 큐에서 데이터 항목을 제거하거나 데이터 항목을 전체 대기열에 삽입하려면 응용 프로그램이 오류 메시지가 표시됩니다.
루프 대기열
새 데이터 항목이 큐에 삽입되면 팀 헤드의 후면 화살표가 배열 첨자의 큰 위치를 향해 위쪽으로 이동합니다. 데이터 항목을 제거 할 때 큐 전면 포인터의 꼬리도 위쪽으로 이동합니다. 이 디자인은 사람들의 직접 관찰에 위배 될 수 있습니다. 사람들이 영화 티켓을 위해 줄을 서서 대기열이 항상 앞으로 나아가고, 그 앞에있는 사람이 티켓을 사고 대기열을 떠나면 다른 사람들은 앞으로 나아갑니다. 컴퓨터의 대기열에서 데이터 항목을 삭제 한 후 다른 모든 데이터 항목을 앞으로 이동할 수도 있지만 매우 효율적입니다. 대신, 우리는 대기열의 머리와 꼬리 포인터의 움직임을 통해 모든 데이터 항목을 동일하게 유지합니다.
이 디자인의 문제점은 테일 포인터가 배열 끝으로 빠르게 이동한다는 것입니다. 배열 시작 부분에는 제거 된 데이터 항목의 위치 인 빈 데이터 항목 장치가 있지만 테일 포인터는 더 이상 뒤로 이동할 수 없으므로 새 데이터 항목을 삽입 할 수 없습니다. 어떻게해야하나요?
마무리 처리
대기열이 불만족 스럽지만 새로운 데이터 항목을 삽입 할 수없는 문제를 피하기 위해 헤드와 테일 포인터를 배열의 시작 부분으로 되돌릴 수 있습니다. 이것은 루프 큐입니다 (때로는 "버퍼 링"이라고도합니다).
포인터 랩핑 프로세스 : 테일 포인터가 배열 후반을 가리 키도록 충분한 데이터 항목을 큐에 삽입하십시오. 배열의 프론트 엔드에 몇 가지 더 데이터 항목을 삭제하십시오. 이제 새 데이터 항목을 삽입하십시오. 테일 포인터가 끝에서 시작 위치로 역전 될 것임을 알 수 있습니다. 이 위치에 새로운 데이터 항목이 삽입됩니다.
더 많은 데이터 항목을 삽입하십시오. 테일 포인터는 예상대로 위로 움직입니다. 테일 포인터가 되감기를 한 후에는 이제 헤드 포인터 아래로 초기 위치를 되돌립니다. 이것을 "파손 시퀀스"라고 할 수 있습니다. 큐의 데이터 항목은 배열의 두 가지 시퀀스로 표시됩니다.
충분한 데이터 항목을 삭제 한 후 팀장도 마무리합니다. 현재 큐 포인터는 초기 런타임에서 위치 상태로 돌아오고 헤드 포인터는 테일 포인터 아래에 있습니다. 데이터 항목은 또한 단일 연속 시퀀스로 복원됩니다.
대기열에 대한 Java 코드
queue.java 프로그램은 insert (), remove (), peek (), isempty () 및 size () 메소드가있는 큐 클래스를 만듭니다.
패키지 스택 및 대기열;
클래스 큐 {private int maxsize; 개인 Long [] QuearRay; 개인 int 전선; 개인 int 후면; 개인 intems; 공개 큐 (int s) {maxsize = s; QuearRay = New Long [maxSize]; 전면 = 0; 후면 = -1; nitems = 0; } public void insert (long j) {if (rear == maxsize-1) rear = -1; QuearRay [++ 후면] = J; nitems ++; } public long remove () {long temp = QuearRay [Front ++]; if (front == maxsize) front = 0; nitems--; 반환 온도; } public long peekfront () {return QuearRay [Front]; } public boolean isempty () {return (nitems == 0); } public boolean iffull () {return (nitems == maxSize); } public int size () {return nitems; }}이 프로그램에 의해 구현 된 큐 클래스에는 전면 (헤드) 및 후면 (팀의 헤드) 필드뿐만 아니라 큐의 현재 데이터 항목 수가 있습니다 : nitems.
insert () 메소드 의 작동을위한 전제 조건은 큐가 만족스럽지 않다는 것입니다. 이 메소드는 main ()에 표시되지 않지만 insert () 메소드는 일반적으로 먼저 호출되고 false를 반환 한 후에 isfull () 메소드를 호출해야합니다. (보다 일반적인 접근법은 큐가 가득 찬지 여부를 확인하기 위해 insert () 메소드에 판단을 추가하는 것입니다. 데이터 항목이 전체 대기열에 삽입되면 예외가 발생됩니다.)
일반적으로 삽입 작업은 후면 (팀 테일 포인터)을 추가하고 테일 포인터가 가리키는 위치에 새 데이터를 삽입하는 것입니다. 그러나 후면 포인터가 배열의 상단, 즉 MaxSize-1 위치를 가리키면 데이터 항목을 삽입하기 전에 배열의 하단으로 다시 상처를 입어야합니다. 와인딩 작업은 후면을 -1로 설정하므로 후면이 추가되면 1이 추가되면 0과 같으며 배열의 하단의 첨자 값이며 마지막으로 Nitem이 추가됩니다.
제거 () 메소드 의 작동을위한 전제 조건은 큐가 비어 있지 않다는 것입니다. 이 메소드를 호출하기 전에 큐가 비어 있지 않도록 isempty () 메소드를 호출 하거나이 오류 확인 메커니즘을 remove () 메소드에 추가해야합니다.
제거 작업은 항상 전면 포인터에서 헤더 데이터 항목의 값을 가져온 다음 전면을 추가합니다. 그러나 전면 값이 배열의 상단을 초과하는 경우, 전면은 배열의 첨자가 0 인 위치로 돌아 가야합니다.이 테스트를 수행하는 동안 반환 값이 일시적으로 저장됩니다. 마지막으로 Nitem은 하나씩 감소합니다.
Peek () 메소드는 간단하고 이해하기 쉽습니다. 전면 포인터가 가리키는 데이터 항목의 값을 반환합니다. 일부 대기열 구현은 또한 큐 엔드 데이터 항목의 값을 볼 수 있습니다. 예를 들어, 이러한 메소드는 peekfront (), peekRear () 또는 Front () 및 rear ()라고 할 수 있습니다.
isempty (), isfull () 및 size () 메소드 의 구현은 모두 nitems 필드에 의존하며, 이는 nitems가 0과 동일 여부, 최대 크기와 같거나 자체 값을 반환하는지 여부를 반환합니다.
큐 클래스에 데이터 항목 계산 필드를 포함하여 큐 클래스에 insert () 및 remove () 메소드가 각각이 변수의 값을 증가시키고 감소시켜야하기 때문에 큐 클래스에 삽입 () 메소드에 약간의 추가 작업이 추가됩니다. 이것은 여분의 오버 헤드가 아닐 수도 있지만 많은 삽입 및 제거 작업을 처리하면 성능에 영향을 줄 수 있습니다.
일부 대기열 구현은 데이터 항목 계산 필드를 사용하지 않지만 전면 및 후면을 사용하여 대기열이 비어 있는지 또는 전체 데이터 항목 수와 데이터 항목 수를 계산하십시오. 이렇게하면 isempty (), iffull () 및 size () 루틴은 앞에서 언급했듯이 데이터 항목의 시퀀스가 두 세그먼트 또는 연속 세그먼트로 무너지기 때문에 상당히 복잡합니다.
그리고 이상한 문제가 발생했습니다. 대기열이 가득 차면 전면 및 후면 포인터가 특정 위치를 취하지만 대기열이 비어 있으면 동일한 위치 관계가 나타날 수 있습니다. 동시에, 대기열이 가득 차 있거나 비어있는 것처럼 보일 수 있습니다. 이 문제에 대한 해결책은 다음과 같습니다. 배열 용량을 최대 큐 데이터 항목 수보다 하나 이상으로 만듭니다.
읽어 주셔서 감사합니다. 도움이되기를 바랍니다. 이 사이트를 지원 해주셔서 감사합니다!