큐

개념

First in First Out의 특성을 갖는 자료구조로, 먼저 들어온 값이 제일 먼저 나간다.

큐에 값을 집어 넣는 enqueue는 큐의 rear 인덱스를 이용하여 이뤄지고,

큐에서 값을 빼내는 dequeue는 큐의 front 인덱스를 이용하여 이루어진다.

따라서 front와 rear라는 인덱스를 이용하여 큐의 삭제와 삽입 연산을 수행한다.

 

구현

#include <iostream>
#define Queue_size 5
using namespace std;
int queue[Queue_size];
int front=0,rear=0;

int isqempty() //front와 rear가 같은 곳을 가리킨다면 큐가 비었다는 의미
{
    return (front==rear) ? 1:0;
}

int isqfull() //front의 바로 뒤에 rear가 있다면 큐가 가득찼다는 의미
{
    return ((rear+1)%Queue_size) == front ? 1:0;
}

void enque(int n)
{
    if(isqfull()==1) return;
    else
    {
        rear=rear+1;
        rear=rear%Queue_size;
        queue[rear]=n;
    }
}

int deque()
{
    if(isqempty()==1) return 0;
    else
    {
        front=front+1;
        front=front%Queue_size;
        return queue[front];
    }
}

int main()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int a;
        cin>>a;
        enque(a);
    }
    while(!isqempty())
    {
        cout<<deque()<<" ";
    }
}

코드에서 %(모듈러) 연산을 해 주고 있는데, 이 이유는 원형 큐를 만들기 위함이다. 직선 형태의 큐로 구현한다면, 값을 빼내다 보면 큐에 값이 가득 차지 않아도 더 이상 큐에 값을 넣을 수 없는 상황이 생기게 된다. 따라서 계속 순환하면서 큐에 값을 넣고 빼기 위해 원형 큐로 구현하고, 이를 위해 모듈러 연산이 필요하다.

큐는 비어있지만 더이상 값을 넣을 수 없다.

 

isqfull 함수를 살펴보면, rear가 front의 뒤에 있을 때 가득 차있다고 반환한다. 하지만 이 때의 큐를 살펴보면 한 자리는 사용되지 않고 낭비되고 있다. 이렇게 구현한 이유는 큐가 비어있는지 가득 차있는지를 구분하기 위함이다. 정말 큐를 가득 채워버리면 현재 비어있는지 차있는지를 구분할 수 없기 때문에 큐에서는 항상 한 자리를 비워둔다.

 

예제 https://www.acmicpc.net/problem/2161

2161번: 카드1

큐의 특성을 이용하면 풀 수 있는 문제이다. 맨 위의 카드를 버리고, 그 밑의 카드를 밑으로 넣는다. 

즉, 맨위를 dequeue 하고, 그다음 카드를 enqueue 한다. 이 과정을 큐가 빌 때까지(front와 rear가 같은 곳을 가리킬 때까지) 반복하면 된다.

 

코드

#include <iostream>
using namespace std;
#define sz 1030
int queue[sz];
int front=0, rear =0;

void enque(int n)
{
    if((rear+1)==front) return;
    rear=rear+1;
    rear=rear%sz;
    queue[rear]=n;
}

int deque()
{
    if(front==rear) return -1;
    front =front+1;
    front = front %sz;
    return queue[front];
}

void change()
{
    int a = deque();
    enque(a);
}

int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        enque(i);
    }
    while(front!=rear)
    {
        int a = deque();
        if(a==-1) break;
        cout<<a<<" ";
        change();
    }
}