큐의 정의
한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조로 먼저 들어간 원소가 먼저 나오게 되는 FIFO의 구조
연산의 시간복잡도는 스택과 마찬가지로 추가와 제거가 모두 O(1)이고, 제일 앞/뒤의 원소 확인도 O(1)이다.
큐라는 자료구조는 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 불가능하지만, 배열을 가지고 만들 때 해당 기능이 가능하도록 구현을 할 수 있다. STL Queue에서는 중간 지점의 원소들을 확인/변경이 불가능하다.
구현 방법
배열이나 연결 리스트 둘 중 어느것을 이용해도 구현하는데 문제는 없지만 배열을 이용한 방식이 더 쉽기 때문에 배열로 구현해보기
- 원소를 담은 배열
- 큐의 앞쪽(head)과 뒤쪽(tail)을 가리킬 변수 2개
배열의 인덱스가 0부터 시작하기 때문에 데이터가 push 될 때마다 tail을 가리키고 있는 위치가 한칸씩 이동되는데 이때 tail은 가장뒤에 있는 원소를 가리키는게 아니라 -1칸을 해야지 마지막 원소를 가리킨다.
(tail의 초기값을 -1로 놓고해도 되지만 0으로 설정하는 방식으로 구현함) - 데이터를 삽입할때는 tail의 위치만 바뀌고 데이터를 제거할때는 head 위치만 바뀐다.
pop을 할 때 마다 head 위치는 증가하면서 큐의 원소들이 있는 장소는 점점 오른쪽으로 밀리게 되는데, 앞쪽에 사용하지 않은 공간이 많음에도 불구하고 push를 할 수 없게 된다.
큐를 배열로 구현했을 때 삭제가 발생하다 보면 앞쪽에 쓸모없는 공간이 생기는데 이 문제를 해결하는 방법은 큐의 원소가 들어갈 배열을 원형으로 만들어서 구현하면 된다.
관념적으로 배열이 원형인 형태로 보이지만 실제 구현을 할 때는 head나 tail이 7인 상태에서 1이 더해질 때 다시 0번 인덱스를 사용하는 방식이 된다. 이렇게 원형의 배열을 가정하고 구현한 큐를 원형 큐라고 부른다.
실무에서 STL말고 큐를 직접 구현해서 사용한다면 원형 큐를 만드는게 좋지만 코딩테스트에서는 push의 최대 횟수가 정해져 있기 때문에 배열의 크기를 push의 최대 횟수보다 크게 둬서 원형 큐를 만들지 않아도 되게끔 할 수 있다.
구현
#include <iostream>
#include <queue>
using namespace std;
const int MX = 100005;
int dat[MX];
int head = 0;
int tail = 0;
void push(int x) {
dat[tail++] = x;
}
void pop() {
head++;
}
int size() {
return tail - head;
}
// 제일 먼저 꺼낼 수 있는 원소
// 첫번째로 들어간 원소
int front() {
return dat[head];
}
// 마지막에 들어간 원소
int back() {
return dat[tail - 1];
}
bool empty() {
// 큐에 데이터가 없으면 true을 반환하고 있으면 false을 반환
if (tail - head == 0) return true;
else return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
queue<int> Q;
Q.push(10);
Q.push(20);
Q.push(30);
cout << Q.size() << '\n';
// 큐도 스택과 마찬가지로 데이터가 없는 경우 pop, front, back 함수 호출시 런타임 에러 발생
if (!Q.empty()) {
Q.pop(); // 10
cout << Q.front() << "\n"; // 20
cout << Q.back() << "\n"; // 30
}
return 0;
}