자료구조 - Queue

Queue

대기열 또는 FIFO (first in, first out)는 컬렉션의 요소를 추가하는 프로세스 인 enqueue의 두 가지 주요 작업으로 요소 컬렉션으로 사용되는 추상 데이터 유형입니다 (요소는 뒷면에서 추가됩니다. ) 추가 된 첫 번째 요소를 제거하는 프로세스를 dequeue합니다. (요소가 앞쪽에서 제거됩니다). 배열과 연결된 목록을 모두 사용하여 구현할 수 있습니다.

Insertion : O(1)
Deletion  : O(1)
Access Time : O(n) [Worst Case]

Example  : 이름으로 표시된 대기열은 버스 정류장이나 열차의 대기열에 따라 작성된 데이터 구조입니다. 

대기열의 맨 앞에 서있는 사람 (가장 오랜 시간 대기 중)이 티켓을받는 첫 번째 사람입니다. 그래서 자원이 여러 사용자들 사이에서 공유되고 선착순으로 제공되는 상황. 예를 들면 CPU 스케줄링, 디스크 스케줄링 등이 있습니다. 

대기열의 또 다른 응용 프로그램은 두 프로세스간에 데이터가 비동기 적으로 전송되는 경우 (전송 된 것과 동일한 비율로 데이터를 수신하지 않아도되는 경우)입니다. IO 버퍼, 파이프, 파일 IO 등을 예로들 수 있습니다.

Circular Queue 이 데이터 구조의 장점은 배열 구현의 경우 공간 낭비를 줄이는 것입니다. (n + 1) 번째 요소의 삽입은 공백 인 경우 0 번째 인덱스에서 수행됩니다.