C언어 자료구조 큐 개념과 구현(2) queue



1.이번시간은 배열로 큐를 구현해보도록 합니다.







1)큐에서의 배열 realloacte()  










//참고 front가 항상 rear보다 오른쪽에 있는 것은 아니다.
헤더파일은 동일.
#include <stdbool.h>
typedef int Item;
typedef struct queue_type *Queue;
Queue create();
void destroy(Queue q);
void make_empty(Queue q);
bool is_empty(Queue q);
void enqueue(Queue q, Item i);
Item dequeue(Queue q);
Item peek(Queue q);
int get_Size(Queue q);
struct queue_type {
Item *contents;
int front;
int rear;
int size;
int capacity;
};
void terminate(const char *message)
{
printf("%\n", message);
exit(1);
}
int get_size(Queue q)
{
return q->size;
}
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; //100으로 설정
return q;
}
void destroy(queue q)
{
free(q->contents);
free(q);
}
void make_empty(Queue q)
{
q->front =0; //free 할 필요없이 사이즈가 0으로 만든다.
q->rear = -1;
q->size = 0;
}
bool is_empty(Queue q)
{
return q->size == 0;
}
bool is_full(Queue q)
{
return q->size == q->capacity;
}
void enqueue(Queue q, Item i)
{
if (is_full(q))
reallocate(q); //인덱스 0을 가리키도록 하면 맨처음으로 삽입이 된다.
q->rear = (q->rear +1)%q->capacity; //1만 증가시키면 배열인덱스 범위가 초과하기 때문에 capacity 를 나눈나머지를 연산한다.
q->contents[q->rear] = i; //ex) rear가 -1일때 +1하면 0이 된다
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->size--;
return result;
}
Item peek(Queue q)
{
if(is_empty(q))
terminate("Error in peek: queue is empty");
return q->contens[q->front];
}









0 comments:

Post a Comment