[선형구조] 큐(Queue), 덱(Deque)

 

큐는 줄서기와 같다.

 

큐(Queue)

 

큐는 FIFO(First In, First Out) 선입선출의 형태를 가지는 자료구조이다.

 

스택처럼 끝부분에서 삽입, 삭제 연산이 이루어지지만

 

스택은 삽입, 삭제가 같은 쪽에서만 이루어지고

 

큐는 서로 다른 쪽에서 이루어진다는 차이를 가진다.

 

 

Queue

 

큐의 입구를 Rear, 출구를 Front라고 한다.

 

그리고 데이터를 삽입되는 연산을 Enqueue, 데이터를 삭제되는 연산을 Dequeue라고 한다.

 

큐는 BFS를 구현할 때, 아주 유용하게 쓰인다.

 

또한 큐 역시 스택과 마찬가지로 연결 리스트를 사용하여 구현하며, 삽입, 삭제 연산은 O(1)이다.

 

 

덱(Deque)

 

덱은 큐의 변형판으로, Double-Ended-Queue의 약자이다.

 

즉, 말뜻처럼 큐가 양쪽에서 가능하다는 것인데,

 

양쪽 끝에서 데이터의 삽입 연산과 삭제 연산이 모두 가능한 자료구조이다.

 

 

Deque

 

마찬가지로 덱 역시 연결 리스트로 구현하면 된다.