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