[ 알고리즘 개념 ] 큐 (Queue), 덱(Deque)

큐 (Queue)

 

큐는 FIFO (First In First Out), FCFS (First Come First Service), 선입선출로, 먼저 들어간 데이터가 먼저 나오는 구조이다.

한쪽 끝에서는 삽입 (Insert) 만 일어나고 다른 한쪽에서는 삭제 (Delete)  만 발생한다.

FIFO (First in First Out)

즉, 놀이공원 줄서기와 같이 들어온 순서대로 처리하는 형태이다.

따라서, 마지막에 들어온 요소를 처리하려면 앞의 요소를 모두 처리해야 한다.

 

어떠한 일을 순서대로 처리할 때, 큐를 사용한다.

먼저 들어온 일을 모두 처리하고 나서야 그 다음 일을 처리할 수 있다.

늦게 삽입된 요소는 계속 대기해야 한다는 단점이 있지만 순서를 보장해야 하는 일에 사용하기 좋다는 장점도 있다.

 

▩ 큐의 주요기능

(1) 큐 생성 (2) rear 원소 삽입 (3) front 원소삭제 (4) front 원소 삭제 후 반환 (5) 큐 비어있는지 확인

 

 

선형 큐

그림에서 나타낸 큐는 선형 큐에 해당한다.

가장 직관적인 형태이지만, 한 가지 단점이 존재한다.

선형 큐에서 삽입연산과 삭제연산을 반복하면 위 그림과 같이 rear가 마지막 index를 가리키게 되는데,

이 경우 앞에는 비어있을 수 있지만 Queue가 꽉 찼다고 인식한다.

원래대로라면 데이터를 삭제할 때마다 배열의 요소를 앞으로 당겨야 하지만, 실제 구현을 할 때에는 비효율적이기 때문에 인덱스 단위로 큐의 연산을 진행하기 때문이다.

 

원형 큐

선형 큐의 단점을 보완한 것이 바로 원형 큐이다.

그림에서는 마치 원 모양으로 보이지만 사실 선형 큐와 동일하게 배열로 구현한다.

구현 시 선형큐와 다른 점은 원형큐는 논리적으로 처음과 끝이 연결되어 있다고 가정한다는 것이다.

 

 

 

덱 (Deque)

 

큐는 위에서 언급했듯이 한쪽 끝(front)에서는 삭제만 하고 다른 한쪽 끝(end)에서만 삽입한다.

그러나 덱은 양쪽 모두에서 삽입과 삭제연산을 수행할 수 있다.

따라서, 큐에 비해 양쪽에서의 삽입 및 삭제연산의 성능이 좋지만 이 또한 중간원소에서는 성능이 떨어진다.

 

덱 (Deque)

 

▩ 덱의 주요기능

(1) 덱 생성 (2) front 원소 삽입 (3) back 원소 삽입 (4) front 원소 삭제 및 반환 (5) back 원소 삭제 및 반환 (6) front 원소 반환 (삭제X) (7) back 원소 반환 (삭제O) (8) 덱이 비어있는지 확인