Java 대기열 구현 원리 및 단순 구현 코드
'대열'이라는 단어는 영국인이 말한'배'다.영국에서 줄을 서라는 뜻은 한 줄에 서 있다는 것이다.컴퓨터 과학에서 대기열은 일종의 데이터 구조로 약간 유사한 창고이다. 단지 대기열에 첫 번째로 삽입된 데이터 항목도 가장 먼저 제거되고 창고에서 마지막으로 삽입된 데이터 항목이 가장 먼저 제거된다.대열의 역할은 영화관 앞에 있는 사람들이 줄을 서 있는 것과 같다. 첫 번째로 부속된 사람이 가장 먼저 대열에 도착해 표를 산다.마지막에 줄을 서 있는 사람이 마지막에야 표를 살 수 있다.
대기열은 창고와 마찬가지로 프로그래머의 도구로도 사용된다.그것도 실제 세계의 환경을 모의하는 데 쓰일 수 있다. 예를 들어 사람들이 은행에서 줄을 서서 기다리거나 비행기가 이륙을 기다리거나 인터넷에 데이터 패키지가 전송되기를 기다리는 것이다.
컴퓨터 운영체제에서 각종 대열이 조용히 일하고 있다.인쇄 작업은 인쇄 대기열에서 인쇄를 기다립니다.키보드를 두드릴 때도 입력한 내용을 저장하는 대기열이 있습니다.마찬가지로, 만약 워드프로세서로 키를 두드리고, 컴퓨터가 잠시 다른 일을 하려고 한다면, 두드리는 내용은 잃어버리지 않고, 워드프로세서가 읽을 시간이 있을 때까지 대기열에 배치될 것이다.대기열을 사용하면 입력한 내용이 처리할 때 순서가 바뀌지 않습니다.
대기열의 기본 작업
대기열의 두 가지 기본 작업은 하나의 데이터 항목을 삽입하는 것이다. 즉, 하나의 데이터 항목을 대열의 끝에 넣고, 다른 하나는removing(제거), 즉 대열의 데이터 항목을 제거하는 것이다.영화 애호가들이 줄을 서서 표를 살 때 먼저 줄을 서서 표를 산 다음 줄을 서서 표를 끊는 것과 유사하다.
창고에 있는 데이터 항목을 삽입하고 제거하는 방법의 이름은 매우 표준적이며,push와pop이라고 부른다.대열의 방법은 지금까지 표준화된 명칭이 없다.'삽입'은put,add 또는enque라고 할 수 있고,'삭제'는delete,get 또는deque라고 할 수 있습니다.데이터 항목을 삽입하는 대열의 끝을 백,tail 또는end라고 할 수도 있습니다.데이터 항목을 제거한 대열은 헤드라고 할 수도 있다.다음은 insert,remove,front,rear를 사용합니다.
삽입은 값을 대열의 끝에 삽입하고, 동시에 대열의 화살표는 하나를 증가하여 새로운 데이터 항목을 가리킨다.
데이터 항목이 제거되면 팀 헤더 바늘이 하나 증가합니다.일반적으로 대기열을 실행할 때, 삭제된 데이터 항목은 메모리에 저장되며, 단지 접근할 수 없습니다. 왜냐하면 팀 헤더 바늘이 다음 위치로 옮겨졌기 때문입니다.
창고의 상황과 달리, 대기열의 데이터 항목은 항상 수조의 0 아래에서 시작하지 않습니다.일부 데이터 항목을 제거하면 팀 헤더 바늘이 비교적 높은 아래 표식 위치를 가리킨다.
이 데이터 항목을 팀에서 삭제하지 않고 헤더 데이터 항목의 값을 되돌려줍니다.
빈 대기열에서 데이터 항목을 제거하거나 가득 찬 대기열에 데이터 항목을 삽입하려면 프로그램에서 오류 메시지를 알려야 합니다.
순환 대기열
대기열에 새 데이터 항목을 삽입하면 대열의 Rear 화살표가 위로 이동하고 그룹 아래에 표시된 큰 위치로 이동합니다.데이터 항목을 제거하면 대열 끝 프론트 포인터도 위로 이동합니다.이런 디자인은 사람들이 직관적으로 눈치채는 것과 상반될 수 있다. 왜냐하면 사람들이 영화표를 사서 줄을 설 때 팀은 항상 앞으로 이동하기 때문이다. 앞에 있는 사람이 표를 사서 팀을 떠난 후에 다른 사람들은 모두 앞으로 이동하기 때문이다.컴퓨터에서 대기열에서 데이터 항목을 삭제한 후에도 다른 데이터 항목을 모두 앞으로 이동할 수 있지만, 이렇게 하는 효율은 매우 떨어진다.반대로 우리는 대열 중대 머리와 대열 꼬리 바늘의 이동을 통해 모든 데이터 항목의 위치를 변하지 않게 유지한다.
이렇게 설계된 문제는 대열의 꼬리 바늘이 곧 수조의 끝부분으로 옮겨질 것이다.수조의 시작 부분에 빈 데이터 항목 단원이 있습니다. 이것은 제거된 데이터 항목의 위치입니다. 그러나 팀의 끝 바늘이 더 이상 뒤로 이동할 수 없기 때문에 새로운 데이터 항목을 삽입할 수 없습니다. 어떻게 해야 합니까?
서라운드 처리
대기열이 불만족스럽지만 새로운 데이터 항목을 삽입할 수 없는 문제를 피하기 위해 대열의 꼬리 바늘을 수조가 시작되는 위치로 돌려놓을 수 있다.이것이 바로 순환 대기열이다. (때로는 버퍼 링이라고도 부른다.)
포인터가 돌아가는 과정: 대기열에 충분한 데이터 항목을 삽입하여 팀의 끝 포인터가 그룹의 미단을 가리키도록 합니다.몇 개의 그룹 앞부분의 데이터 항목을 삭제합니다.새 데이터 항목을 삽입합니다.대열의 꼬리 바늘이 시작점으로 돌아오지 않는 것을 볼 수 있다.새 데이터 항목이 이 위치에 삽입됩니다.
더 많은 데이터 항목을 삽입합니다.대열의 꼬리 바늘이 예상대로 위로 이동한다.대열의 끝 바늘이 감긴 후에 대열의 머리 바늘 아래에 있으니 주의하세요. 이것은 초기의 위치를 뒤바꿉니다.이것을'절단된 서열'이라고 할 수 있습니다. 대기열의 데이터 항목은 두 개의 다른 서열에 존재합니다.
충분한 데이터 항목을 삭제하면 팀 헤드 바늘도 감깁니다.이때 대기열의 바늘은 처음에 실행되었을 때의 위치 상태로 돌아가고, 대열의 머리 바늘은 대열의 끝 바늘 아래에 있다.데이터 항목도 단일한 연속적인 시퀀스로 복구됩니다.
대기열의 Java 코드
Queue.자바 프로그램은 insert (), remove (), peek (), isEmpty (), size () 방법이 있는Queue 클래스를 만들었습니다.
패키지 창고와 대기열;
class Queue{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
public Queue(int s){
maxSize=s;
queArray=new long[maxSize];
front=0;
rear=-1;
nItems=0;
}
public void insert(long j){
if(rear==maxSize-1)
rear=-1;
queArray[++rear]=j;
nItems++;
}
public long remove(){
long temp=queArray[front++];
if(front==maxSize)
front=0;
nItems--;
return temp;
}
public long peekFront(){
return queArray[front];
}
public boolean isEmpty(){
return (nItems==0);
}
public boolean ifFull(){
return (nItems==maxSize);
}
public int size(){
return nItems;
}
}
Insert() 메서드가 실행되는 전제 조건은 대기열 불만입니다.ain () 에는 이 방법이 표시되지 않지만, 보통 isFull () 방법을 호출하고false를 되돌린 후에야 insert () 방법을 호출합니다.(더 일반적인 방법은 insert () 방법에 대기열이 가득 찼는지 확인하는 판정을 추가하고, 가득 찬 대기열에 데이터 항목을 삽입하는 경우 이상을 던지는 것입니다.)
일반적인 경우, 삽입 작업은rear(대미 포인터)를 추가한 후, 대미 포인터가 가리키는 위치에 새로운 데이터를 삽입합니다.그러나rear 바늘이 수조의 맨 끝, 즉 maxSize-1의 위치를 가리킬 때, 데이터 항목을 삽입하기 전에 수조의 맨 밑으로 돌아가야 합니다.회전 작업은rear를 -1로 설정합니다. 따라서rear가 1을 더하면 0과 같고 그룹 밑부분의 하표값입니다. 마지막으로 nItem가 1을 추가합니다.
Remove () 방법이 실행되는 전제 조건은 대기열이 비어 있지 않다는 것입니다. 이 방법을 사용하기 전에 isEmpty () 방법을 사용해서 대기열이 비어 있지 않거나remove () 방법에 오류 검사 메커니즘을 추가해야 합니다.
제거 (remove) 작업은 항상 프론트 포인터에서 헤더 데이터 항목의 값을 얻어서front를 하나로 추가합니다.단, 이렇게 하면front의 값이 수조의 맨 끝을 초과하면front는 수조 아래에 0이라고 표시된 위치로 돌아가야 한다.이런 검사를 하는 동시에 우선 반환 값을 임시로 저장한다.마지막으로 nItem에서 1 빼기.
Peek () 방법은 간단하고 이해하기 쉽습니다. 프론트 포인터가 가리키는 데이터 항목의 값을 되돌려줍니다.일부 대기열의 실현도 대기열의 끝 데이터 항목의 값을 볼 수 있다.예를 들어 이러한 방법은peekFront (), peekRear (), 또는front () 와rear () 라고 할 수 있다.
isEmpty (), isFull (), size () 방법의 실현은 모두 nItems 필드에 의존합니다. 각각 nItems가 0인지, maxSize인지 또는 그 자체의 값을 되돌려줍니다.
Queue 클래스에 데이터 항목 계수 필드를 포함하는 nItems는 insert () 와remove () 방법으로 하여금 이 변수 값을 각각 점차적으로 증가하고 점차적으로 줄여야 하기 때문에 추가 작업을 추가합니다.이것은 추가 비용이 아닐 수도 있지만, 대량의 삽입과 제거 작업을 처리하면 성능에 영향을 줄 수 있다.
일부 대기열의 구현은 데이터 항목의 수를 계산하는 필드를 사용하지 않고front와rear를 통해 대기열이 비어 있거나 가득 차 있는지, 데이터 항목의 개수를 계산하기 때문이다.만약 이렇게 한다면 isEmpty (), ifFull (), size () 예는 상당히 복잡할 것이다. 왜냐하면 앞에서 말한 것처럼 데이터 항목의 서열이 두 단락으로 접히거나 연속된 단락이기 때문이다.
그리고 이상한 문제가 생겼어요.대기열이 가득 찼을 때,front와rear 바늘은 일정한 위치를 취하지만, 대기열이 비어 있을 때도 같은 위치 관계를 나타낼 수 있습니다.그래서 같은 시간에 대열이 꽉 찼을 수도 있고 비어 있을 수도 있다.이 문제의 해결 방법은 대기열 데이터 항목의 최대 값학보다 수조 용량을 크게 하는 것이다.
읽어주셔서 감사합니다. 여러분에게 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
