알고리즘 (Queue)

큐 (Queue)

 

큐는 먼저 넣은 데이터가 먼저 나오는 형식입니다.(선입선출)

(나중에 넣은 데이터가 먼저 나오는 스택과는 정반대 부분이다.)

 

FIFO 구조 저장하는 선형자료.

 

큐는 FIFO(First In First Out) / LILO(Last In Last Out) 순서를 따릅니다.

• FIFO : 처음 들어온 값이 처음에 나가는 것
• LILO : 마지막에 들어온 값이 마지막에 나가는 것

큐에 끝(Rear)에서 요소를 추가하는 작업을 enqueue라고 하며 큐에 맨 앞(Front)에서 요소를 제거하는 작업을 dequeue라고 합니다.

 

가득 찬 큐에 요소를 추가하려고 할 때 Overflow가 발생하며, 빈 큐에서 요소를 제거하려고 할 때 Underflow가 발생합니다.

 

 

기본 동작

- enqueue() - 큐에 끝(rear)에 데이터항목을 추가

- dequeue() - 큐에 맨 앞(front)에 항목을 제거

- peek() - 큐에 맨 앞(front)에 있는 항목을 반환

- isfull() - 큐가 가득 찼는지 확인

- isempty() - 큐가 비어 있는지 확인

 

 

시간 복잡도

큐 에 데이터 항목을 추가/제거 시에 O(1) 을 실행한다.

 

 

큐 구현 방법의 두가지 경우

 

-배열 사용

장점 - 구현이 쉽다.

단점 - 크기가 동적이 아님. 런타임 시 필요에 따라 늘어나거나 줄어들지 않음

 

-연결 리스트사용

장점 - 크기가 동적임. 런타임 시 필요에 따라 크기가 확장 및 축소될 수 있음

단점 - 포인터를 위한 추가 메모리 공간이 필요함.

 

 

사용 사례

- 어떠한 작업/ 데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용합니다.

ex) 디스크 스케줄링

- 서로 다른 쓰레드 또는 프로세스 사이에서 자료를 주고 받을 때 자료를 일시적으로 저장하는

용도로 많이 사용합니다.

ex) IO버퍼, 파이프