참고 자료
https://youtu.be/Nk_dGScimz8?t=116
https://chanhuiseok.github.io/posts/algo-26/
https://yjg-lab.tistory.com/115
큐는 스택과 마찬가지로 실제로 존재하지는 않지만 일종의 규칙을 제공함으로써, 자료를 보다 구조적으로 이해할 수 있게 해주는 ADT (추상 데이터 타입)이다.
큐 (Queue)의 사전적 정의는 '대기열'인데, 선착순으로 줄 서는 것을 생각하면 이해하기 매우 쉽다. 버스 정류장에서 일렬로 줄을 선다면, 맨 앞에 있는 사람이 가장 먼저 버스에 탑승할 것이다.
이처럼 큐는 가장 먼저 들어온 요소가 가장 먼저 나가기 때문에 First In First Out (FIFO, 선입선출)이라고 불린다.
큐는 우리 생활 곳곳에서 쓰인다. 이메일 수신, 푸시 알림 기능, 쇼핑몰에서 선착순으로 주문을 처리하는 방식 등 선착순이랑 관련된 모든 것에 큐가 사용된다고 볼 수 있다.
선형 큐 (Linear Queue)
큐의 맨 앞을 front, 맨 뒤를 rear라 하고, 큐에서 기본적으로 자주 사용되는 연산들을 배열로 구현해보자.
enqueue: 큐의 rear에 요소 삽입
dequeue: 큐의 front에 있는 요소 삭제
isFull: 큐가 가득 찼는지 검사
isEmpty: 큐가 비었는지 검사
front: 큐의 front에 있는 값 출력
back: 큐의 rear에 있는 값 출력
선형 큐에서는 rear가 배열 크기와 같아지면 큐가 꽉 찼다고 판단하며, front와 rear가 동일한 위치를 가리키면 큐가 비었다고 판단한다.
#include <iostream>
using namespace std;
template<class T>
class Queue {
private:
int front;
int rear;
int capacity;
T* arr;
public:
Queue(int capacity) {
front = rear = 0;
this->capacity = capacity;
arr = new T[capacity];
}
// 큐의 rear에 원소 삽입
void enqueue(int data) {
if (isFull()) {
printf("Queue is full\n");
return;
}
arr[rear++] = data;
printf("push %d\n", data);
}
// 큐의 front에 있는 원소 삭제하면서 그 값을 리턴
T dequeue() {
if (isEmpty()) {
printf("Queue is empty\n");
return -1;
}
return arr[front++];
}
bool isFull() {
return (rear == capacity);
}
bool isEmpty() {
return (front == rear);
}
T getFront() {
return arr[front];
}
T getBack() {
return arr[rear - 1];
}
};
int main() {
Queue<int> q(5);
// rear에 원소 삽입
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
q.enqueue(5);
// full
q.enqueue(6);
printf("front: %d, back: %d\n", q.getFront(), q.getBack());
// front에 있는 원소 삭제
printf("pop %d\n", q.dequeue());
printf("pop %d\n", q.dequeue());
printf("pop %d\n", q.dequeue());
printf("pop %d\n", q.dequeue());
printf("pop %d\n", q.dequeue());
// empty
printf("pop %d\n", q.dequeue()); // -1
return 0;
}출력 결과
push 1
push 2
push 3
push 4
push 5
Queue is full
front: 1, back: 5
pop 1
pop 2
pop 3
pop 4
pop 5
Queue is empty
pop -1
그런데, 선형 큐는 원소 삭제 시 앞에서부터 공간이 남게 되는데, 이때 뒤의 원소들을 앞으로 당겨주지 않으면 빈 공간이 많이 남아 있음에도 불구하고 더 이상 원소를 추가하지 못하는 문제가 발생할 수 있다. 그렇다고 삭제 연산이 일어날 때마다 원소들을 한칸씩 앞으로 당기기에는 매우 비효율적이다. 이를 해결할 수 있는 방법이 원형 큐이다.
원형 큐 (Circular Queue)
원형 큐는 말그대로 큐의 시작과 끝이 이어져 있는 큐이다. 실제로는 선형 자료구조인 1차원 배열로 구현하긴 하지만, 배열의 끝에 이르면 다시 앞으로 돌아온다는 점에서 원형 큐라고 부른다.
원소를 삽입하다가 rear의 인덱스가 배열 크기를 넘어버렸을 때 다시 배열의 앞쪽으로 돌아가려면 어떻게 해야 할까? 바로 (rear + 1)을 배열 크기로 나눈 위치에 새로운 원소를 삽입해주면 된다. 배열 크기를 n이라고 했을 때, 그 나머지는 0~(n-1)까지의 값을 가지기 때문에 항상 배열의 인덱스 범위 내에 원소를 삽입할 수 있다. 그리고 선형 큐와 달리, 원소 삭제로 인해 생기는 빈 공간을 효율적으로 사용할 수 있다.
- front: 첫번째 요소 바로 앞의 인덱스
- rear: 마지막 요소의 인덱스
- 원형 큐가 비었을 때는? front == rear
- 원형 큐가 꽉 찼을 때는? front == (rear + 1) % (배열 크기)
- 원형 큐에서는 공백 상태와 포화 상태를 구별하기 위해 하나의 공간은 항상 비워둔다.
#include <iostream>
using namespace std;
template<class T>
class Queue {
private:
int front;
int rear;
int capacity;
T* arr;
public:
Queue(int capacity) {
front = rear = 0; // 원형 큐이기 때문에 초기 인덱스가 0이 아니어도 됨.
this->capacity = capacity;
arr = new T[capacity];
}
// 큐의 rear에 원소 삽입
void enqueue(int data) {
if (isFull()) {
printf("Queue is full\n");
return;
}
rear = (rear + 1) % capacity;
arr[rear] = data;
printf("push %d\n", data);
}
// 큐의 front에 있는 원소 삭제하면서 그 값을 리턴
T dequeue() {
if (isEmpty()) {
printf("Queue is empty\n");
return -1;
}
front = (front + 1) % capacity;
return arr[front];
}
bool isFull() {
return front == ((rear + 1) % capacity);
}
bool isEmpty() {
return (front == rear);
}
T getFront() {
return arr[front + 1];
}
T getBack() {
return arr[rear];
}
};
int main(void)
{
Queue<int> q(6);
// rear에 원소 삽입
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
q.enqueue(5);
// full
q.enqueue(6);
printf("front: %d, back: %d\n", q.getFront(), q.getBack());
// front부터 원소 삭제
printf("pop %d\n", q.dequeue());
printf("pop %d\n", q.dequeue());
printf("pop %d\n", q.dequeue());
printf("pop %d\n", q.dequeue());
printf("pop %d\n", q.dequeue());
// empty
printf("pop %d\n", q.dequeue()); // -1
return 0;
}출력 결과
push 1
push 2
push 3
push 4
push 5
Queue is full
front: 1, back: 5
pop 1
pop 2
pop 3
pop 4
pop 5
Queue is empty
pop -1
백준 10845번
https://www.acmicpc.net/problem/10845
C++의 STL에서 제공하는 queue 컨테이너를 사용해보자.
큐가 비어있는데 front(), back(), pop() 함수를 호출하면 런타임 에러가 발생하므로 주의가 필요하다.
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main() {
queue<int> q;
int n;
cin >> n; // 명령어의 개수
string str;
for (int i = 0; i < n; i++) {
cin >> str;
if (str == "push") {
int val;
cin >> val;
q.push(val);
}
else if (str == "pop") {
if (!q.empty()) {
printf("%d\n", q.front());
q.pop();
}
else
printf("-1\n");
}
else if (str == "size") {
printf("%d\n", q.size());
}
else if (str == "empty") {
printf("%d\n", q.empty());
}
else if (str == "front") {
if (!q.empty())
printf("%d\n", q.front());
else
printf("-1\n");
}
else if (str == "back") {
if (!q.empty())
printf("%d\n", q.back());
else
printf("-1\n");
}
}
return 0;
}
