정의와 성질

큐는 스택과 비슷하지만 First In, First Out(FIFO)인 자료구조!
가게에서 기다리고 있는 손님 줄을 생각하면 된다.

성질도 스택과 거의 유사하다.

기능과 구현

배열을 이용한 구현을 해보자. head와 tail 두 변수가 필요하다.
21과 30이 들어있는 큐를 보자. head는 가장 앞 원소의 인덱스, tail은 가장 뒤 원소 인덱스+1로 잡아두었다.
0번째 인덱스가 비어있는 이유는 아래와 같다.

빈 큐에 55를 넣고 17을 넣어보자. tail은 2만큼 증가하고 head는 그대로 있다. 이때 가장 앞의 원소인 55를 삭제하려고 한다. 굳이 값을 변경할 필요는 없고 head만 1만큼 증가시키면 된다.
큐의 크기는 tail-head가 된다.
이런식으로 반복하다보면 공간이 계속 늘어나게 되는데, 이 문제는 원형의 배열을 가정하게 되면 해결할 수 있다.

5,6,7번 인덱스에 원소가 있는 상황에서 하나를 더 추가하고자 할때, 8번 인덱스가 아닌 0번 인덱스에 원소를 추가하는 방법이다.

push 함수

void push(int x){
	dat[tail++]=x;
}

pop 함수

void pop(){
	head++;
}

front 함수

int front(){
	return dat[head];
}

back 함수

int back(){
	return dat[tail-1];
}

STL queue

스택과 거의 같지만 front(),back() 함수가 더 있다.
queue는 코테 단골 문제인 BFS나 Flood Fill문제에서 사용된다. 여기서도 큐가 비어있을 때 front,back,pop 함수를 사용하면 런타임 에러 발생하기때문에 주의하기!

연습문제

백준10845 큐

풀이

내 코드
<stl 풀이>

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    queue<int> q;
    int N,x;
    string order;
    cin >> N;
    while(N--){
        cin >> order;
        if(order == "push"){
            cin >> x;
            q.push(x);
        }
        else if(order == "pop"){
            if(!q.empty()){
                cout << q.front() << "\n";
                q.pop();
            }
            else cout << "-1\n";
        }
        else if(order == "size") cout << q.size() << "\n";
        else if(order == "empty") {
            if(!q.empty()) cout << "0\n";
            else cout << "1\n";
            
        }
        else if(order == "front"){
            if(!q.empty()) cout << q.front() << "\n";
            else cout <<"-1\n";
        }
        else {
            if(!q.empty()) cout << q.back() << "\n";
            else cout <<"-1\n";
        }
    }

    return 0;
}

<구현 풀이>

#include <iostream>

using namespace std;

int dat[100001];
int head=0;
int tail=0;

void push(int x){
	dat[tail++]=x;
}

void pop(){
    head++;
}

int front(){
	return dat[head];
}

int back(){
    return dat[tail-1];
}

int main()
{
    int N,x;
    string order;
    cin >> N;
    while(N--){
        cin >> order;
        if(order == "push"){
            cin >> x;
            push(x);
        }
        else if(order == "pop"){
            if(tail-head > 0){
                cout << front() << "\n";
                pop();
            }
            else cout << "-1\n";
        }
        else if(order == "size") cout << tail-head << "\n";
        else if(order == "empty") {
            if(tail-head > 0) cout << "0\n";
            else cout << "1\n";
            
        }
        else if(order == "front"){
            if(tail-head > 0) cout << front() << "\n";
            else cout <<"-1\n";
        }
        else {
            if(tail-head > 0) cout << back()<< "\n";
            else cout <<"-1\n";
        }
    }

    return 0;
}