큐, 원형큐 개념과 C언어로 구현하기

큐(Queue)란?

큐(Queue)는 스택(LIFO)와 달리 FIFO(First In First Out) 구조로

먼저 들어온 데이터가 가장 먼저 나가는 자료구조입니다.

간단히 말하면 마트 계산대 줄처럼 먼저 줄 선 사람이 먼저 계산을 받는 원리와 동일합니다.

 

가장 나중에 들어온 데이터가 가장 먼저 나갔던 스택과 정반대 되는 개념입니다.

 

stack은 top을 기준으로 판별하였다면 

Queue는 front와 rear을 사용을 합니다.

 

왜 2개를 사용할까요?

Queue에는 연산 방식이 2개 있습니다.

뒤에 데이터를 추가하는 enqueue가 있고

앞에서 데이터를 꺼내주는 dequeue가 있습니다.

 

아래 예시 참고해주세요

 

위 사진에서는 front가 배열의 -1의 인덱스에 위치해있고 rear는 4에 위치해있습니다.

dequeue를 실행했습니다

front += 1 이 이루어졌습니다!

이걸 간단히 코드로 표현해보면 어떨까요?

 

int dequeue(){

    if (front < MAX_SIZE){

    return list[++front];

}

}

 

스택의 pop이랑 비슷한거 아니야? 하실 수 있겠지만 그 생각이 맞습니다 앞에서 pop한다고 생각하시면 편해요

 

자 그럼 다음 그림 보겠습니다

 

이번엔 enqueue로 6을 리스트에 추가를 해줬습니다!

rear가 ++ 되면서 한칸 오른쪽으로 옮겨갔죠?

뭐야 front도 오른쪽으로 가는데 rear도 오른쪽으로 가는게 맞아? 할 수 있지만 맞습니다

 

이건 여러분들이 push하는것과 똑같습니다!

 

사실상 큐는 스택에서 pop을 앞에서 해주는 것과 다름없습니다!

 

#include <stdio.h>
#define SIZE 5

int queue[SIZE];
int front = -1, rear = -1;

int is_empty() { 
	return front == rear; 
}
int is_full() { 
	return rear == SIZE - 1; 
}

void enqueue(int val) {
    if (is_full()) {
        printf("큐가 가득 찼습니다.\n");
    } else {
        queue[++rear] = val;
    }
}

int dequeue() {
    if (is_empty()) {
        printf("큐가 비었습니다.\n");
        return -1;
    } else {
        return queue[++front];
    }
}

int main() {
    enqueue(10); // front=-1, rear=0
    enqueue(20); // front=-1, rear=1
    enqueue(30); // front=-1, rear=2

    printf("Dequeue: %d\n", dequeue()); // front=0 (queue[0]=10 제거)
    printf("Dequeue: %d\n", dequeue()); // front=1 (queue[1]=20 제거)

    enqueue(40); // rear=3
    enqueue(50); // rear=4
    enqueue(60); // 큐가 가득 참 (rear=4, SIZE-1=4)

    while (!is_empty()) {
        printf("Dequeue: %d\n", dequeue());
    }

    return 0;
}

 

이 방식의 문제점은 무엇일까요?

is_full 함수를 보면 알 수 있습니다

 

여러분은 이게 Queue가 꽉찬걸로 보이시나요?

앞에 공간이 한참 남는데 return rear == SIZE -1에 걸려 full상태로 취급당하게 됩니다.

 

그럼 어떻게할까요?

 

앞과 끝을 이어서 동그랗게 말아보면 어떨까요

 

그게 바로 원형 Queue입니다.

 

이번에도 front는 첫번째 요소 하나 앞의 인덱스

rear은 마지막 요소의 인덱스에 위치하고 있습니다.

방식은 일반 큐를 다루는것과 크게 다르지 않습니다.

 

enqueue를 하게되면 

 

이렇게 될 것이고

 

dequeue를 한다면 이렇게 되겠죠

 

그렇다면 is_empty 즉 큐가 비어있는 형태는 

이렇게 공백은 front == rear 상태 이고

 

이것이 포화 상태가 되겠죠 

즉 is_full은 front  == (rear + 1) % SIZE 라는 식을 도출 할 수 있습니다.

 

어 근데 하나 더 채울 수 있지 않나요? 라고 말씀하실 수 있는데

그렇게 되면 front == rear이기 때문에 공백 상태랑 구분하기 어려워 한칸을 비워둡니다.

 

아래는 기본 구현입니다.

#include <stdio.h>

#define SIZE 5

int queue[SIZE];
int front = 0, rear = 0;

