Queue

Queue

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조입니다. 하지만 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입(FIFO, First In First Out)인 점이 스택과 다릅니다.

생활에서 볼수 있는 큐의 에는 은행창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열을 들 수 있습니다.

큐에 데이터를 넣는 작업을 enqueue라하고, 데이터를 꺼내는 작업을 dequeue 라고합니다. 또 데이터를 꺼내는 쪽을 front라 하고, 데이터를 넣는 쪽을 rear라고 합니다. 배열과 front, rear 변수를 사용해 쉽게 queue를 구현할 수 있습니다.

front와 rear라는 변수를 도입한 이유는 현실세계처럼 queue를 컴퓨터상에서 구현하려면 많은 자원을 필요로 합니다. 배열에 1,2,3,4,5라는 데이터가 들어 있을 때 1의 차례가 와서 1을 제거하면 2,3,4,5를 앞으로 이동시켜서 다음 차례를 기다리도록 해야합니다. 이렇게 데이터가 5개정도일 때는 상관이 없지만 데이터가 100개, 1000개 있다면 이렇게 queue를 구현하는 것은 효율적인 상황이 아닙니다. 이를 해결하기 위해 front와 rear라는 변수를 도입합니다. 가장 먼저 들어온 데이터를 front가 가리키도록 하고 fornt에 있는 데이터를 제거 할 때마다 front를 한칸 이동시켜 다음차례의 데이터를 가리키도록 하면 됩니다. rear는 데이터의 삽입할 위치를 가리키기 위해서 사용합니다. 데이터를 삽입할때 rear를 사용해서 마지막에 온 데이터를 표시하면 그 다음에 들어온 데이터를 어디에 삽입시켜야 할지 손쉽게 알 수 있습니다.

하지만 이렇게 queue를 구현 했을 때도 문제는 남아 있습니다. 그래서 배열 형태로 선형 큐를 구현할 수도 있지만 주로 원형큐를 사용합니다. 선형큐를 사용하면 rear값이 계속 증가하고 앞에 제거되며 front를 증가시킬때 front 앞부분의 메모리 공간이 낭비되는 현상이 발생합니다.

이러한 문제를 해결하기 위해 원형큐를 사용합니다. 선형적인 데이터 구조로 front와 rear를 도입해 queue를 구현했기 때문에 front와 rear 사이에 공간에만 데이터를 사용할 수 있고 rear가 끝에 도달하면 더이상 데이터를 삽입할 수 없는 문제가 있습니다. 이를 해결하기 위해서 순환큐를 사용합니다. 순환 큐는 배열의 처음과 끝을 이어 붙인 상태로 하지만 C언어에서는 이러한 형태는 없기 때문에 어디 까지나 논리적인 구조이고 이를 코드로 구현하기 위해서는 rear가 배열의 마지막 인덱스에 도달한다면 배열의 처음 인덱스로 이동하하여 다시 데이터를 추가하도록 해야합니다. 그리고 front와 rear가 만나게 되면 이제 진짜 queue가 꽉찬 상태가 됩니다.

큐의 응용분야 : 컴퓨터의 운영체제에서 여러 작업들의 스케줄링

스택과 마찬가지로 큐 역시 컴퓨터 알고리즘에서 많이 사용되는 중요한 기본 자료형

*주의 사항

1.queue 자료구조가 빈 상태 (rear==front)

2. 큐에서 가득 찬상태는 rear가 1증가해서 front와 나머지가 같을때 꽉 찬 상태로 정의 해야함. 그렇지 않다면 데이터를 Queue에 Push할수 없음. (Empty 상태와 구분되지 않기 때문 )

그렇게 된다면 항상 큐의 front가 가리키는 인덱스는 비어있는 상태로 유지되는데 이를 통해 full과 empty를 구분한다. 만약 front에 자리까지 원소가 삽입된다면 empty(rear == front)조건과 구분되지 않기 때문이다.

꽉 찬 상태 조건은 한 바퀴 돌아서 모든 메모리에 꽉 찬 상태로 넣고 rear와 front가 같아진 때만 생각한다면 이상할게 없지만 초기 상태 rear와 front가 같을때도 데이터를 넣을 수 없음.

