[Data Structure] Chapter 07: 큐(Queue)

FIFO구조를 가지는 자료구조인 queue에 대해 이해하고, 추가적으로 queue와 비슷한 deque을 구현해보자.

 

 

큐

• 큐은 가장 처음에 들어간 데이터가 가장 먼저 나오는 선입선출, FIFO(First-In, First-Out)의 자료구조를 가진다.

 

큐 자료구조의 ADT

void QueueInit(Queue * pq);
- 큐의 초기화를 진행한다.
- 큐 생성 후 제일 먼저 호출되어야 하는 함수이다.

int QIsEmpty(Queue * pq);
- 큐가 빈 경우 TRUE(1)를, 그렇지 않은 경우 FALSE(0)을 반환한다.

void Enqueue(Queue * pq, Data data)
- 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

Data Dequeue(Queue * pq);
- 저장순서가 가장 앞선 데이터를 삭제한다.
- 삭제된 데이터는 반환이 된다.
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Data QPeek(Queue * pq);
- 저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다.
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

 

큐의 배열 기반 구현

 

enqueue

dequeue

 

• Enqueue: R이 새로운 칸을 지정하고, 해당 위치에 새 데이터가 저장된다.
• Dequeue: F가 기존의 다음 위치로 이동하고 기존 칸을 삭제, 후에 해당 데이터를 반환한다.

 

원형 큐(Circular Queue)

• 배열이 텅 빈 경우 -> F와 R이 같은 위치를 가리킨다.
• 배열이 가득 찬 경우와 텅 빈 경우 F와 R의 위치 관계가 같아서 두 경우를 구분하기 어렵기 때문에, 배열의 길이가 N이면 데이터가 N-1개 채워졌을 때를 꽉 찬 경우로 본다.
• 배열이 꽉 찬 경우 -> R이 가리키는 위치의 다음을 F가 가리킨다. 

 

원형 큐가 꽉 찬 경우

 

원형 큐의 구현

 파일명: CircularQueue.h

#ifndef __C_QUEUE_H__
#define __C_QUEUE_H__

#define TRUE        1
#define FALSE       0

#define QUE_LEN     100
typedef int Data;

typedef struct _cQueue
{
    int front;
    int rear;
    Data queArr[QUE_LEN];
} CQueue;

typedef CQueue Queue;

void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);

void Enqueue(Queue * pq, Data data);
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);

#endif

 

 파일명: CircularQueue.c

#include <stdio.h>
#include <stdlib.h>
#include "CircularQueue.h"

void QueueInit(Queue * pq)
{
    pq -> front = 0;
    pq -> rear = 0;
}

int QIsEmpty(Queue * pq)
{
    if(pq->front == pq->rear)
        return TRUE;
    else
        return FALSE;
}

int NextPosIdx(int pos)
{
    if(pos == QUE_LEN-1)
        return 0;
    else
        return pos+1;
}

void Enqueue(Queue * pq, Data data)
{
    if(NextPosIdx(pq->rear) == pq->front)
    {
        printf("Queue Memory Error!");
        exit(-1);
    }

    pq->rear = NextPosIdx(pq->rear);
    pq->queArr[pq->rear] = data;
}

Data Dequeue(Queue * pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }

    pq->front = NextPosIdx(pq->front);
    return pq->queArr[pq->front];
}

Data QPeek(Queue * pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }

    return pq->queArr[NextPosIdx(pq->front)];
}

 

 파일명: CircularQueueMain.c

#include <stdio.h>
#include "CircularQueue.h"

int main(void)
{
    Queue q;
    QueueInit(&q);

    printf("%d %d ",sizeof(q.queArr), sizeof(2));

    for(int i =0; i<9; i++) //queArr의 size는 400이고 int 하나의 사이즈는 4이므로 꽉 채우기 직전인 99개 까지는 채울 수 있음! 
    {
        Enqueue(&q, 1);
        Enqueue(&q, 2);
        Enqueue(&q, 3);
        Enqueue(&q, 4);
        Enqueue(&q, 5);
        Enqueue(&q, 6);
        Enqueue(&q, 7);
        Enqueue(&q, 8);
        Enqueue(&q, 9);
        Enqueue(&q, 0);
        Enqueue(&q, 0);
    }

    while(!QIsEmpty(&q))
        printf("%d ", Dequeue(&q));


    return 0;
}

400 4 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 9 
0 0 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 9 0 0

-> 99개까지는 정상적으로 실행된다. 

 

#include <stdio.h>
#include "CircularQueue.h"

