[자료구조] 큐 (Queue)

개념

큐(queue)는 리스트의 한 쪽 끝(rear)에서 자료의 입력이 이루어지고, 다른 쪽(반대 쪽) 끝(front)에서 자료의 출력이 이루어지도록 구성된 구조를 의미한다. 따라서 큐는 선입선출(FIFO, First In First Out)이라고 하며 이는 먼저 들어간 것이 먼저 나온다는 것을 의미한다.

큐는 공유 자원 접근, 멀티 프로그래밍, 메시지 큐, 그래프와 트리의 너비 우선 탐색 등에 사용된다.

이동 큐(Remove Queue)

큐의 구조상 큐에 기억 공간에 남아 있어도 새로운 노드를 삽입시킬 수 없게 된다. 따라서 이를 해결하기 위하여 기억 공간을 정리하여 새로운 노드를 삽입할 수 있도록 하는 방식이다.

큐의 추상 데이터 타입(ADT)

• push(val): 큐의 rear에 val을 삽입한다.
• pop(): 큐의 front에서 객체를 삭제한다. 빈 큐(empty queue)일 경우 에러를 발생시킨다.
• front(): front 값을 반환한다. 만약 빈 큐(empty queue)이면 에러를 발생시킨다.
• size(): 큐 안의 객체의 개수를 반환한다.
• empty(): 큐가 비었으면 true를 그렇지 않으면 false를 반환한다.

원형 큐(Circular Queue)

이동 큐가 가지고 있는 불리한 점을 개선한 방법이며, 큐의 마지막 부분과 처음 부분이 서로 이웃하도록 원형으로 만들고 이를 운영하는 방식이다.

데크(Deque)

데크(deque)는 양쪽 끝에서 삽입과 삭제가 가능한 구조이다. 선형 리스트의 일종이면서 삽입과 삭제가 일어나는 곳이 리스트의 한쪽 끝으로 고정된 것이 아니고 양쪽 끝에서 발생할 수 있는 형태의 리스트를 말한다. 이것은 스택과 큐를 합쳐놓은 것으로 볼 수도 있다.

데크의 추상 데이터 타입(ADT)

• push_front(val): 큐의 front에 val을 삽입한다.
• push_back(val): 큐의 rear에 val을 삽입한다.
• pop_front(): 큐의 front에서 객체를 삭제한다. 빈 큐(empty queue)일 경우 에러를 발생시킨다.
• pop_back(): 큐의 rear에서 객체를 삭제한다. 빈 큐(empty queue)일 경우 에러를 발생시킨다.
• front(): front 값을 반환한다. 만약 빈 큐(empty queue)이면 에러를 발생시킨다.
• back(): back 값을 반환한다. 만약 빈 큐(empty queue)이면 에러를 발생시킨다.
• size(): 큐 안의 객체의 개수를 반환한다.
• empty(): 큐가 비었으면 true를 그렇지 않으면 false를 반환한다.

구현

C++에서 array, struct, vector, queue, deque 등으로 구현할 수 있다.