[Python] 자료구조 - 큐와 덱 이해하기

 

 

큐

 

 

큐는 Queue로 '대기 줄'을 의미합니다.

보통 놀이공원에서 줄을 설 때 먼저 줄을 선 사람이 먼저 입장하게 됩니다.

마찬가지로 큐는 가장 먼저 들어간 자료가 가장 먼저 나오는 자료 구조입니다.

 

편의점에서 일해보셨던 경험이 있으셨던 분들은 익숙하겠지만

'선입선출'과도 같은 개념입니다.

 

 

 

우유를 진열한다고 가정해보면

제일 먼저 들어온 우유는 가장 전단에 배치하고

제일 늦게 들어온 우유는 가장 후단에 배치합니다.

 

그리고 유통기한이 지난 우유를 폐기처분할 때는

전단에 있는 우유를 꺼내서 폐기처분을 하게 됩니다.

 

나머지 우유는 앞으로 한 칸씩 앞으로 당겨 배치하게 되죠..

 

https://miro7923.github.io/java/java-queue/

 

 

큐도 마찬가지로

새로 들어오는 데이터는 후단에 배치하고

전단에 있는 데이터를 삭제하게 됩니다.

 

데이터를 삭제할 때는

뒤에 있는 데이터를 한 칸 씩 당겨와야하구요.

 

지금까지 설명드렸던 내용이 바로

배열 구조를 가지는 큐에 대한 설명입니다.

 

 

쉽죠?

 

 

배열 구조를 가진 큐의 동작을 이해하기는 쉬우나

요소를 삭제하고나서 나머지 요소들을 앞으로 이동시켜야 한다는 단점이 있습니다.

 

따라서 이를 보완해주기 위해

원형 큐를 사용해줍니다!!

 

 

 

큐 구현을 위한 개념

 

 

원형 큐를 설명드리기 앞서

큐를 구현하기 위해서 어떤 개념이 필요한지

잠시 짚고 가겠습니다.

 

array	큐 요소들을 저장할 배열
capacity	큐에 저장할 수 있는 요소의 최대 개수
rear	가장 후단에 위치한 요소의 인덱스 (요소를 추가할 때는 (rear+1)의 위치에 요소를 추가)
front	가장 전단에 위치한 요소 바로 1칸 앞의 인덱스 (요소를 삭제할 때는 (front+1)의 위치에 있는 요소를 삭제)

 

 

원형 큐

 

 

https://yo0on.github.io/posts/자료구조02.Queue/

 

 

원형 큐를 나타낸 그림인데요,

실제로 큐가 저렇게 원형으로 생긴 게 아닙니다.

 

전단 인덱스(front)나 후단 인덱스(rear)가 증가하다가

capacity와 같아지면 0으로 만들어주는데

 

이 때 front와 rear가 아무리 증가한다고 해도

0~7에서만 움직이기 때문에

원형 큐처럼 나타내준 것입니다.

 

 

작동 방식은 앞서 배운 큐와 마찬가지로

후단에서 요소를 추가하고, 전단에서 요소를 삭제합니다.

 

rear에서 시계 방향으로 한 칸 이동한 (rear+1)의 위치에 요소를 추가하고

front에서 시계 방향으로 한 칸 이동한 (front+1) 위치의 요소를 삭제합니다.

 

 

원형 큐 작동 방식을

나머지 연산인 %를 통해서

 

front = (front + 1) % capacity

rear = (rear + 1) % capacity

 

위처럼 나타내어 줄 수 있습니다.

 

 

원형 큐만 있다면 데이터를 삭제해도

front와 rear를 이동시켜주면 되기 때문에

굳이 데이터를 앞으로 이동시켜줄 필요가 없습니다!

(front와 rear을 이동시켜주는 게 훨씬 간편)

 

 

덱

 

 

덱(deque)은 double-ended queue로

쉽게 말하자면 전단과 후단에서 모두 삽입과 삭제가 가능한 큐입니다.

 

전단에서 요소를 추가하고,

후단에서 요소를 삭제하는 것만 제외하고는

대부분의 큐의 동작과 겹칩니다.

 

따라서 큐를 구현한 코드에

몇 가지 기능만 추가해준다면

덱을 코드로 쉽게 구현해줄 수 있습니다.

 

 

 

큐와 덱의 구현과 문제 풀이는

다음 시간에 다뤄보도록 하겠습니다!