[바킹독: 알고리즘] 큐(Queue)

※ (링크) 바킹독 유튜브 영상을 통해

학습한 내용을 정리한 것입니다.

 

본인은 JAVA를 활용해 학습하였습니다

비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다.

 

본문의 모든 내용의 출처는 아래 명시된 링크와 같습니다.

 

[목차] 정의와 성질, 기능과 구현, STL Queue, 연습문제

[실전 알고리즘] 0x06강 - 큐

출처: blog.encrypted.gg/934?category=773649

---

정의와 성질

(1) 정의

큐는 한쪽 끝에서 원소를 넣고, 반대쪽 끝에서 원소를 뺄 수 있는 자료구조입니다. 스택에서는 FILO이었지만, 큐는 FIFO(First In First Out)으로, 먼저 들어간 자료가 먼저 나오는 구조입니다

 

(2) 성질

 

1. 원소의 추가, O(1)
2. 원소의 제거, O(1)
3. 제일 앞/뒤 원소 확인, O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

스택에서는 원소가 추가되고 제거되는 곳을 top이라 부르며, 원소가 위/아래로 배치된 것이라 생각을 많이 합니다.

큐에서는 추가되는 곳을 rear(뒤쪽)이라고 하며, 제거되는 곳을 front(앞쪽)이라고 합니다.

 

(4)번은 원칙적으로 불가능하나, 배열로 직접 큐를 만들 경우 해당 기능이 가능하도록 구현할 수 있습니다.

---

구현

큐의 구현은 스택과 마찬가지로 배열을 이용한 구현이 더 쉽습니다. 

 

1. 큐를 구현하기 위한 필요 요소
   원소를 담을 배열, 앞쪽(head)과 뒤쪽(tail)을 나타낼 변수 두 개
   
   
2. head는 가장 앞에 위치한 원소를 가지며, tail은 가장 마지막 원소의 번호를 가집니다.
   
   
3. 시작시 head = tail = 0 입니다.
   만약 데이터를 추가할 경우 tail은 한 칸 증가하게 됩니다.
   만약 맨 앞에 데이터를 제거할 경우 head의 값은 증가하게 됩니다.
   
   
4. (3)번 내용을 정리하자면, head와 tail 값은 0에서 시작해 계속 증가합니다.
   
   이를 정리하면, 배열에서 배열[head]부터 배열[tail - 1]까지 큐의 원소가 들어있는 자리이며, 큐의 크기는 tail - head로 계산할 수 있습니다.

데이터의 pop(제거)와 push(추가)가 발생하며 Queue의 원소는 오른쪽으로 밀리는 특징이 있습니다. 고로 삭제가 발생할 때마다, 앞쪽에 쓸모없는 공간이 생기게 됩니다.

 

원형 큐(Circular Queue)

 

위 메모리 낭비에 대한 해결법은 큐의 원소가 들어갈 배열을 원형으로 만드는 것입니다. 관념적으로 배열이 원형인 것이며, 실제 구현을 할 때, head 혹은 tail이 더해질 때, 큐의 마지막 index번호인 경우 0으로 돌아가게 하는 것입니다.

 

선형배열은 삭제가 될 때마다 앞에 공간이 존재함에도 불구하고, 새 원소를 추가할 수 없는 상황이 발생할 수 있습니다. 하지만 원형 큐(Circular Queue)는 head와 tail이 다시 앞으로 돌아오기에 원소의 갯수가 배열의 크기보다 커지지 않는한 문제가 발생하지 않습니다.

 

만약 STL을 사용하지 않고 직접 구현한다면, 원형 큐를 이용하는게 좋습니다.

 

---

연습 문제

(1) BOJ 10845번

 

---

 

github.com/encrypted-def/basic-algo-lecture/blob/master/workbook.md

encrypted-def/basic-algo-lecture

www.acmicpc.net/workbook/view/7310

문제집: 0x06강 - 큐 (BaaaaaaaaaaarkingDog)