[바킹독 실전 알고리즘 0x06] 큐

정의와 성질

큐는 한쪽 끝에서 원소를 넣고, 다른쪽 끝에서 원소를 뺄 수 있는 자료구조이다.(FIFO)

큐에서 원소가 추가되는 곳을 rear, 즉 뒷쪽이라고 하고, 원소가 제거되는 곳을 front라고 한다.

• 원소의 추가나 제거를 할 때 O(1)의 시간복잡도가 필요하다.
• 가장 앞이나 가장 뒤 원소를 확인하려면 O(1)의 시간복잡도가 필요하다.
• 가장 앞이나 가장 뒤 원소를 제외한 원소들의 확인/변경은 원칙적으로 불가능하다. (앞 게시글의 스택과 비슷한 맥락)

 

기능과 구현

큐도 스택과 마찬가지로 배열 혹은 연결리스트를 사용해 구현이 가능하다. 배열로 구현하는 방법이 더 쉬워서 이번 게시글에서는 배열로 구현하는 것만 소개하려고 한다. 

const int MAX = 1000000;
int data[MAX]; //원소를 담을 큰 배열
int head = 0, tail = 0;  //앞쪽, 뒤쪽을 가리킬 변수

head는 가장 앞에 있는 원소의 인덱스, tail은 (가장 뒤에 있는 원소의 인덱스+1)를 가리킨다.

시작할 땐 head와 tail이 모두 배열의 0번 인덱스를 가리킨다. 원소가 추가되면 head는 그대로이고 tail은 1이 증가한다. 반대로 원소가 삭제되면 head값이 1 증가하고 tail값이 그대로 유지된다.

 

원소들을 담은 배열 data[]에서 data[head]부터 data[tail-1]까지의 위치에 원소들이 담겨 있다. 이를 통해 큐의 크기는 (tail-head)임을 쉽게 알 수 있다.

 

 

 

 

큐를 사용하면 원소를 삭제할 때마다 head값이 증가하고, 추가할 때마다 tail값이 증가하기 때문에 연산을 진행할수록 data 배열 상에서 큐의 원소들이 들어 있는 장소는 점점 오른쪽으로 이동할 것이다. 따라서 큐를 배열로 구현하면 삭제 연산을 진행할수록 배열의 앞부분에 쓰지 않는 빈 공간이 생기게 된다. 이 문제는 큐의 원소가 들어갈 배열을 원형으로 만듦으로써 해결할 수 있다.

위 그림과 같이 선형적인 1차원 배열을 원형으로 만들 수 있다. head가 인덱스 5, tail이 인덱스 7을 가리키고 있는 상태에서 원소를 하나 더 추가하고 싶다면 tail의 인덱스를 0으로 변경하면 된다. 이런 방식으로 구현한 큐는 원형 큐라고 부른다. 

 

그치만 대부분의 코딩 테스트의 경우, push()연산의 횟수가 정해져 있다. 따라서 push횟수보다 배열의 크기를 크게 만들면 굳이 원형 큐가 아닌 일차원 배열을 사용해 구현하더라도 문제가 없을 것이다.

push()

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

//더 간단한 코드
void push(int x){
	data[tail++] = x;
}

pop()

void pop(){
	head += 1;
}

 

STL queue

보통 큐는 BFS와 Flood Fill을 구현할 때 사용하게 되는데, 둘 다 코딩테스트 빈출 주제여서 문제를 풀 때 STL queue를 사용할 일이 아주 많다. STL queue 사용 시 큐가 비어있는데 front, back, pop을 호출하면 런타임에러가 발생할 수 있음에 주의해야 한다.

#include <bits/stdc++.h>
using namespace std;

int main(void){
    queue<int> Q;
    Q.push(10); //10
    Q.push(20); //10 20
    Q.push(30); //10 20 30
    cout << Q.size() << '\n';
    if(Q.empty()) cout << "Q is empty\n";
    Q.pop(); //20 30
    cout << Q.front() << '\n'; //30
    Q.push(40); //20 30 40
    Q.pop(); //30 40
    cout << Q.front() << '\n'; //30
}