[C] 큐

후입선출구조를 가지는 스택과는 다르게 큐는 데이터의 삽입과 삭제의 위치가 반대인 선입선출 구조이다. 즉 먼저 넣었던 데이터가 먼저 나오는 자료구조이다. 데이터를 꺼내오는 위치와 넣는 위치가 다르기 때문에 큐는 2개의 인덱스를 사용한다. 주로 front 와 rear로 명명하여 사용한다. 데이터를 삽입하는 과정을 enQueue 라고 하며, 데이터를 꺼내는 과정을 deQueue라고 한다면 각각 스택에서의 push 와 pop의 과정과 대응된다.

큐를 구현하는 가장 간단한 방법은 배열을 사용하는 것이다. front 와 rear의 값이 초기화 이후에 같은 값을 가지면 모든 요소를 꺼낸 것이므로 큐가 비었다는 뜻이며, rear의 인덱스가 배열 끝에 다다르면 큐가 다찼다는 것을 의미한다.

#include<stdio.h>
#define q_size 100

int Q[q_size];
int front = -1;
int rear = -1;

int isFull(void){
    if (rear == q_size -1) return 1;
    else return 0;
}

int isEmpty(void){
    if (rear == front) return 1;
    else return 0;
}

void enQueue(int x) {
	if (isFull()) return;
    else Q[++rear] = x;
    return;
}

int deQueue() {
    if (isEmpty()) return -1;
    else return Q[++front];
}

int main() {
	enQueue(1);
    enQueue(2); 
    printf("%d\n", deQueue());
    
    enQueue(3);

    printf("%d\n", deQueue());
    printf("%d\n", deQueue());

    return 0;
}

1
2
3

큐에 데이터를 넣을 때에는 큐가 비었는지 혹은 다 찼는지부터 파악해야한다. 위 예제는 함수형태로 조건들을 확인하며 알고리즘 문제풀이 처럼 단일 문제해결에서는 간단하게 구현한다. 알고리즘을 자세히 보면 실제 데이터가 삭제되는 것이 아니라 인덱스가 훑고 지나가는 것을 알 수 있다. 큐의 인덱스는 항상 증가하기 때문에 마지막에 도달하면 더 이상 사용할 수 없게 된다. 이러한 단점을 극복하기 위해 큐의 끝과 처음을 이어서 원형형태로 구현한 원형 큐가 있다. 아래에 간단한 형태의 큐 코드를 소개하고 이후 원형 큐 코드를 소개한다.

#include<stdio.h>

int Q[100];
int front = -1;
int rear = -1;

int main() {
	Q[++front]=1;
    Q[++front]=2;

    printf("%d\n", Q[++rear]);
    
    Q[++front]=3;

    printf("%d\n", Q[++rear]);
    printf("%d\n", Q[++rear]);

    return 0;
}

1
2
3

#include <stdio.h>
#define q_size 10

int front;
int rear;
int Q[q_size];

int isFull(void){
    if ((rear+1) % q_size == front) return 1;
    else return 0;
}

int isEmpty(void){
    if (rear == front) return 1;
    else return 0;
}

int main() {

    if (isFull());
    else {
        rear = (rear +1 ) % q_size; 
        Q[rear]= 1;
    }

    if (isFull());
    else {
        rear = (rear +1 ) % q_size; 
        Q[rear]= 2;
    }

    front = (front +1) % q_size;
    if (isEmpty());
    else printf("%d\n", Q[front]);
    
    return 0;
}

1