int main(void)
{
    Queue q;
    QueueInit(&q);

    printf("%d %d ",sizeof(q.queArr), sizeof(2));

    for(int i =0; i<10; i++) //queArr의 size는 400이고 int 하나의 사이즈는 4이므로 꽉 채우기 직전인 99개 까지는 채울 수 있음! 
    {
        Enqueue(&q, 1);
        Enqueue(&q, 2);
        Enqueue(&q, 3);
        Enqueue(&q, 4);
        Enqueue(&q, 5);
        Enqueue(&q, 6);
        Enqueue(&q, 7);
        Enqueue(&q, 8);
        Enqueue(&q, 9);
        Enqueue(&q, 0);
    }

    while(!QIsEmpty(&q))
        printf("%d ", Dequeue(&q));


    return 0;
}

400 4 Queue Memory Error!

-> n-1개까지 배열을 채울 수 있으므로, 400개를 넣으면 Memory Error 발생!

 

 

큐의 연결 리스트 기반 구현

 

연결리스트 기반 큐

 

 파일명: ListBaseQueue.h

#ifndef __LB_QUEUE_H__
#define __LB_QUEUE_H__

#define TRUE        1
#define FALSE       0

typedef int Data;

typedef struct _node
{
    Data data;
    struct _node * next;
} Node;

typedef struct _lQueue
{
    Node * front;
    Node * rear;
} LQueue;

typedef LQueue Queue;

void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);

void Enqueue(Queue * pq, Data data);
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);

#endif

 

 파일명: ListBaseQueue.c

#include "ListBaseQueue.h"
#include <stdio.h>
#include <stdlib.h>

void QueueInit(Queue * pq)
{
    pq->front = NULL;
    pq->rear = NULL;
}

int QIsEmpty(Queue * pq)
{
    if(pq->front == NULL)
        return TRUE;
    else
        return FALSE;
}

void Enqueue(Queue * pq, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode->next = NULL;
    newNode->data = data;

    if(QIsEmpty(pq)==TRUE)
    {
        pq->front = newNode;
        pq->rear = newNode;
    }
    else
    {
        pq->rear->next = newNode;
        pq->rear = newNode;
    }
}

Data Dequeue(Queue * pq)
{
    if(QIsEmpty(pq)==TRUE)
    {
        printf("Queue Memory Error!");
        exit(-1);
    }

    Node * rpos = pq->front;
    Data rdata = rpos->data;

    pq->front = pq->front->next;
    free(rpos);

    return rdata;
}

 

 파일명: ListBaseQueueMain.c

#include <stdio.h>
#include "ListBaseQueue.h"

int main(void)
{
    Queue q;
    QueueInit(&q);

    Enqueue(&q, 1); Enqueue(&q, 2);
    Enqueue(&q, 3); Enqueue(&q, 4);
    Enqueue(&q, 5);

    while(!QIsEmpty(&q))
        printf("%d ", Dequeue(&q));

    return 0;
}

1 2 3 4 5

 

 

덱

• 덱(deque)은 double-ended queue을 의미하고, 양방향으로 데이터를 넣고 뺄 수 있다.

 

덱 자료구조의 ADT

void DequeInit(Deque * pdeq);
- 덱의 초기화를 진행한다.
- 덱 생성 후 제일 먼저 호출되어야 하는 함수이다.

int DQIsEmpty(Deque * pdeq);
- 덱이 빈 경우 TRUE(1)를, 그렇지 않은 경우 FALSE(0)을 반환한다.

void DQAddFirst(Deque * pdeq, Data data)
- 덱의 머리에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

void DQAddLast(Deque * pdeq, Data data)
- 덱의 꼬리에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

Data DQRemoveFirst(Queue * pdeq);
- 덱의 머리에 위치한 데이터를 반환 및 소멸한다.

Data DQRemoveLast(Queue * pdeq);
- 덱의 꼬리에 위치한 데이터를 반환 및 소멸한다.

Data DQGetFirst(Queue * pdeq);
- 덱의 머리에 저장된 데이터를 소멸하지 않고 반환한다.

Data DQGetLast(Queue * pdeq);
- 덱의 꼬에 저장된 데이터를 소멸하지 않고 반환한다.

 

덱의 양방향 연결 리스트 기반 구현

• 자료구조는 구현하기 전 항상 그림을 그려서 이해하고 구현하는 것이 편하다!!

 

DQAdd___과 DQRemove___의 구조

 

 파일명: Deque.h

#ifndef __DEQUE_H__
#define __DEQUE_H__

#define TRUE        1
#define FALSE       0

typedef int Data;

typedef struct _node
{
    Data data;
    struct _node * next;
    struct _node * prev;
} Node;

typedef struct _dlDeque
{
    Node * head;
    Node * tail;
} DLDeque;

typedef DLDeque Deque;

void DequeInit(Deque * pdeq);
int DQIsEmpty(Deque * pdeq);

void DQAddFirst(Deque * pdeq, Data data);
void DQAddLast(Deque * pdeq, Data data);

