🚝 Queue

자료 구조 중에서 데이터와 링크로 구성된 연결 리스트(Linked List)라는 것이 있다. 이 연결리스트를 어떻게 활용하여 만드느냐에 따라서 여러 자료 구조를 만들 수 있다. 이번엔 그 중에서 Queue에 대해서 얘기하겠다.

Queue(큐)

• 리스트형 데이터 구조 중에서 한 쪽에서만 데이터를 추가하고 다른 한 쪽에서만 삭제할 수 있는 FIFO(First In First Out; 선입선출)식 데이터 구조이다.
• 단어의 본래 사전적 의미처럼 줄을 서는 모양과 같다. 먼저 들어온 데이터가 먼저 나가는 형식이다.
• 삽입이 일어나는 쪽은 rear, 삭제가 일어나는 쪽을 front라고 한다.
• 큐의 연산
  • insert, enqueue, offer, push : rear에 새로운 아이템을 추가
  • remove, poll, pop : front에 있는 아이템을 삭제하고 반환
  • peek, front : front에 있는 원소를 제거하지 않고 반환
  • is_empty : 큐가 비어있으면 true(1)을 리턴
• 큐의 구현
  • 배열을 활용한 선형 큐
  • 배열을 활용한 선형 큐
  • 링크드 리스트를 활용한 큐
• 큐의 종류
  • 선형 큐(Linear Queue)
  • 원형 큐(Circular Queue)
  • 데큐(Dequeue)
  • 우선 순위 큐(Priority Queue) → 나중에 따로 다룸

선형 큐(Linear Queue / 일반 큐)

• 미리 지정해둔 QUEUE_MAX_SIZE크기의 배열에 값을 넣는 형태의 큐이다.
• push하면 rear가 뒤로 밀리고 pop하면 front가 뒤로 밀린다.
• 점점 갈수록 rear와 front가 뒤로 밀리기 때문에 점점 사용할 수 있는 큐의 크기가 작아진다.
• front가 QUEUE_MAX_SIZE를 넘기면 큐 오버플로우(Queue Overflow)가 일어난다.
• Linear Queue 구현

# define QUEUE_MAX 10

static size_t   front = 0;
static size_t   rear = 0;

• pop 구현

int     pop(int queue[])
{
    queue[front] = 0;
    front++;
}

• push 구현

void    push(int queue[], int item)
{
    queue[rear] = item;
    rear++;
}

• seek 구현

int     seek(int queue[])
{
    return (queue[front]);
}

• is_empty 구현

int     is_empty(int queue[])
{
    return (front == rear);
}

원형 큐(Circular Queue / 순환 큐)

• 미리 지정해둔 QUEUE_MAX_SIZE크기의 배열에 값을 넣는 형태의 큐이다.
• 선형 큐와 같이 push와 pop에 의해서 rear 와 front가 뒤로 밀린다.
• 하지만 rear나 front가 QUEUE_MAX_SIZE 값일 때, push나 pop을 하면 0이 돼서 순환한다.
• 그렇기 때문에 항상 최대 QUEUE_MAX_SIZE 만큼의 아이템을 가질 수 있다.
• 선형 큐와는 다르게 rear의 위치는 마지막 원소의 뒤 인덱스이다.
  → 그렇게 구현하지 않으면 full과 empty를 구분하기 힘듬
• Circular Queue 구현

# define QUEUE_MAX 10

static size_t   front = 0;
static size_t   rear = 0;

• pop 구현

int     pop(int queue[])
{
    int val;
    if (is_empty(queue))
        return (0);
    val = queue[front];
    front = (front + 1) % QUEUE_MAX;
    return (val);
}

• push 구현

void    push(int queue[], int item)
{
    if (is_full(queue))
        return ;
    queue[rear] = item;
    rear = (rear + 1) % QUEUE_MAX;
}

• seek 구현

int     seek(int queue[])
{
    return (queue[front]);
}

• is_empty 구현

int     is_empty(int queue[])
{
    return (front == rear);
}

• is_full 구현

int     is_full(int queue[])
{
    if (front <= rear)
        return (front == 0 && rear == QUEUE_MAX);
    return (front == rear + 1);
}

연결 리스트로 구현한 큐

• 미리 정해두지 않고 동적으로 필요할 때 값을 추가하여 사용한다.
• 그렇기 때문에 메모리 내에서 사용한다면 크기의 제약이 거의 없다.
• 만들려면 연결 리스트로도 원형큐를 만들 수 있겠지만 굳이 사이즈 제약을 두면 만들 이유는 없는거 같다.
• Linked Queue 구현

typedef struct s_linked_queue
{
	int data;
	struct s_linked_queue *next;
} t_linked_queue;

• pop 구현

