[C++/코테] 큐(queue)

큐 Queue

• 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조
• FIFO. 먼저 들어간 원소가 먼저 나온다. 공항 입국 수속 처럼!
• BFS, Flood Fill을 할 때 사용한다. ⭐ 코테 단골 문제

큐의 성질

1. 원소의 추가(rear)와 제거(front)가 $O(1)$
2. 제일 앞/뒤의 원소 확인이 $O(1)$
3. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다.
   STL queue에서도 없는 기능이지만, 배열의 인덱스 기능을 활용하여 접근 가능하게 만들 수는 있다.

구현

스택과 마찬가지로 배열과 연결리스트 모두로 구현 가능하지만, 배열로 구현하는 것이 쉽다.

배열로 구현할 시,

• 원소를 담을 큰 배열 1개와 앞쪽(head), 뒤쪽(tail)을 가리킬 변수 2개가 필요하다.
• data[head] 부터 data[tail-1] 번지가 바로 큐의 원소들이 있는 자리이다.
• 큐의 크기(size)는 tail - head 로 계산할 수 있다.

head 와 tail 변수의 원리

스택과 다르게, 배열로 큐를 구현할 시 삭제가 발생할 때마다 뒤로 밀리기 때문에, 앞쪽에 쓸 수 없는 공간이 생기게 된다.

• 큐의 배열을 원형으로 만든다. (Circular Queue)
• head나 tail이 마지막 인덱스에 도달했을 때(max가 되었을 ) 1이 증가되면, 다시 0번지로 오게 구현한다.

그러므로, STL에서 제공하는 queue가 아닌 직접 구현할 때는 원형 큐를 사용해 구현한다.
그러나 코딩테스트에서는 push의 최대 횟수가 정해져 있기 때문에, 배열의 크기를 push의 최대 횟수보다 크게 두어 선형 큐로 구현 가능하다.

 

push 함수

• tail이 가리키는 자리에 원소를 추가한다.
• tail을 1 증가시킨다.

void push(int x){
    dat[tail++] = x;
}

pop 함수

• head를 1 증가시킨다.

void pop(){
    head++;
}

front 함수

• data[head]를 반환한다.

void front(){
    return data[head];
}

back 함수

• data[tail-1]을 반환한다.

void back(){
    return dat[tail-1];
}

큐가 비어있을 때 front/ back/ pop을 호출하면 런타임 에러가 발생할 수 있다.

연습 문제: 백준 10845 큐

* 파이썬으로 풀었습니다.

2023.11.09 - [Algorithm] - [Python/코테] 백준 10845번 큐

[Python/코테] 백준 10845번 큐

---

출처:

https://www.youtube.com/watch?v=D_fwSy5tRAY