Data-Structure - Circular Queues

기존의 queue에는 위와 같은 문제가 있다. 당연히 남는 array의 메모리 공간이 있을테고, 이를 앞으로 다시 땡겨와야 하는 문제가 있다. 이의 시간 복잡도는 O(MQS)인데 무시를 못한다.

 

Circular Queues(1)

기본적인 형태는 위와 같습니다. 또한 동작방식을 정리하자면 아래와 같습니다.

Addition을 할 때에는 rear가 움직이고 Deletion을 하면 front가 움직이는 그러한 간단한 구조입니다.

또한 Circular Queue에는 중요한 규칙이 하나 더 있습니다.

• The position next to MQS-1 is 0
• The position that precedes 0 is MQS-1

MQS가 최대 용량, 즉 위의 그림에서는 7이라고 한다면 0~7인덱스중 MQS-1인 6번 index의 다음 index는 0이고 0의 전 index는 MQS-1인 6번 index와 같다는 것입니다.

 

Array doubling by realloc()

 

우선 realloc으로 circular-queue를 doubling하게 되면 최대 2 * capacity - 2만큼의 원소들을 움직여야 합니다.

최악의 경우에는 위와 같은 경우가 나타나게 됩니다.

Alternative configuration by malloc()

새로운 newQueue의 용량을 원래의 capacity만큼의 2배로 늘립니다. 그다음에 [front + 1~capacity - 1]만큼의 원소들을 newQueue의 0번 인덱스로 옮깁니다. 그리고 원래의 [0~rear]의 원소들을 newQueue의 시작지점으로부터 capacity - front - 1만큼의 지점에 갖다 붙힙니다.

이와 관련된 코드는 아래와 같습니다.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
 
#define ERROR_KEY -100
 
#define MALLOC(p, s)                            \
    if (!((p) = malloc(s)))                     \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }
 
#define REALLOC(p, s)                           \
    if (!((p) = realloc(p, s)))                 \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }
 
typedef struct
{
    int key;
} element;
element *queue;
 
int capacity = 6;
int rear = -1;
int front = -1;
 
void copy(element *startIndex, element *endIndex, element *targetIndex)
{
    /* startIndex ~ endIndex - 1 */
    int increaseIndex = 0;
    while (startIndex != endIndex)
    {
        *(targetIndex + increaseIndex++) = *startIndex;
        startIndex++;
    }
}
void queueFull()
{
    /* allocate an array with twice the capacity */
    element *newQueue;
    MALLOC(newQueue, 2 * capacity * sizeof(*queue));
 
    /* copy from queue to new Queue */
    int start = (front + 1) % capacity;
    if (start < 2)
    {
        /* no wrap around */
        copy(queue + start, queue + start + capacity - 1, newQueue);
    }
    else
    {
        /* queue wraps around */
        copy(queue + start, queue + capacity, newQueue);
        copy(queue, queue + rear + 1, newQueue + capacity - start);
    }
 
    /* switch to newQueue */
    front = 2 * capacity - 1;
    rear = capacity - 1;
    capacity *= 2;
    free(queue);
    queue = newQueue;
}
 
element queueEmpty()
{
    element errorElement;
    errorElement.key = ERROR_KEY;
    fprintf(stderr, "queue is empty, cannot delete element\n");
    return errorElement;
}
 
/* add an item to the queue */
void addq(element item)
{
    rear = (rear + 1) % capacity;
    if (front == rear)
        queueFull();
    queue[rear] = item;
}
 
/* remove front element from the queue */
element deleteq()
{
    if (front == rear)
        return queueEmpty();
    front = (front + 1) % capacity;
    return queue[front];
}
 
void printQueue()
{
    int tempRear = rear, tempFront = front;
    int count = abs(rear - front);
 
    // front부터 시작해서 row를 만날 때 까지
    while (tempFront != tempRear % capacity)
    {
        tempFront = (tempFront + 1) % capacity;
        printf("%d ", queue[tempFront].key);
    }
}
 
int main(void)
{
    MALLOC(queue, sizeof(*queue));
 
    element newElement = {1};
    addq(newElement);
    addq(newElement);
    addq(newElement);
    addq(newElement);
    addq(newElement);
    deleteq();
    deleteq();
    deleteq();
    deleteq();
    addq(newElement);
    deleteq();
    newElement.key = 2;
    addq(newElement);
    newElement.key = 3;
    addq(newElement);
    newElement.key = 4;
    addq(newElement);
    newElement.key = 5;
    addq(newElement);
    newElement.key = 6;
    addq(newElement);
    deleteq();
    newElement.key = 7;
    addq(newElement);
    deleteq();
 
    // 우리가 원하는 circular queue의 상태가 완성 되었다.
    printQueue();
 
    return 0;
}

제가 짠 코드에서의 상황은 위의 그림과 같습니다. 이에 대한 결과는 아래와 같습니다.

circular-queus를 dynamic하게 malloc으로 capacity를 늘리는 것과 addq, deleteq가 정상 작동하는 것을 볼 수 있습니다.