[바킹독 알고리즘]0x06강 - 큐

0x00 정의와 성질

정의

 

 

큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 된다. 스택을 FILO(First In Last Out)이라고 한 것과 비슷하게 큐를 FIFO(First in First Out)이라고 하기도 한다.

 

 

 

성질

 

큐에서는 추가되는 곳을 rear(뒤쪽)라고 하고, 제거되는 쪽을 front(앞쪽)이라고 한다.

 

 

 

 

 

 

0x01 기능과 구현

선형 배열로 만든 큐

 

head는 가장 앞에있는 원소의 인덱스이고 tail은 가장 뒤에 있는 원소의 인덱스 +1 이다. 꼭 이렇게 안두고 tail을 가장 뒤에있는 원소의 인덱스로 두어도 괜찮다.

 

값을 추가하면 head는 변함이 없고 tail은 한 칸 올라가게 된다.

값을 제거하면 head가 한 칸 올라가가고 tail은 변함이 없다.

큐의 크기는 tail - head 이다.

 

선형 배열로 만든 큐는 삭제가 될 때 마다 쓸모없는 공간이 계속 생겨서 앞쪽에 공간이 많음에도 불구하고 새 원소를 추가할 수 없는 상황이 생길 수 있다.

 

 

 

 

원형 큐

 

원형 큐는 head와 tail이 다시 앞쪽으로 돌아오기 때문에 원소의 갯수가 배열의 크기보다 커지지 않는 한 문제가 없다. 그래서 실무에서 굳이 STL말고 큐를 직접 구현해서 쓰겠다고 하면 원형 큐로 만드는게 좋다.

 

하지만 우리가 연결 리스트에서 생각한 것과 비슷하게, 코딩테스트에서는 어차피 push의 최대 횟수가 정해져 있다. 그러면 배열의 크기를 push의 최대 횟수보다 크게 둬서 굳이 원형 큐를 만들지 않아도 되게끔 할 수 있다.

 

 

 

 

구현

사실 원형 큐의 구현이라고 해봐야 head, tail이 MX가 될 경우 0으로 만드는 것만 달라지기 때문에 어려운 것은 아닌데, 그래도 여기서는 일단 원형 큐가 아니라 선형 배열에서의 큐를 다루겠다. 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'; // 10
  cout << back() << '\n'; // 30
  pop(); pop();
  push(15); push(25);
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 25
}

int main(void) {
  test();  
}

 

 

 

 

 

 

0x02 STL queue

 

물론 STL에 큐도 있다. 보통 큐는 BFS랑 Flood Fill를 할 때 쓰게 되는데 둘 다 코딩테스트 단골 문제여서 문제를 풀 때 STL queue를 쓸 일이 아주 아주 많을 것이다. 

 

그리고 큐가 비어있는데 front나 back이나 pop을 호출하면 런타임에러가 발생할 수 있다는 점은 주의해야 한다.

 

 

 

 

 

 

0x03 연습문제

BOJ 10845번:큐

 

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

const int MX = 1000005;
int dat[MX];
int tail, head;

void push(int x){
    dat[tail++] = x;
}
void pop(){
    head++;
}
int front(){
    return dat[head];
}
int back(){
    return dat[tail-1];
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >>n;
    
    while(n--){
        string q;
        string ord;
        cin >> ord;
        if(ord == "push"){
            int val;
            cin >> val;
            push(val);
        }
        else if(ord == "pop"){
            if(tail==head){
                cout << -1 << '\n';
            } else {
                cout << front() << '\n';
                pop();
            }
        }
        else if(ord == "front"){
            if(tail==head){
                cout << -1 << '\n';
            } else {
                cout << front() << '\n';
            }
        }
        else if(ord == "back"){
            if(tail==head){
                cout << -1 << '\n';
            } else {
                cout << back() << '\n';
            }
        }
        else if (ord == "empty"){
            if(tail == head){
                cout << 1 << '\n';
            } else cout << 0 << '\n';
        }
        else cout << tail-head << '\n';
    }
}

 

 

 

BOJ 18258번:큐2

 

 

 

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

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    queue<int> Q;
    int n;
    cin >> n;
    while(n--){
        string s;
        cin >> s;
        if(s=="push"){
            int val;
            cin >> val;
            Q.push(val);
        }
        else if(s=="pop"){
            if(Q.empty()) cout << -1 << '\n';
            else{
                cout << Q.front() << '\n';
                Q.pop();
            }
        }
        else if(s=="size") {
            cout << Q.size() << '\n';
        }
        else if(s=="front") {
            if(Q.empty()) cout << -1 << '\n';
            else{
                cout << Q.front() << '\n';
            }   
        }
        else if(s=="back") {
            if(Q.empty()) cout << -1 << '\n';
            else{
                cout << Q.back() << '\n';
            }
        } else{
            if(Q.empty()) cout << 1 << '\n';
            else cout << 0 << '\n';
        }
    }
}