[자료구조 이론] 큐(Queue) + 덱(Deque ; Double Ended Queue) 이해하기

큐는 스택과 함께 언급되고 또 비교되는 자료구조이다.

스택은 먼저 들어간 데이터가 나중에 나오는 구조인 반면, 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다.  이것이 스택과 큐의 유일한차이!

 

이렇듯 큐는 '선입선출' 구조의 자료구조 이다. 영어로는 'FIFO(Fistr in , First out)' 구조

 

큐의 구조

 스택에서는 가장 최근 데이터의 위치를 확인하기 위해 top변수를 사용하였다. 

큐에서는 입구와 출구가 따로 있기 때문에 앞과 뒤를 의미하는 front와 back(원형 큐에서는 rear)을 사용한다.

 

- 큐의 핵심 연산

1) enqueue(x) : 큐에 데이터를 넣는 연산, 주어진 요소 x를 큐의 맨뒤에 추가한다.

2) dequeue() : 큐가 비어있지 않으면 맨앞에 있는 요소를 삭제하고 반환한다.

 

- 큐 구현

스택과 마찬가지로 배열과 연결리스트로 구현 할 수 있는데 스택과 같이 단지 일직선으로 큐를 구현하려 한다면 앞서 먼저 그 구조를 고민해야 한다. 구현이 매우 간단하지만 문제점을 발견하게 될것이다. 

 

 먼저, 큐에 데이터가 꽉찬다면 데이터를 더 추가 할 수 없다. 이문제는 물론 큐 사이즈를 늘리고 원소를 다시 복사 하면된다.(그러나 시간이,,, 좋은 방법이 아니겠죠)

 두번째로 공간의 효율성에 문제가 생긴다. 배열로 단순히 구현하면 enqueue 반복하여 데이터를 삽입후 dequeue를 반복하여 삭제를 한다면 front가 계속 뒤로 밀려 앞에 공간이 남게 된다.  다시말해 하나의 원소가 빠져서 공간이 비게 되면 그 다음부터 남아있는 모든 데이터를 당겨아야 하니까 비효율적인 것이다. 작은 데이터라면 상관이 없지만, 크기가 큰 데이터를 처리하기에는 무리이다.

 

 

 원형큐(Circular Queue)

 이 선형큐의 단점을 보완 할 수 있는 것이 바로 원형큐! 

  배열로 구현은 하지만, 실제 작동 할 때는 마치 원형으로 되어 있는 것처럼 자료구조를 사용하는 것이 특징이다.

 

 위에서 본 선형큐와 front, rear은 같다. 그러나 여기서 중요한 것은 front 는 첫번째 요소 하나 앞에 인덱스를 가리키는 반면, back는 마지막 요소를 가리키고 있다는 것!

 

 

원형 큐의 연산

처음 시작 할 때는 front와 rear가 같은곳을 가르키고 있다.

enqueue 연산 시 R이 가리키는 위치를 한 칸 이동시킨 다음에 , R이 카리키는 위치에 데이터를 저장한다.

dequeue 연산 시 F가 가리키는 위치를 한 칸 이동시킨 다음에 , F가 가리키는 위치에 저장된 데이터를 반환 및 소멸한다.

 

원형 큐가 포화 상태일 때 

처음 시작 할 때는 front와 rear이 같은 곳을 가리키고 있지만 포화 상태일 때는 front와 rear이 한칸 차이가 난다. 왜냐하면 포화 상태 일때도 모든 공간을 다 사용하게 된다면 front와 rear이 같은곳을 가리키게 되므로 공백상태와 포화 상태가 구분이 안가는 것이다. 그렇기에 한탄을 띄어 놓는다.

 

따라서 원형큐의 특성을 다음 두가지로 추가 정리 할 수 있다.

- 원형큐가 텅 빈 상태 : F와 R이 동일한 위치를 가리킨다.

- 원형큐가 꽉 찬 상태 : R이 가리키는 위치의 앞을 F가 가리킨다.

 

 

보너스 덱(Deeque)

 

 

덱의 구조

앞뒤에서 입력과 출력이 모두 가능한 형태이다. 

 

Double Ended Queue의 준말로 큐의 확장형 같은 느낌이지만 스택의 확장형이라는 느낌도 받는다.

이 때까지 스택과 큐는 특수목적에서 사용되는 자료구조라는 느낌이 들었던 반면 자유도가 매우 높아진

덱의 경우에는 여러가지 용도에 부합되게 사용될 경우의 수가 많이 늘어나게 된다.. 그러나 실제로 양쪽의 입력과 출력을 모두 사용하는 경우는 없다.

 보통 두가지의 이유중 하나로 사용하게 되는데 입력을 추가하거나 출력을 추가하는 방식으로 많이 사용합니다.

즉 큐를 구현했는데 양쪽에서 출력할 수 있어야해!! 이럴경우랑 스택을 구현했는데 양쪽에서 입력하고 싶어!! 이럴경우에 덱을 쓰게 된다.

 

 

- 덱의 연산 

1) addFront(e) : 주어진 요소 e를 덱의 맨앞에 추가한다.

2) deleteRear(): 덱이 비어있지 않으면 맨뒤에 있는 요소를 삭제하고 반환한다.

3) getFront/Rear(): 덱이 비어 있지 않으면 맨 앞/맨 뒤에 있는 요소를 삭제하지 않고 반환 한다.