[DS] Queue(큐) & Circular Queue(순환 큐)

# 큐

- 큐: 처리를 기다리고 있는 작업(원소)들의 리스트

- 선입 선출(FIFO, First-In, First-Out) 방식 / FCFS (First-Come, First-Served)

- 우선순위를 부여하지 않음

- 새로운 원소는 큐의 맨 뒤(rear)에 삽입되고 큐의 맨 앞(front) 원소가 먼저 삭제됨

- insert된 순서대로 처리됨

- 스택과 달리 큐의 맨 앞 원소와 맨 뒤 원소를 가리키기 위한 두 개의 front와 rear 포인터가 필요

Q = [a0, a1, ..., an-1]

 

 

# 큐의 구현

- front: delete할 때 사용

- rear: stack에서의 top과 같은 역할을하며 add할 때 사용

- front와 rear 포인터의 초기 값 = -1 ← 일반적으로 이렇게 설정

- 새로운 원소는 rear 포인터 다음 위치에 추가되고, front 포인터가 가리키는 원소가 먼저 큐에서 삭제됨

- addq()

  > full queue: rear == QUEUE_SIZE-1 (upper bound)

  > full queue가 아닐 때: rear를 증가하고 해당 인덱스에 새로운 원소를 저장

void addq(int item){
  if(rear == QUEUE_SIZE - 1){ // full queue
    printf("full queue");
    return;
  }
  queue[++rear] = item;
  print_queue();
}

 

- deleteq()

  > empty queue: rear == front, -999 반환

  > empty queue가 아닐 경우 front를 증가하고 해당 인덱스에 원소를 return

int deleteq(){
  if(front == rear){ // empty queue
    printf("empty full");
    return -999;
  }
  return queue[++front];
}

 

- 큐 구현

[코드]

#include <stdio.h>
#define QUEUE_SIZE 100

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

void print_queue();
void addq(int item);
int deleteq();

int main(){
    int temp;

    addq(3);
    addq(5);
    addq(7);

    temp = deleteq();
    print_queue();

    return 0;
}

void print_queue(){
    // 큐는 앞에서부터 삭제하기 때문에 인덱스 0, 1, ..에 값이 존재하지 않을 수 있음

    int i;
    for(i=front+1;i<=rear;i++){
        printf("%d ",queue[i]);
    }
    printf("\n");
}

void addq(int item){
    if(rear == QUEUE_SIZE -1){ // full queue
        printf("full queue");
        return;
    }
    queue[++rear]=item;
    print_queue();
}

int deleteq(){
    if(front==rear) {//empty queue
        printf("empty queue");
        return -999;
    }
    return queue[++front];
}

 

[실행결과]

 

 

# 일반 큐의 문제점

- item이 삽입/삭제됨에 따라 큐 안에 item들이 오른쪽으로 이동됨

- 실제로 Queue full signal이 큐가 가득찬 것을 의미하지 않음

  > 원소들이 삭제된 인덱스의 공간들이 낭비되고 있음

- 큐를 다시 사용하기 위해서는 item을 왼쪽으로 옮기는 과정이 필요

  > worst case: n-1 times (shift 횟수)

  > TC: O(n)

- 해결방법: 순환 큐

 

 

# 순환 큐

- 순환 큐: 큐의 오른쪽 끝을 반대편 끝과 연결하여 원소가 이동할 필요 없이

전체 공간을 모두 사용할 수 있음 / 원형큐라고도 함

- empty 조건: front == rear

  > empty 조건과 구별하기 위해서 순환 큐에서 n개의 공간을 할당할 때

     실질적으로는 n-1만큼의 공간만을 사용할 수 있음

 

 

# 순환 큐 구현

- addcq()

  > 순환 큐에 여유 공간이 있는지 확인하는 과정 필요

  > rear 포인터의 값을 1 증가시킨 후 큐의 크기로 나눈 나머지를 rear으로 다시 설정

  > 다시 설정한 값이 front와 같으면 순환 큐에 공간이 없는 것 → full 조건

  > 여유 공간이 있다면 rear 위치에 값을 저장

void addcq(int item){
    if(front==((rear+1)%QUEUE_SIZE)){ // full 조건
        printf("queue full");
        return;
    }
    rear = (rear+1)%QUEUE_SIZE;
    cqueue[rear] = item;
    print_queue();
}

 

 

- deletecq()

  > front와 rear 값을 비교하여 빈 큐인지 확인

  > 삭제할 원소가 남아 있으면 front를 1 증가시킨 후 해당 위치의 원소를 반환

int deletecq(){
    if(front==rear){ // empty 조건
        printf("queue empty");
        return -999;
    }
    front=(front+1)%QUEUE_SIZE;
    return cqueue[front];
}

 

- 순환 큐 구현

[코드]

#include <stdio.h>
#define QUEUE_SIZE 100

int front, rear;
int cqueue[QUEUE_SIZE];
void addcq(int item);
int deletecq();
void print_queue();

int main() {
    int temp;
    front = rear = 0;

    addcq(11);
    addcq(13);
    addcq(17);
    addcq(19);
    temp = deletecq();
    print_queue();
    temp = deletecq();
    print_queue();
    temp = deletecq();
    print_queue();
    temp = deletecq();
    print_queue();
    return 0;
}

void addcq(int item){
    if(front==((rear+1)%QUEUE_SIZE)){ // full 조건
        printf("queue full");
        return;
    }
    rear = (rear+1)%QUEUE_SIZE;
    cqueue[rear] = item;
    print_queue();
}

int deletecq(){
    if(front==rear){ // empty 조건
        printf("queue empty");
        return -999;
    }
    front=(front+1)%QUEUE_SIZE;
    return cqueue[front];
}

void print_queue(){
    int i=front;
    while(i!=rear){ // i가 rear 같지 않다면
        i=(i+1)%QUEUE_SIZE;
        printf("%d ",cqueue[i]);
    }
    printf("\n");
}

 

[실행결과]