int is_empty() {
    return front == rear;
}

int is_full() {
    return (rear + 1) % SIZE == front;
}

void enqueue(int val) {
    if (is_full()) {
        printf("큐가 가득 찼습니다.\n");
    } else {
        rear = (rear + 1) % SIZE;
        queue[rear] = val;
    }
}

int dequeue() {
    if (is_empty()) {
        printf("큐가 비었습니다.\n");
        return -1;
    } else {
        front = (front + 1) % SIZE;
        return queue[front];
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);

    printf("Dequeue: %d\n", dequeue());
    printf("Dequeue: %d\n", dequeue());

    enqueue(50);
    enqueue(60);
    enqueue(70);  // 큐가 가득 차서 실패

    while (!is_empty()) {
        printf("Dequeue: %d\n", dequeue());
    }

    return 0;
}

 

 

 

 

 

연습 문제입니다.

 

입력 예시 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0

출력 21

 

입력 예시: 10 20 -1 30 -1 40 50 -1 0

출력 70

 

아래는 예시 정답 코드입니다.

 

#include <stdio.h>
 
#define SIZE 20
 
int queue[SIZE];
int front = -1, rear = -1;
 
void enqueue(int val) {
    if (rear < SIZE - 1) queue[++rear] = val;
}
 
int dequeue() {
    if (front < rear) return queue[++front];
    return -1;
}
 
int is_empty() {
    return front == rear;
}
 
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n == -1) dequeue();
        else if (n == 0) {
            if (!is_empty())
                printf("%d", queue[front + 1] + queue[rear]);
            else
                printf("-999");
            break;
        } else {
            enqueue(n);
        }
    }
    return 0;
}

 

 

 

두번째는 원형 큐 문제입니다.

 

 

 

정답 예시입니다.

 

#include <stdio.h>
 
 
typedef struct Queue {
    int data[6];
    int front, rear;
}Queue;
 
void init(Queue* q) {
    q->front = q->rear = 0;
}
 
int is_full(Queue* q) {
    return (q->rear + 1) % 6 == q->front;
}
 
int is_empty(Queue* q) {
    return q->front == q->rear;
}
 
void enqueue(Queue* q, int data) {
    if (!is_full(q)) {
        q->rear = (q->rear + 1) % 6;
        q->data[q->rear] = data;
    }
}
 
int dequeue(Queue* q) {
    if (!is_empty(q)) {
        q->front = (q->front + 1) % 6;
        return q->data[q->front];
    }
}
 
int main() {
    int a;
    Queue q;
 
    init(&q);
    while (1) {
        scanf("%d", &a);
        if (a < 0) 
            dequeue(&q);
        else if(a>0)
            enqueue(&q, a);
        else if (a == 0) {
            while (1) {
                if (is_empty(&q)) return 0;
                printf("%d ", dequeue(&q));
            }
        }
             
         
    }
    return 0;
}

 

구조체를 사용했습니다.

여러 개의 큐를 동시에 관리해야 할 때 편리하기 때문에 이런 방식으로 풀었지만 사실

이 문제는 큐가 하나 뿐이라 구조체를 사용하지 않는게 더 편리하긴 합니다.

구조체를 사용하지 않고 이 문제를 푼 원형 큐입니다.

#include <stdio.h>

#define SIZE 6
int queue[SIZE];
int front = 0, rear = 0;

int is_empty() { return front == rear; }
int is_full() { return (rear + 1) % SIZE == front; }

void enqueue(int val) {
    if (!is_full()) {
        rear = (rear + 1) % SIZE;
        queue[rear] = val;
    }
}

void dequeue() {
    if (!is_empty()) {
        front = (front + 1) % SIZE;
    }
}

int main() {
    int input;

    while (scanf("%d", &input) != EOF) {
        if (input > 0)
            enqueue(input);
        else if (input < 0)
            dequeue();
        else if (input == 0)
            break;
    }

    // 큐에 남은 값 출력
    int i = (front + 1) % SIZE;
    while (i != (rear + 1) % SIZE) {
        printf("%d ", queue[i]);
        i = (i + 1) % SIZE;
    }

    return 0;
}

코드구조가 더 간단해진 것을 보실 수 있습니다!

 

 

 

 

 

여담으로...

파이썬에서는 위 문제를 10줄이면 구현 가능합니다

from collections import deque
tmp = deque()
li = list(map(int, input().split()))
for i in range(len(li)):
    if li[i] > 0 and len(tmp) < 5:
        tmp.append(li[i])
    elif li[i] < 0 and tmp:
        tmp.popleft()
    elif li[i] == 0:
        print(*tmp)