큐(queue)

1. 배열을 이용한 큐 구현

단순히 스택과 같이 큐를 배열을 이요하여 구현하면 아래와 같다.

문제점은 큐의 크기를 한번 다 사용하고 나면 큐는 실제로는 비어있지만 더이상 데이터를 삽입할 수가없다.

그렇기 때문에 배열을 이요할 때에는 원형 큐를 구현하게된다.

init: 큐 초기화

isEmpty: 큐가 비어있으면 1반환, 데이터가 있으면 0 반환

isFull: 큐가 가득 차있으면 1반환, 빈공간이 있으면 0반환

enqueue: 큐에 데이터 삽입

dequeue: 큐에서 데이터 추출

#include <stdio.h>
 
#define MAX_SIZE 10
 
typedef struct _queue {
    int data[MAX_SIZE];
    int front;
    int rear;
}queue;
 
void init(queue* q)
{
    q->front = 0;
    q->rear = 0;
}
int isEmpty(queue* q)
{
    if (q->front == q->rear)
        return 1;
    else
        return 0;
}
int isFull(queue* q)
{
    if (q->rear == MAX_SIZE)
        return 1;
    else
        return 0;
}
void enqueue(queue* q, int data)
{
    if (isFull(q))
    {
        printf("queue is full\n");
        return;
    }
 
    q->data[q->rear] = data;
    q->rear++;
}
int dequeue(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    
    return q->data[q->front++];
}
int seek(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    return q->data[q->front];
}
int main(void)
{
    queue q;
    init(&q);
    for (int i = 1; i <= 11; i++)
    {
        enqueue(&q, i * 10);
        printf("queue front : %d\n", seek(&q));
    }
    while (!isEmpty(&q))
        printf("dequeue data : %d \n", dequeue(&q));
    printf("queue front : %d\n", seek(&q));
    return 0;
}
 

2. 배열을 이용한 원형 큐 구현

원형 큐의 경우, 배열을 지속적으로 사용할 수 있는 장점이 있다.

배열이 비어있는상태, 꽉차있는 상태를 구분하기 위해, 배열의 크기 - 1 만큼을 큐에서 사용한다.

front==rear인 경우 큐가 비어있는 상태이며, front-1 = rear인 경우 큐가 가득차 있는 상태이다.

isNext: 다음 인덱스를 가져오는 함수이다.

#include <stdio.h>
 
#define MAX_SIZE 10
 
typedef struct _queue {
    int data[MAX_SIZE];
    int front;
    int rear;
}queue;
 
void init(queue* q)
{
    q->front = 0;
    q->rear = 0;
}
int isEmpty(queue* q)
{
    if (q->front == q->rear)
        return 1;
    else
        return 0;
}
int isNext(int pos)
{
    if ( pos == MAX_SIZE-1)//마지막 인덱스면 첫번째로 돌아간다.
        return 0;
    else
        return pos + 1;
}
void enqueue(queue* q, int data)
{
    if (isNext(q->rear)==q->front)
    {
        printf("queue is full\n");
        return;
    }
    q->rear = isNext(q->rear);
    q->data[q->rear] = data;
}
int dequeue(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    q->front = isNext(q->front);
    return q->data[q->front];
}
int seek(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    return q->data[isNext(q->front)];
}
int main(void)
{
    queue q;
    init(&q);
    for (int i = 1; i <= 11; i++)
    {
        enqueue(&q, i * 10);
        printf("queue front : %d\n", seek(&q));
    }
    while (!isEmpty(&q))
        printf("dequeue data : %d \n", dequeue(&q));
    printf("queue front : %d\n", seek(&q));
    return 0;
}
 

위 코드를 실행하면 아래와 같은 값이 나온다.

큐의 크기는 10이지만, 실제로 사용하는 영역은 9칸 이기 때문에, 11개의 데이터를 삽입하려고 시도하면 2번의 에러가 발생한다.

3. 리스트를 이용한 큐 구현

리스트를 사용할 경우, 데이터 삽입을 위해 리스트의 가장 마지막을 노드를 가르키는 포인터(여기서는 Tail)이 필요하다.

큐에서 데이터 삽입시 Tail 위치에 삽입하며, 삭제시 Head가 가르키는 노드를 삭제한다.

#include <stdio.h>
#include <stdlib.h>
 
typedef struct _node {
    int data;
    struct _node* next;
}node;
 
typedef struct _queue {
    node* head;
    node* tail;
}queue;
 
void init(queue* q)
{
    q->head = NULL;
    q->tail = NULL;
}
 
int isEmpty(queue* q)
{
    if (q->head == NULL)
        return 1;
    else
        return 0;
}
 
void enqueue(queue* q, int data)
{
    node* newnode = (node*)malloc(sizeof(node));
 
    newnode->data = data;
    newnode->next = NULL;
    
    if (isEmpty(q))
    {
        q->head = newnode;
        q->tail = newnode;
    }
    else
    {
        q->tail->next = newnode;
        q->tail = newnode;
    }
}
 
int dequeue(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
 
    int ret = q->head->data;
    node* temp = q->head;
 
    q->head = temp->next;
    free(temp);
 
    return ret;
}
 
int seek(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    return q->head->data;
}
 
int main(void)
{
    queue q;
    init(&q);
 
    for (int i = 1; i <= 11; i++)
    {
        enqueue(&q, i * 10);
        printf("queue front : %d\n", seek(&q));
    }
 
    while(!isEmpty(&q))
        printf("dequeue data : %d \n", dequeue(&q));
 
    printf("queue front : %d\n", seek(&q));
 
    return 0;
}