Data DQRemoveFirst(Deque * pdeq);
Data DQRemoveLast(Deque * pdeq);

Data DQGetFirst(Deque * pdeq);
Data DQGetLast(Deque * pdeq);

#endif

 

 파일명: Deque.c

#include "Deque.h"
#include <stdio.h>
#include <stdlib.h>


void DequeInit(Deque * pdeq)
{
    pdeq->head = NULL;
    pdeq->tail = NULL;

}

int DQIsEmpty(Deque * pdeq)
{
    if(pdeq->head == NULL && pdeq->tail == NULL)
        return TRUE;
    else
        return FALSE;
}

void DQAddFirst(Deque * pdeq, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;

    newNode->prev = NULL;

    if(DQIsEmpty(pdeq)==TRUE)
        pdeq->tail = newNode;
    else
        pdeq->head->prev = newNode;
    newNode->next = pdeq->head;

    pdeq->head = newNode;
}

void DQAddLast(Deque * pdeq, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;

    newNode->next = NULL;

    if(DQIsEmpty(pdeq)==TRUE)
        pdeq->head = newNode;
    else
        pdeq->tail->next = newNode;
    newNode->prev = pdeq->tail;

    pdeq->tail = newNode;
}


Data DQRemoveFirst(Deque * pdeq)
{
    Node * rpos = pdeq->head;
    Data rdata = rpos->data;

    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error!");
        exit(-1);
    }

    pdeq->head = pdeq->head->next;
    free(rpos);

    if(pdeq->head == NULL)
        pdeq->tail = NULL;
    else
        pdeq->head->prev = NULL;

    return rdata;
}

Data DQRemoveLast(Deque * pdeq)
{
    Node * rpos = pdeq->tail;
    Data rdata = rpos->data;

    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error!");
        exit(-1);
    }

    pdeq->tail = pdeq->tail->prev;
    free(rpos);

    if(pdeq->tail == NULL)
        pdeq->head = NULL;
    else
        pdeq->tail->next = NULL;

    return rdata;
}

Data DQGetFirst(Deque * pdeq)
{
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error!");
        exit(-1);
    }

    return pdeq->head->data;
}

Data DQGetLast(Deque * pdeq)
{
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error!");
        exit(-1);
    }

    return pdeq->tail->data;
}

 

 파일명: DequeMain.c

#include <stdio.h>
#include "Deque.h"

int main(void)
{
    Deque deq;
    DequeInit(&deq);

    DQAddFirst(&deq, 3);
    DQAddFirst(&deq, 2);
    DQAddFirst(&deq, 1);

    DQAddLast(&deq, 4);
    DQAddLast(&deq, 5);
    DQAddLast(&deq, 6);

    while(!DQIsEmpty(&deq))
        printf("%d ", DQRemoveFirst(&deq));
    
    printf("\n");

    DQAddFirst(&deq, 3);
    DQAddFirst(&deq, 2);
    DQAddFirst(&deq, 1);

    DQAddLast(&deq, 4);
    DQAddLast(&deq, 5);
    DQAddLast(&deq, 6);

    while(!DQIsEmpty(&deq))
        printf("%d ", DQRemoveLast(&deq));

    return 0;
}

1 2 3 4 5 6 
6 5 4 3 2 1

 

문제 07-1

덱을 기반으로 큐 구현

• Deque.h와 Deque.c를 디렉토리에 포함한 상태로 이를 활용해 큐를 구현

 파일명: DequeBaseQueue.c

#ifndef __DQ_BASE_QUEUE_H__
#define __DQ_BASE_QUEUE_H__

#include "Deque.h"

typedef Deque Queue;

void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);

void Enqueue(Queue * pq, Data data);
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);

#endif

 

 파일명: DequeBaseQueue.h

#include "DequeBaseQueue.h"

void QueueInit(Queue * pq)
{
    DequeInit(pq);
}

int QIsEmpty(Queue * pq)
{
    return DQIsEmpty(pq);
}

void Enqueue(Queue * pq, Data data)
{
    DQAddLast(pq, data);
}

Data Dequeue(Queue * pq)
{
    return DQRemoveFirst(pq);
}

Data QPeek(Queue * pq)
{
    return DQGetFirst(pq);
}

 

 파일명: DequeBaseQueueMain.c

#include <stdio.h>
#include "DequeBaseQueue.h"

int main(void)
{
    Queue q;
    QueueInit(&q);

    Enqueue(&q, 1);
    Enqueue(&q, 2);
    Enqueue(&q, 3);
    Enqueue(&q, 4);
    Enqueue(&q, 5);

    while(!QIsEmpty(&q))
        printf("%d ", Dequeue(&q));

    return 0;
}

1 2 3 4 5

 

---

참고자료

• 윤성우, <윤성우의 열혈 자료구조>, 오렌지미디어, 2022.04.11