그러나 실제로 모든 값이 (rear와 front가 같을때를 빈상태)로 정의했기 때문에 빈상태와 꽉 찬 상태가 조건이 같아지는 경우가 발생함 그래서 rear의 나머지숫자가 front의 나머지보다 하나 작을때를 꽉 찬 상태로 정의함

3. 0.rear와 front를 먼저 증가시키고 함수요청 처리를 할수도 있고, 함수요청 처리후 증가처리 할수 있다. 이 때 주의 할 점은 rear, front 모두 증가를 먼저하든 증가를 나중에하든 둘다 똑같이 해야함

Queue.h

#pragma once

typedef struct q_ {
    int* queue;
    int front, rear;
    int capacity;
}Queue;

void Push(Queue* q, int data);
int Pop(Queue* q);
void InitQueue(Queue* q, int cap);
void UninitQueue(Queue* q);

Queue.cpp

#include <stdlib.h>
#include "Queue.h"
//서버(Queue)
void Push(Queue* q, int data) {
    if ((q->rear + 1) % q->capacity == q->front)
        return;

    //rear가 0,1,2,3,4 가 되는 코드
    /*rear = rear + 1;
    if (rear == 5)
        rear = 0;*/

    q->rear = (q->rear + 1) % q->capacity; //위 주석 처리 코드와 같음(rear가 0,1,2,4가 되는 코드)
    q->queue[q->rear] = data;
}
int Pop(Queue* q) {
    if (q->front == q->rear)
        return 0xfffffff; //오류값으로 임의의 큰 값 지정

    //Push에서 대입전 rear를 증가시키고 대입시켰으므로 
    //Pop에서도 증가시키고 값을 빼야 해당 위치의 값을 정확히 값의 위치로 가리키게됨 
    q->front = (q->front + 1) % q->capacity;
    return q->queue[q->front];
}
void InitQueue(Queue* q, int cap) {
    q->queue = (int*)malloc(sizeof(int) * cap);
    q->capacity = cap;
    q->front = q->rear = 0; //front 와 rear를 같게만 해주면 됨 0,1,2,3,4 어느것으로 초기화 하든 상관없음

}
void UninitQueue(Queue* q) {
    free(q->queue);
    q->front = q->rear = 0; //여기서는 Uninit 할거 없지만해줌
}

Client.cpp

#include <stdio.h>
#include "Queue.h"
int main() {

    Queue q;
    InitQueue(&q,100);
    Push(&q, 10);
    Push(&q, 20);
    Push(&q, 30);
    Push(&q, 40);
    Push(&q, 50);

    printf("queue:%d\n", Pop(&q));
    printf("queue:%d\n", Pop(&q));
    printf("queue:%d\n", Pop(&q));
    printf("queue:%d\n", Pop(&q));
    printf("queue:%d\n", Pop(&q));
    UninitQueue(&q);
}

Client.cpp

#기억하면 좋을 예외 처리 아이디어

정수론에서 중요한 나머지를 이용해서 100과 0을 같은 상태로 표시

해석 :

rear에 1을 더한 값을 배열 크기로 나눈 값의 나머지가 front와 같을 때 큐의 자료구조는 꽉 찬 상태라는 아이디어

rear와 1은 모두 배열의 크기(MAX_N)수 보다 작다. 즉, 배열의 크기로 나눈 나머지는 rear + 1이다. front가 rear+1과 같으면 큐자료구조는 곽찬 상태라는 의미다.(rear가 최대 값을 넘어서 다시 0부터 시작해서 돌아서 front보다 하나 작은 위치 일 때 꽉찬 상태) 그런데 이때이때 (rear+1 == front) 이렇게 조건을 쓰면,아직 rear가 0으로 돌아오지 않은 상태일때는 즉 MAX_N이 100일때, rear가 99일때 꽉찬 상태이지만 1을 더하면 rear +1은 100이고 front는 0일때 꽉 찬 상태이지만 꽉 찬 상태를 표시 하지 못한다.

그래서 수학 정수론에서 중요한 나머지를 이용하는 것이다. 모든 수를 나머지로 분류해서 100과 0을 같은 상태로 표시 하기 위함이다.