[실전 알고리즘] 0x06강 - 큐

1. 정의와 성질

큐 - 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조

스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 된다. 스택은 FILO(First In Last Out), 큐는 FIFO(First in First Out)이다.

 

큐의 성질

1. 원소의 추가 - O(1)

2. 원소의 제거 - O(1)

3. 제일 앞/뒤의 원소 확인 - O(1)

4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능.

 

스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각을 많이 하는데 큐에서는 추가되는 곳을 rear, 즉 뒤쪽이라고 하고 제거되는 쪽을 front, 즉 앞쪽이라고 한다.

 

스택과 비슷한 맥락으로 큐라는 자료구조에서는 인덱스를 가지고 원소에 접근하는 기능이 없지만, 배열을 가지고 직접 만들 땐 해당 기능이 가능하도록 구현을 할 수 있다. 단, STL queue에는 인덱스로 내부 원소를 접근하는 기능이 없다.

 

---

2. 기능과 구현

큐도 배열이나 연결 리스트를 이용해서 구현 가능하다. 배열을 이용하는 게 더 쉽다. 배열로 구현 시 원소를 담은 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개가 필요하다. head와 tail을 각각의 변수라고 할 때 head는 가장 앞에 있는 원소의 인덱스이고 tail은 가장 뒤에 있는 원소의 인덱스 + 1이다.

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

 

head와 tail은 0번지에서 시작해 계속 증가하게 된다. dat 배열에서 dat[head]부터 dat[tail-1]번지가 바로 큐의 원소들이 들어있는 자리이고 큐의 크기는 tail - head로 쉽게 계산할 수 있다.

 

push를 할 땐 tail이 증가하고, pop을 할 땐 head가 증가한다. 그렇기 때문에 dat 배열에서 큐의 원소들이 들어있는 장소는 점점 오른쪽으로 밀리게 된다.

 

head가 5를 가리키고 있고 tail이 8을 가리키고 있어 dat의 5번지, 6번지, 7번지를 사용하고 있는 상황을 보면 앞쪽에 사용하지 않고 있는 공간이 많음에도 불구하고 더 이상 삽입을 할 수가 없다. 삽입을 하려면 dat[8]에 값을 써야 하는데 배열이 8칸이니 그럴 수가 없기 때문이다.

 

이와 같이 스택과는 다르게 큐는 배열로 구현하면 삭제가 발생할 때 마다 앞쪽에 쓸모없는 공간이 계속 생기게 된다. 이 문제를 해결하는 방법은 의외로 간단한데 큐의 원소가 들어갈 배열을 원형으로 만드는 것이다. 개념적으로 배열이 원형인거고, 실제 구현을 할 땐 head나 tail이 7인 상태에서 1이 더해질 때 0번지로 다시 오도록 만들면 된다.

 

즉, dat의 5, 6, 7번지를 사용하는 상황에서 원소 1개가 추가되면 0번지를 점유하는 것이다. 이렇게 원형의 배열을 가정하고 구현한 큐를 원형 큐(Circular Queue)라고 부른다.

 

선형 배열에서 만든 큐는 삭제가 될 때 마다 쓸모없는 공간이 계속 생겨서 앞쪽에 공간이 많음에도 불구하고 새 원소를 추가할 수 없는 상황이 생길 수 있는데, 원형 큐는 head와 tail이 다시 앞쪽으로 돌아오기 때문에 원소의 갯수가 배열의 크기보다 커지지 않는 한 문제가 없다. 그래서 큐를 직접 구현해서 쓸 때는 원형 큐로 만드는게 좋다.

 

하지만 코딩테스트에서는 어차피 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'; // 10
  cout << back() << '\n'; // 30
  pop(); pop();
  push(15); push(25);
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 25
}

int main(void) {
  test();  
}

 

---

3. STL stack

레퍼런스 링크

http://www.cplusplus.com/reference/queue/queue/

queue - C++ Reference

 

예제

#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'; // 3
  if(Q.empty()) cout << "Q is empty\n";
  else cout << "Q is not empty\n"; // Q is not empty
  Q.pop(); // 20 30
  cout << Q.front() << '\n'; // 20
  cout << Q.back() << '\n'; // 30
  Q.push(40); // 20 30 40
  Q.pop(); // 30 40
  cout << Q.front() << '\n'; // 30
}

보통 큐는 BFS랑 Flood Fill를 할 때 쓰게 되는데 둘 다 코딩테스트 단골 문제여서 문제를 풀 때 STL queue를 쓸 일이 아주 많을 것이니 잘 익혀두도록!

 

그리고 큐가 비어있는데 front나 back이나 pop을 호출하면 런타임에러가 발생할 수 있으니 주의할 것!

 

---

4. 연습문제

BOJ 10845번: 큐

10845번: 큐

STL queue 이용

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, x;
    string s;
    queue<int> q;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        if (s == "push")
        {
            cin >> x;
            q.push(x);
        }
        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 == "empty")
        {
            if (q.empty())
            {
                cout << 1 << "\n";
            }
            else
            {
                cout << 0 << "\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";
            }
        }
    }

    return 0;
}

STL 이용 X

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

int q[100000];
int head, tail;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, x;
    string s;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        if (s == "push")
        {
            cin >> x;
            q[tail++] = x;
        }
        else if (s == "pop")
        {
            if (tail - head <= 0)
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << q[head++] << "\n";
            }
        }
        else if (s == "size")
        {
            cout << tail - head << "\n";
        }
        else if (s == "empty")
        {
            if (tail - head <= 0)
            {
                cout << 1 << "\n";
            }
            else
            {
                cout << 0 << "\n";
            }
        }
        else if (s == "front")
        {
            if (tail - head <= 0)
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << q[head] << "\n";
            }
        }
        else if (s == "back")
        {
            if (tail - head <= 0)
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << q[tail - 1] << "\n";
            }
        }
    }

    return 0;
}

 

---

참고자료

[실전 알고리즘] 0x06강 - 큐

[실전 알고리즘] 0x06강 - 큐