[자료구조] 큐(Queue)의 개념

큐(Queue)
스택과 마찬가지로 일종의 리스트로, 대기 행렬(줄)과 같은 형태의 리스트이다.

데이터의 삽입은 한쪽 끝에서(줄의 맨 끝), 삭제는 반대쪽 끝(줄의 맨 앞)에서만 일어난다.

큐에서 삽입이 일어난 쪽을 rear, 삭제가 일어나는 쪽을 front라고 부른다.
*rear : 뒤쪽, 뒤쪽의

FIFO(First-In, First-Out)라고도 많이 부른다.

큐는 스택보다 자주 사용되는 자료구조이다. 여러 개의 프로그램이나 프로세스 등이 하나의 공유 자원을 사용하기 위해 대기하는 상황에서 큐를 주로 사용한다. (ex : 프린터 큐)

큐의 연산

- 큐의 rear에 새로운 원소를 삽입하는 연산 : insert, enqueue, offer(java), push(C++ STL)

- 큐의 front에 있는 원소를 삭제하고 반환하는 연산 : remove, dequeue, poll, pop

- 큐의 front에 있는 원소를 제거하지 않고 반환하는 연산 : peek, element, front

- 큐가 비었는지 검사 : is_empty

큐의 응용 예

- CPU 스케쥴링 : multitasking 환경에서 프로세스들은 큐에서 CPU가 할당되기를 기다린다. (프로세스들이 동시에 실행되지 않고, 돌아가면서 아주 잠깐씩 실행된다.)

- 데이터 버퍼 : 네트워크를 통해 전송되는 패킷(packet)들은 도착한 순서대로 버퍼에 저장되어 처리되기를 기다린다. (패킷 전송속도가 빨라 패킷들이 즉시 처리되지 못하고 버퍼에 저장된 채로 처리되기까지 대기할 때)

- 그 외에도 자원을 공유하는 대부분의 경우에 큐가 사용됨.

스택과 큐

둘 다 일종의 리스트이지만,
스택은 한쪽 끝에서 삽입과 삭제가 모두 일어나고(후입선출)
큐는 한쪽 끝에서 삽입이 일어나고 반대 쪽 끝에서 삭제가 일어난다. (선입선출)