큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. FIFO(First in First out) 구조이다.
큐의 성질
- 원소의 추가가 O(1)
- 원소의 제거가 O(1)
- 제일 앞/뒤의 원소 확인이 O(1)
- 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각함.
큐에서는 추가되는 곳을 rear, 즉 뒤 쪽이라고 하고 제거되는 쪽을 front, 즉 앞 쪽이라고 한다.
자료구조에서는 인덱스를 가지고 원소에 접근하는 기능이 없지만 배열을 가지고 만들 땐 해당 기능이 가능하도록 구현할 수 있다. 하지만 STL queue에는 인덱스로 내부 원소를 접근하는 기능이 없다.
큐를 구현할 때 원소를 담을 큰 배열 한 개와 앞쪽 위쪽을 가리킬 변수 두 개가 필요하다. head와 tail인데 head는 가장 앞에 있는 원소의 인덱스이고 tail은 가장 뒤에 있는 원소의 인덱스 +1이다.
push 할 땐 tail이 증가하고 pop할 땐 head가 증가한다.
위의 그림처럼 dat의 5,6,7번지를 사용하고 있는 상황을 보면 앞쪽에 사용하지 않고 있는 공간이 많음에도 불구하고 더 이상 삽입을 할 수 없다. 삽입을 하려면 dat [8]에 값을 써야 하는데 배열이 8칸이니 그럴 수가 없기 때문이다.
큐 구현
이와 같이 스택과는 다르게 큐는 배열로 구현하면 삭제가 발생할 때마다 앞쪽에 쓸모없는 공간이 계속 생기게 된다. 이 문제를 해결하는 방법은 간단히 큐의 원소가 들어갈 배열을 원형으로 만드는 것이다.
관념적으로는 배열이 원형인 것이고, 실제 구현을 할 때는 head나 tail이 7인 상태에서 1이 더해질 때 0번지로 다시 오도록 만들면 된다. 즉 dat의 5,6,7번지를 사용하는 상황에서 원소 1개가 추가되면 0번지를 점유하게 되는 것이다.
이렇게 원형의 배열을 가정하고 구현한 큐를 원형 큐(Circular Queue)라고 부른다.
그냥 선형 배열에서 만든 큐는 삭제가 될 때마다 쓸모없는 공간이 계속 생겨서 앞쪽에 공간이 많음에도 불구하고 새 원소를 추가할 수 없는 상황이 생길 수 있는데, 원형 큐는 head와 tail이 다시 앞쪽으로 돌아오기 때문에 원소의 개수가 배열의 크기보다 커지지 않는 한 문제가 없다. 그래서 실무에서 굳이 STL 말고 큐를 직접 구현해서 쓰겠다면 원형 큐로 만드는 것이 좋다.
하지만 코테에서는 어차피 push의 최대 횟수가 정해져 있고 그러면 배열의 크기를 push의 최대 횟수보다 크게 둬서 굳이 원형 큐를 만들지 않아도 되게끔 할 수 있다.
push, pop은 각각 삽입과 삭제를 하는 함수이고, front, back은 각각 제일 앞 쪽의 원소 확인과 제일 뒷쪽의 원소를 반환하는 함수이다.
#include<bits/stdc++.h>
using namespace std;
const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;
void push(int x) {
dat[tail++] = x;
}
void pop() {
head++;
}
int front() {
return dat[head];
}
int back() {
return dat[tail - 1];
}
void test() {
push(10); push(20); push(30);
cout << front() << "\n";
cout << back() << "\n";
pop(); pop();
push(15); push(25);
cout << front() << "\n";
cout << back() << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
test();
}
STL queue
#include<bits/stdc++.h>
using namespace std;
int main() {
queue<int> Q;
Q.push(10);
Q.push(20);
Q.push(30);
cout << Q.size() << "\n";
if (Q.empty()) cout << "Q is empty \n";
else cout << "Q is not empty\n";
Q.pop();
cout << Q.front() << "\n";
cout << Q.back() << "\n";
Q.push(40);
Q.pop();
cout << Q.front() << "\n";
}큐는 BFS랑 Flood Fill을 할 때 쓰게 되는데 이들은 코테 단골 문제이다.
큐가 비어있는데 front나 back이나 pop을 호출하면 런타임 에러가 발생할 수 있다는 점은 주의해야한다.