큐 는 데이터 요소가 한쪽 끝 (뒤쪽 끝)에서 삽입되고 다른 쪽 끝 (앞쪽 끝)에서 삭제되는 FIFO 순서 다음에 비 프리미티브 선형 데이터 구조로 설명 될 수 있습니다. 대기열의 다른 변형은 순환 대기열, 이중 종료 대기열 및 우선 순위 대기열입니다.
비교 차트
| 비교 근거 | 선형 대기열 | 순환 대기열 |
|---|---|---|
| 기본 | 순서대로 데이터 요소와 명령어를 차례로 구성합니다. | 마지막 요소가 첫 번째 요소에 연결된 원형 패턴의 데이터를 정렬합니다. |
| 작업 실행 순서 | 작업은 이전에 배치 된 순서대로 실행됩니다 (FIFO). | 작업 실행 순서가 변경 될 수 있습니다. |
| 삽입 및 삭제 | 새로운 요소는 뒤쪽 끝에서 추가되고 앞쪽에서 제거됩니다. | 삽입 및 삭제는 어느 위치에서나 수행 할 수 있습니다. |
| 공연 | 무능한 | 선형 대기열보다 효과적입니다. |
선형 큐의 정의
선형 대기열 은 합리적으로 선입 선출 된 첫 번째 목록입니다. 요소가 차례로 위치하는 직선과 닮았 기 때문에이를 선형이라고 부릅니다. 여기에는 새로운 요소가 한쪽 끝에 추가되고 다른 쪽에서 삭제되는 동질적인 요소 모음이 포함됩니다. 대기열의 개념은 극장 티켓을 얻기 위해 티켓 카운터 외부에서 기다리는 관중의 예를 통해 이해할 수 있습니다. 이 대기열에서 사람은 대기열의 뒤쪽 끝을 조인하여 티켓을 가져오고 티켓은 대기열의 프론트 엔드에서 발행됩니다.
대기열에서 수행되는 여러 작업이 있습니다.
- 먼저 대기열이 0으로 초기화됩니다 (즉, 비어 있음).
- 큐가 비어 있는지 확인하십시오.
- 큐가 가득 차 있는지 여부를 판별하십시오.
- 후미 (Enqueue)에서 새 요소를 삽입합니다.
- 프런트 엔드에서 요소 삭제 (Dequeue).
대기열은 두 가지 방식으로 구현 될 수 있습니다.
- 정적으로 (배열 사용)
- 동적으로 (포인터 사용)
선형 대기열의 한계는 대기열에 빈 공간이 포함되어 있어도 대기열에 새 요소를 추가 할 수없는 시나리오를 작성한다는 것입니다. 위의 상황이 아래 주어진 그림에 나와 있습니다. 모든 상자가 여전히 비어있는 동안 뒤가 마지막 색인을 가리키고 있지만 새 요소를 추가 할 수 없습니다.
순환 대기열 정의
순환 대기열 은 선형 대기열의 한계를 효과적으로 극복 한 선형 대기열의 변형입니다. 순환 대기열에서 마지막 요소가 사용되고 공간을 사용할 수있는 경우 대기열의 첫 번째 위치에 새 요소가 추가됩니다. 선형 대기열의 경우 삽입은 후단에서 수행하고 프론트 엔드에서 삭제할 수 있습니다. 대기열에서 일련의 연속 삭제를 수행 한 후 전체 대기열에서 언더 플로우 조건 (Rear = max - 1)이 존재하기 때문에 사용할 수있는 공간이 더 남아 있어도 새 요소를 추가 할 수없는 상황이 발생합니다.
순환 대기열은 마지막 요소 다음에 첫 번째 요소가 오는 포인터를 통해 두 끝을 연결합니다. 또한 삽입 및 삭제할 요소를 추적 할 수 있도록 몇 가지 추가 로직을 구현하여 앞면과 뒷면을 추적합니다. 이 경우 순환 대기열은 실제 대기열이 가득 찰 때까지 오버플로 조건을 생성하지 않습니다.
원형 큐가 뒤 따르는 조건들 :
- 정면은 첫 번째 요소를 가리켜 야합니다.
- Front = Rear이면 대기열이 비어 있습니다.
- 새로운 요소가 추가되면 대기열은 값 1 (Rear = Rear + 1)만큼 증가합니다.
- 큐에서 요소가 삭제되면 front가 1 씩 증가합니다 (Front = Front + 1).
선형 대기열과 순환 대기열의 주요 차이점
- 선형 대기열은 데이터 요소가 순차적으로 구성되는 순서 목록입니다. 반대로 원형 큐는 순환 방식으로 데이터를 저장합니다.
- 선형 큐는 태스크를 실행하기 위해 FIFO 순서를 따릅니다 (첫 번째 위치에 추가 된 요소는 첫 번째 위치에서 삭제됨). 반대로 순환 대기열에서 요소에 대해 수행 된 작업 순서가 변경 될 수 있습니다.
- 요소의 삽입 및 삭제는 선형 큐에서 고정됩니다. 즉, 후단에서 추가 및 프런트 엔드에서 삭제됩니다. 반면 순환 큐는 요소가 비어있을 때까지 요소를 삽입하고 삭제할 수 있습니다.
- 선형 큐는 메모리 공간을 낭비하고 순환 큐는 공간을 효율적으로 사용합니다.
선형 대기열 구현
아래 주어진 알고리즘은 큐에 요소를 추가 하는 것을 보여줍니다.
큐에는 큐를 저장하는 하나의 배열과 -1 인 앞쪽 및 뒤쪽 초기 위치를 저장하는 다른 배열을 포함하여 세 개의 데이터 변수가 필요합니다.
insert (item, queue, n, rear) {if (rear == n) 다음에 "queue overflow"를 출력한다. else {뒤 = 뒤 + 1; 큐 [rear] = item; }} 아래에 주어진 알고리즘은 대기열에있는 요소를 삭제하는 방법 을 보여줍니다.
delete_circular (item, queue, rear, front) {if (rear == front) 다음에 "queue underflow"를 출력하십시오; else {앞 = 앞 + 1; item = 큐 [앞]; }} 순환 큐의 구현
원형 큐에서 요소의 추가 를 해석하는 알고리즘 :
insert_circular (item, queue, rear, front) {rear = (rear + 1) mod n; if (front == rear) then "queue is full"을 출력하십시오; else {queue [rear] = item; }} 알고리즘은 순환 대기열에서 요소 삭제 를 설명합니다.
delete_circular (item, queue, rear, front) {if (앞 == 뒤) 다음 print ( "대기열이 비어 있음"); else {앞 = 앞 + 1; item = 큐 [앞]; }} 결론
선형 큐는 삽입 동작을 수행하기 위해 요소가 빈 공간으로 이동해야하는 경우에는 비효율적입니다. 그것이 저장 공간을 낭비하는 경향이있는 이유는 순환 큐가 저장 공간을 적절하게 사용하는 반면 빈 공간이 있으면 임의의 위치에 요소가 추가되기 때문입니다.
