큐(Queue)_2

안녕하세요!!

글을 자주 쓴다는 게 생각보다 쉽지 않네요...

항상 다짐은 하는데 할 거 다 하고 나면 하기 귀찮다는 마음이 올라와서 자주 쓰지 못하는 것 같네요..

앞으로는 진짜 미루지 않고 항상 글을 쓰는 부지런한 사람이 되어야겠어요 ㅎ

---

이번에 알아볼것은 원형큐 입니다

저번에 선형 큐에 대해서 알아보았는데

선형 큐에서의 문제점은 enqueue와 dequeue를 사용했을 시에

데이터가 앞으로 당겨져 오지 않다가 결국에는 데이터가 쉽게 꽉 차는 현상이 발생하였는데

물론 이제 내부에 for문을 작성함으로써 데이터를 제일 앞으로 오게끔 만들어 줄 수 도 있지만

그러면 시간복잡도 O(N)을 가지는 연산을 수행하여야 하기 때문에 나중에는 비효율적인 코드가 될 수도 있기 때문에

그것을 해결하기 위해서 원형 큐라는 것을 사용하게 되는 겁니다

전체적인 추상 자료형을 구상하는 부분에 있어서는 선형 큐와는 똑같습니다

대신 이름에서 알 수 있듯이 데이터가 처음과 끝이 연결되어있는 구조로 되어있고

그렇기 때문에 for문을 통해 굳이 데이터를 옮길 필요가 없어지게 됨으로써 시간 복잡도에서 이익을 가질 수 있습니다

 

큐의 추상 자료형이 궁금하다면 <큐(Queue)_1>의 글을 읽고 오시면 될 것 같아요 ㅎㅎ

---

원형 큐를 한번 코드로 구현해 보도록 할게요!!

작성 언어 : C언어

typedef int element;
typedef struct {
    element data[MAX_QUEUE_SIZE];
    int front, rear;
}QueueType;

void init_queue(QueueType *q){
    q->front = 0;
    q->rear = 0;
}

void error(char *message){
    fprintf(stderr, "%s\n", message);
    exit(1);
}

 

int is_empty(QueueType *q){
    return (q->front == q->rear);
}

int is_full(QueueType *q){
    return ((q->rear+1)%MAX_QUEUE_SIZE == q->front);
}

 

int dequeue(QueueType *q){
    if(is_empty(q)){
        error("큐가 비었습니다");
    }
    q->front = (q->front+1)%MAX_QUEUE_SIZE;
    return q->data[q->front];
}

int peek(QueueType *q){
    if(is_empty(q)){
        error("큐가 비었습니다");
    }
    return q->data[(q->front+1)%MAX_QUEUE_SIZE];
}

void enqueue(QueueType *q,element value){
    if(is_full(q)){
        error("큐가 가득찼습니다");
    }
    q->rear = (q->rear+1)%MAX_QUEUE_SIZE;
    q->data[q->rear] = value;
}

이번 코드에서 눈여겨서 봐야 할 부분은

실제로 우리가 배열을 원처럼 만들 수가 없기 때문에 컴퓨터 원처럼 착각하도록 만들어 주는 것입니다

여기서는 큐의 크기를 5로 정적으로 주었습니다

그러면 배열에서의 인덱스 값은 0~4까지 가지게 되는데 rear가 4에 도달하게 되었을 때 원이라면 다음 값이 0이 되어야겠죠??

그래서 이제 (q->rear+1)% MAX_QUEUE_SIZE 선언해줌으로써 해결해 줄 수 있습니다

MAX_QUEUE_SIZE로 나머지 값을 취해줌으로써 rear값이 4 -> 0으로 만들어 줄 수 있는 것입니다

---

이번에 원형큐라는 것을 짧게 알아보았는데 저에게 부족한 점이 보이거나 궁금한 점이 있으시다면 밑에 댓글로 남겨주세요!!

읽어 주셔서 감사합니다!!