※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.
환형 배열로 큐 구현하기
큐의 경우 배열보다는 연결리스트로 구현하는 것이 좀 더 간단한데,
배열은 크기가 정해져있기 때문이다.
환형 배열(Circular array)을 이용해 큐를 구현하면 배열의 끝에 도달할 때마다 재할당을 해서 크기를 늘리지 않아도 된다.
배열의 앞에서부터 순서대로 데이터들을 저장한다.
데이터를 삭제하게 되면, 먼저 저장한 데이터부터(앞에서부터) 지워나간다.
이렇게 해서 배열의 앞에는 공간이 있고, 배열의 끝에는 데이터가 저장되어있는 상태에서 새로운 원소를 또 추가한다면,
다시 배열의 첫번째 칸에서부터 추가한다.
이와 같이 원형으로 순환하며 데이터를 저장한다.
헤더 파일은 연결리스트 구현 때 만든 파일을 그대로 사용한다.
terminate() 함수와 get_size() 함수도 완전히 동일하다.
구조체 정의하기
queueADT.c
#include <stdio.h>
#include <stdlib.h>
#include "queueADT.h"
#define INIT_CAPACITY 100
struct queue_type {
Item *contents; /* 배열 */
int front;
int rear;
int size; /* 저장된 데이터의 개수 */
int capacity; /* 배열 contents의 크기 */
};
함수 정의하기
create(), destroy()
Queue create()
{
Queue q = (Queue)malloc(sizeof(struct queue_type));
if (q == NULL)
terminate("Error in create: queue could not be created.");
q->contents = (Item *)malloc(INIT_CAPACITY * sizeof(Item));
if (q->contents == NULL) {
free(q);
terminate("Error in create: queue could not be created.");
}
q->front = 0;
q->rear = -1; /* */
q->size = 0;
q->capacity = INIT_CAPACITY;
return q;
}
void destroy(Queue q)
{
free(q->contents);
free(q);
}
empty(), full()
void make_empty(Queue q)
{
q->front = 0;
q->rear = -1;
q->size = 0;
/* q->contents는 그대로 두고(제거X) 초기화만 시킨다 */
}
bool is_empty(Queue q)
{
return q->size == 0;
}
bool is_full(Queue q)
{
return q->size == q->capacity;
}
enqueue(), dequeue(), peek()
void enqueue(Queue q, Item i)
{
if (is_full(q))
reallocate(q);
q->rear = (q->rear + 1)%(q->capacity);
/* if (q->rear +1) = capacity, q->rear = 0; */
q->contents[q->rear] = i;
q->size++;
}
Item dequeue(Queue q)
{
if (is_empty(q))
terminate("Error in dequeue: queue is empty.");
Item result = q->contents[q->front];
q->front = (q->front + 1)%(q->capacity);
/* 배열의 끝에 도달(q->front+1 == capacity)하면 다시 0으로 돌아감 */
q->size--;
return result;
}
Item peek(Queue q)
{
if (is_empty(q))
terminate("Error in peek: queue is empty.");
return q->contents[q->front];
}
enqueue() 함수에서
q->rear = (q->rear + 1)%(q->capacity);
위 식의 결과는
만약 q->rear + 1이 capacity보다 작다면,
그대로 q->rear + 1 이 되어 마지막 원소 다음 자리에 Item을 삽입하게 된다.
만약 q->rear + 1 == capacity라면 결과는 0이 되어
배열의 첫번째 칸에 Item을 삽입하게 된다.
이렇게 하여 앞에서 언급한 것처럼 순환하는 배열(Circular array)을 만들 수 있다.
dequeue() 함수에서도 비슷한 식을 사용한다.
q->front = (q->front + 1)%(q->capacity);
dequeue() 함수에서는 front를 이동시키기 전에
front가 원래 가리키고 있던 데이터를 따로 저장해뒀다가 반환한다.
이렇게 코드를 작성하는 것이 간결하지 못하게 느껴진다면
또다른 방법이 있다.
front가 큐의 첫번째 데이터가 아닌 첫번째 데이터의 한칸 앞을 가리키도록 하고
그 상태에서
q->front = (q->front + 1)%(q->capacity); 로
front를 이동시킨 다음,
front가 가리키는 데이터를 반환하면 그것이 이동 전의 원래 데이터가 된다.
이렇게 하면 원래 데이터를 따로 저장해두는 과정을 생략할 수 있으므로 코드가 좀 더 간략해진다.
(front가 계속 한 칸 앞 데이터를 가리키기 때문)
reallocate()
void reallocate(Queue q)
{
Item *tmp = (Item *)malloc(2 * q->capacity * sizeof(Item));
if (tmp == NULL) {
terminate("Error in create: queue could not be expanded.");
}
int j = q->front;
for (int i=0; i<q->size; i++) {
tmp[i] = q->contents[j];
j = (j + 1)%q->capacity;
}
free(q->contents);
q->front = 0;
q->rear = q->size - 1;
q->contents = tmp;
q->capacity *= 2;
}
