[큐] 큐의 개념과 구현

작성일 | In

이번 글에서는 큐의 개념과, 구현 방법을 간단하게 다루겠습니다.

큐란?

전에 설명한 스택은 후입선출(혹은 선입후출) 의 형태를 가졌습니다. 그러나 이번에 다룰 큐는 선입선출(FIFO)의 형태를 가지고 있습니다.
마치 선착순 과 같은 개념입니다.

그림으로 간단히 나타내봅시다.


스택은 출입구가 한 곳에 다 있었지만, 큐는 한 쪽은 입구, 반대쪽은 출구입니다.
한 쪽에서 넣고 반대 쪽에서 빼다보니 먼저 들어오는 것이 먼저 나오는 선입선출의 구조를 띄게 됩니다.
스택과 마찬가지로, overflow와 underflow오류를 조심해야 합니다.

구현 방법

먼저 큐의 크기를 정해줍니다.

1
#define SIZE 10010

큐를 선언한 뒤, front(가장 앞 쪽 인덱스)와 rear(가장 뒤 쪽 인덱스)를 0으로 설정해줍니다.

1
2
3
int q[SIZE];
int front = 0;
int rear = 0;

push

이제 push기능을 구현합시다.
push를 할 때는 현재 맨 뒤 자리(rear)에 데이터를 넣고 맨 뒤 위치를 표시하는 rear를 한 칸 옮겨줍니다.

1
2
3
void push(int data){
    q[rear++] = data;
}

pop

그 다음은 pop기능을 구현할 것입니다.
pop할 때는 현재 가장 맨 앞 자리(front)에 있는 값을 없애고 front를 한 칸 옮겨줍니다.
underflow검출도 집어넣어줍시다. underflow가 발생할 때에는 -1을 반환하도록 하겠습니다.

1
2
3
4
int pop(){
    if(front >= rear) return -1;
    return q[front++];
}

size(length)

그 다음에는 큐의 길이를 구하는 함수를 만들것 입니다.

1
2
3
int size(){
    return rear-front;
}

empty

그 다음은 비어있는지를 검사하는 함수를 만듭시다.
맨 앞을 가리키는 변수가 맨 뒤를 가리키는 변수보다 크거나 같다면 큐가 비어있다 할 수 있습니다.

1
2
3
4
int empty(){
    if(front >= rear) return 1;
    return false;
}

getFront(front)

pop은 앞에서 빼왔지만, 이번에 구현할 getFront함수는 가장 앞에 있는 데이터를 빼지 않고 읽기만 할 것 입니다.

1
2
3
4
int getFront(){
    if(front >= rear) return -1;
    return q[front];
}

getBack(back)

가장 앞쪽에 있는 데이터를 읽어오는 함수를 만들었으니 이제 가장 뒤쪽에 있는 데이터를 읽어와봅시다.

1
2
3
4
int getBack(){
    if(front >= rear) return -1;
    return q[rear-1];
}

이렇게 해서 기본적인 기능 구현을 완료했습니다.

전체 코드

https://www.acmicpc.net/problem/10845
이 문제를 풀어봅시다.
문제에서 요구한 기능들은 모두 구현했으니 문자열 비교만 잘 해주면 문제를 해결할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <string.h>

#define SIZE 10010

int q[SIZE];
int front = 0;
int rear = 0;

void push(int data){
    q[rear++] = data;
}

int pop(){
    if(front >= rear) return -1;
    return q[front++];
}

int size(){
    return rear-front;
}

int empty(){
    if(front >= rear) return 1;
    return false;
}

int getFront(){
    if(front >= rear) return -1;
    return q[front];
}

int getBack(){
    if(front >= rear) return -1;
    return q[rear-1];
}

int main(){
    int n; scanf("%d", &n);
    while(n--){
        char op[10]; scanf("%s", op);
        if(!strcmp(op, "push")){
            int data; scanf("%d", &data);
            push(data);
        }else if(!strcmp(op, "pop")){
            printf("%d\n", pop());
        }else if(!strcmp(op, "size")){
            printf("%d\n", size());
        }else if(!strcmp(op, "empty")){
            printf("%d\n", empty());
        }else if(!strcmp(op, "front")){
            printf("%d\n", getFront());
        }else if(!strcmp(op, "back")){
            printf("%d\n", getBack());
        }
    }
}