큐 연결리스트. 배열구현

큐 연결리스트 구현

Front(삭제) 가 오른쪽에 위치하면 삭제를 할때의 이전노드를 매번 알고있어야하므로 불편함.
삽입을 위해선 마지막노드(Rear)의 주소를 알아야 함.

큐 공간에서 front rear size 를 저장해둠

연결리스트를 통한 큐 구현

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int Item;
typedef struct queue_type *Queue;

Queue create();
void destory(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 node {
    Item data;
    struct node *next;
};
struct queue_type{
    struct node*front;
    struct node*rear;
    int size;
};

void terminate(const char* message)
{
    printf("%s\n",message);
    exit(EXIT_FAILURE);
}
int get_size(Queue q)
{
    return q->size;
}
Queue create()
{
    Queue q = malloc(sizeof(struct queue_type));
    if(q==NULL)
        terminate("Error in create: queue could not be created");
    q->front==NULL;
    q->rear=NULL;
    q->size=0;
    return q;
}
void destory(Queue q)
{
    make_empty(q);
    free(q);
}
void make_empty(Queue q)
{
    while(!is_empty(q))
        dequeue(q);
    q->size=0;
}
bool is_empty(Queue q)
{
    return q->front ==NULL;
}
void enqeue(Queue q,Item i)
{
    struct node* new_node=malloc(sizeof(struct node));
    if(new_node==NULL)
        terminate("Error in push: queue is full.");
    new_node->data=i;
    new_node->next=NULL;
    if(q->front==NULL)
    {
        q->front=new_node;
        q->rear=new_node;
    }
    else
    {
        q->rear->next=new_node;     //노드 연결시켜주고
        q->rear=new_node;       //연결시킨 새로운 노드가 rear가 된다.
    }
    q->size++;
}
Item deqeue(Queue q)
{
    struct node* old_front;
    Item i;
    if(is_empty(q))
        terminate("Erro in deqeue");
    old_front=q->front;
    i=old_front->data;
    q->front=old_front->next;
    if(q->front==NULL)
        q->rear=NULL;
    free(old_front);
    q->size--;
    return i;
}
Item peek(Queue q)
{
    if(is_empty(q))
        terminate("Error in peek");
    return q->front->data;  
    )
}

배열통한 큐 구현

서큘러배열 이용

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int Item;
typedef struct queue_type *Queue;

Queue create();
void destory(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);

/* 위의 함수 프로토타입은 큐에서와 동일하다 */
#define INIT_CAPACITY 100

struct queue_type {
    Item* contents;     //배열 (동적할당)
    int front;
    int rear;
    int size;       //저장된 데이터 개수
    int capacity;   // 배열 contents의 크기
};

void terminate(const char* message)
{
    printf("%s\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;
    return q;
}
void destroy(Queue q)
{
    free(q->contents);
    free(q);
}
void make_empty(Queue q)
{
    q->front=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);
    q->rear = (q->rear+1) % q->capacity;    //서큘러배열 처리
    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->size--;
    return result;
}
Item peek(Queue q)
{
    if(is_empty(q))
        terminate("Error in peek: queue is empty.");
    return q->contents[q->front];
}
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;
}

q->rear = (q->rear+1) % q->capacity; //서큘러배열 처리