6. Queue

Queue

뒤에서 대기열에 추가하고 앞에서 대기열에서 제거가 발생하는 자료구조입니다. FIFO (First-in-First Out) 목록이라고도합니다.

 

추가는 대기열의 뒤쪽에만 할 수 있으며 제거는 앞쪽에서만 할 수 있습니다.

 

Array implementation of a queue

• 큐에 항목을 저장하기 위해 q[] 배열을 사용합니다.
  • enqueue(): q[tail]에 새로운 항목을 추가합니다.
  • dequeue(): q[head]에 있는 항목을 제거합니다.
• Update head and tail modulo the capacity.
• Add resizing array.

 

 

큐의 문제점

배열의 특성상 큐의 용량(Capacity) 이미 정해져 있으므로, 배열로 구현한 큐의 삽입(Enqueue)과 삭제(Dequeue)의 함수 구현에는 주의해야 할 2가지 사항이 있다.

1. 첫번째로 삽입과 삭제가 이루어진 후 큐의 상태의 처리
2. 비어있음(Empty)과 가득참(Full)을 어떻게 구별할 것인가이다.

 

용량(Capacity)이 5 이고 이미 데이터가 1, 2, 3, 4가 들어있는 큐로 생각해보자.

 

 

Dequeue(1)

Enqueue(5)

 

Dequeue(2)

 

Enqueue(6)

 

지금 구현한 큐는 삽입, 삭제가 이루어질 때마다 실제 용량이 줄어드는 것을 알 수 있다.

공간이 2개나 비어 있는데 6이 큐에 못 들어간다. 이것은 메모리를 효율적으로 사용하지 못한 큐의 예이며,

언젠가 큐의 용량이 0으로 되어버릴 것이다.

 

 

해결책

 

1. 선형큐(Liner Queue)

선형큐(Liner Queue)는 삭제가 이루어질 때 마다 큐의 원소들를 각각 왼쪽으로 옮기는 방식이다.

 

 

이 방식으로 삽입,삭제가 무수히 이행되도 실제용량은 5로 고정되지만.

한번 삭제가 이루어 질 때마다 모든 배열의 원소를 옮기는 것이므로 너무 비효율적이다.

 

2. Circular queue

 

구현

1. front: 첫 번째 항목에서 시계 반대 방향으로 한 칸 옆을 가리키는 변수
2. rear: 마지막 항목을 가리키는 변수

 

기능

Queue createQueue (int maxQueSize);
bool IsFull (Queue queue, int maxQueueSize);
bool IsEmpty (Queue queue);
void Add (Queue queue, int item);
void Delete (Queue queue);
int size(Queue queue);

 

• Queue createQueue (int maxQueSize);

struct Queue {
    int front;
    int rear;
    int capacity;
    int size;
    int * arr;
};

struct Queue* createQueue (int capacity) {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = -1;
    queue->rear = -1;
    queue->size = 0;
    queue->capacity = capacity;
    queue->arr = (int*)malloc(queue->capacity * sizeof(int));
    return queue;
};

 

• Enqueue (Add)
  • rear 가 가리키는 칸을 시계방향으로 한칸 이동 시킨다.
  • 만약 rear가 배열의 끝이고 포화상태가 아니라면 q[rear]에 항목을 삽입한다.
  → 배열의 포화상태 여부를 판단하기 위하여 배열의 1칸은 비워둡니다. (rear+1)%arraysize == front 라면 배열이 포화상태인걸로 판단하여 데이터 삽입이 이루어지지 않게 됩니다.

void Enqueue (struct Queue* queue, int item) {
    if (!IsFull(queue)) {
        queue->rear = (queue->rear + 1) % queue->capacity;
        queue->arr[queue->rear] = item;
        queue->size++;
        printf("front = %d, rear = %d\n", queue->front, queue->rear);
    }
    else {
        printf("Queue is full\n");
        return;
    }
}

 

 

• Dequeue (Delete)
  • front가 가리키는 칸을 시계방향으로 한칸 이동시킨다.
  • q[front] 데이터를 배열에서 가지고 옵니다.
  • → rear==front 이라면 배열이 공백상태인걸로 판단하여 Dequeue가 실행되지 않습니다.
  

void Dequeue (struct Queue* queue) {
    if (!IsEmpty(queue)) {
        queue->front = (queue->front + 1) % queue->capacity;    // circular queue
        queue->size--;
        printf("Removing  %d\n", queue->front);
    }

    else {
        printf("Queue is empty\n");
        return;
    }
}

 

 

• Empty
  • 아래의 사진처럼 하나씩 제거하다 보면 front == rear인 상황이 발생하는데 이 때가 빈큐의 경우이다.
  • 따라서 빈 큐를 생성할 때 front == rear == 0으로 초기화 해준다.
  

bool IsEmpty(struct Queue *queue) {
    return queue->rear == queue->front;
}

 

 

• Full
  • 아래의 사진처럼 하나씩 추가하다보면 front == rear인 상황이 발생하는데 가득찬 큐의 경우이다.
  • front == rear 일 때 full인지 empty인지 식별이 안되므로 큐를 한칸 비워놓습니다.
  

bool IsFull (struct Queue* queue) {
    return (queue->rear+1)%queue->capacity == queue->front;
}