int     pop(t_linked_queue *queue)
{
    t_linked_queue  *node;
    int             ret_val;

    if (!queue || !queue->next)
        return ;
    node = queue->next;
    ret_val = node->data;
    queue->next = node->next;
    free(node);
    return (ret_val);
}

• push 구현

void    push(t_linked_queue *queue, int item)
{
    t_linked_queue *node;
    t_linked_queue *new;

    if (!queue)
        return ;
    if ((new = (t_linked_queue *)malloc(sizeof(t_linked_queue))) == 0)
        return ;
    node = queue;
    while (node->next)
        node = node->next;
    new->data = item;
    new->next = NULL;
    node->next = new;
}

• peek 구현

int     peek(t_linked_queue *queue)
{
    return (queue->next->data);
}

• is_empty 구현

int     is_empty(t_linked_queue *queue)
{
    if (!queue)
        return (1);
    return (!queue->next);
}

덱(Dequeue; Double-Ended Queue / 데큐)

• 끝이 두 개인 큐라서 double-ended queue이다.
• front, rear에서 push, pop 모두 가능하다.
• stack과 queue의 특징을 모두 가지고 있다.
• 노드가 데이터(data), 이전 노드(prev), 다음 노드(next)로 이루어진다.
• 스크롤 (Scroll) : 입력이 한 쪽 끝으로만 가능하도록 제한한 덱
• 셸프 (Shelf) : 출력이 한 쪽으로만 가능하도록 제한한 덱
• Dequeue 구현

typedef struct      s_node
{
    int             data;
    struct s_node   *next;
    struct s_node   *prev;
}                   t_node;

typedef struct      s_dequeue
{
    t_node          *head;
    t_node          *tail;
}                   t_dequeue;

• init_dequeue 구현

t_dequeue               *init_dequeue(void)
{
    t_dequeue   *dequeue;

    if ((dequeue = (t_dequeue *)malloc(sizeof(t_dequeue))) == 0)
        return (NULL);
    dequeue->head = NULL;
    dequeue->tail = NULL;
    return (dequeue);
}

• pop_back 구현

int                     pop_back(t_dequeue *dequeue)
{
    t_node  *node;
    t_node  *tmp;
    int     ret_val;

    if (!dequeue)
        return (0);
    node = dequeue->tail;
    ret_val = node->data;
    if (dequeue_size(dequeue) == 1)
    {
        free(node);
        dequeue->head = NULL;
        dequeue->tail = NULL;
    }
    else
    {
        tmp = node->prev;
        node->prev->next = NULL;
        free(node);
        dequeue->tail = tmp;
    }
    return (ret_val);
}

• push_back 구현

void                    push_back(t_dequeue *dequeue, int item)
{
    t_node  *new_node;

    if (!dequeue)
        return ;
    if ((new_node = (t_node *)malloc(sizeof(t_node))) == 0)
        return ;
    new_node->data = item;
    new_node->prev = dequeue->tail;
    new_node->next = NULL;
    if (is_empty(dequeue))
        dequeue->head = new_node;
    else
        dequeue->tail->next = new_node;
    dequeue->tail = new_node;
}

• pop_front 구현

int                     pop_front(t_dequeue *dequeue)
{
    t_node  *node;
    t_node  *tmp;
    int     ret_val;

    if (!dequeue)
        return (0);
    node = dequeue->head;
    ret_val = node->data;
    if (dequeue_size(dequeue) == 1)
    {
        free(node);
        dequeue->head = NULL;
        dequeue->tail = NULL;
    }
    else
    {
        tmp = node->next;
        tmp->prev = NULL;
        free(node);
        dequeue->head = tmp;
    }
    return (ret_val);
}

• push_front

void                    push_front(t_dequeue *dequeue, int item)
{
    t_node  *new_node;

    if (!dequeue)
        return ;
    if ((new_node = (t_node *)malloc(sizeof(t_node))) == 0)
        return ;
    new_node->data = item;
    new_node->prev = NULL;
    new_node->next = dequeue->head;
    if (is_empty(dequeue))
        dequeue->tail = new_node;
    else
        dequeue->head->prev = new_node;
    dequeue->head = new_node;
}

• is_empty 구현

int                     is_empty(t_dequeue *dequeue)
{
    return (dequeue->head == NULL);
}

• dequeue_size 구현

size_t                  dequeue_size(t_dequeue *dequeue)
{
    size_t  cnt;
    t_node  *node;

    if (!dequeue)
        return (0);
    if (is_empty(dequeue))
        return (0);
    cnt = 1;
    node = dequeue->head;
    while (node->next)
    {
        node = node->next;
        cnt++;
    }
    return (cnt);
}

Reference

• https://velog.io/@pa324/자료구조-Queue큐-udjxr0hb3x
• https://jeong-pro.tistory.com/97