Chapter 07. 큐(Queue)

김민정·2024년 10월 30일

윤성우 열혈 자료구조

목록 보기

7/14

07-1. 큐의 이해와 ADT 정의

큐는 스택과 함께 언급되고 비교되는 자료구조다.
스택은 먼저 들어간 데이터가 나중에 나오는데에 반해
큐는 먼저 들어간 데이터가 먼저 나오기 때문이다.
이것이 큐와 스택의 유일한 차이점이다...!
그렇다면 연결 리스트 기반으로 큐를 구현할 때 tail이 아닌 head에 새 데이터를 추가하면 될까...?
배우면서 맞는지 살펴보자!

큐(Queue)의 이해

큐(Queue)는 선입선출(先入先出)구조의 자료구조다. FIFO(First-In, First-Out) 구조의 자료구조라고도 한다.
일상생활 속에서 줄서기와 터널, 호스 등 다양하게 큐란 자료구조의 모습을 볼 수 있다.

큐(Queue) ADT 정의

스택과 마찬가지로 큐의 ADT도 정형화된 편이다.
그 중 핵심이 되는 두 가지 연산은 다음과 같다.

enqueue : 큐에 데이터를 넣는 연산 (스택의 Push와 비슷)
dequeue : 큐에 데이터를 꺼내는 연산 (스택의 Pop과 비슷)

따라서 이 연산에 대한 ADT는 다음과 같다.

✅Operations:

void QueueInit(Queue * pq);
- 큐의 초기화를 진행
- 큐 생성 후 제일 먼저 호출되는 함수
int QIsEmpty(Queue * pq);
- 큐가 빈 경우 TRUE(1), 그렇지 않은 경우 FALSE(0)을 반환
void Enqueue(Queue * pq, Data data);
- 큐에 데이터를 저장. 매개변수 data로 전달된 값 저장
Data Dequeue(Queue * pq);
- 저장순서가 가장 앞선 데이터 삭제
- 삭제된 데이터는 반환
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재 필수. (QIsEmpty 함수 활용)
Data QPeek(Queue * pq);
- 저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않음.
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재 필수. (QIsEmpty 함수 활용)

ADT를 정의했으니 이제 큐를 구현해보려 하는데 큐도 스택과 동일하게 배열 기반, 연결 리스트 기반으로 구현할 수 있다.

07-2. 큐의 배열 기반 구현

큐의 구현에 대한 논리

큐와 스택에 대한 차이가 데이터가 앞에서 꺼내지는지 뒤에서 꺼내지는지 밖에 없으니 구현해 놓은 스택을 대상으로 꺼내는 방법만 조금만 바꾸면 큐를 구현할 수 있지 않을까? 생각할 수도 있다.
하지만 큐의 구현 모델을 생각해보면 생각보다 차이가 크다고 느껴질 것이다.
예를 들어 enqueue 연산을 생각해보면 아래 그림과 같이 F는 Front의 약자로 큐의 머리를, R은 Rear의 약자로 큐의 꼬리를 가리킨다고 해보자.

enqueue 연산시 R이 다음칸으로 가고 그 자리에 새로운 데이터가 저장된다.
하지만 dequeue 연산을 생각해보면 어떨까?

F가 가리키는 데이터를 대상으로 데이터가 반환되고 사라진다.
즉, F를 참조하여 dequeue 연산을 하고, R을 참조하여 enqueue 연산을 한다.
(뒤로 데이터를 넣고 앞으로 데이터를 빼는 구조)

만약 dequeue 연산을 할 때 단순히 데이터를 반환하는데 그치지 않고 배열에 데이터들을 앞쪽으로 계속해서 땡겨 채우게 되면 어떻게 될까?
이 방법을 적용하면 dequeue 연산의 대상이 맨 앞부분에 위치하므로 F가 필요없어진다.
단, 이 방식은 dequeue 연산 시마다 저장된 데이터를 한 칸씩 이동시켜야 하는 단점이 있다.
배열 기반의 큐에서는 위의 방식으로 dequeue 연산을 진행하지 않는다.

그래서 이전에 보여준 그림과 같은 방식을 사용하지만 이때도 약간의 문제가 있다.

배열의 맨 끝까지 데이터가 저장될 경우 R을 더이상 오른쪽으로 이동시킬 수 없다.
이럴 경우 enqueue 연산을 어떻게 할까?
R을 다시 배열의 시작으로 옮기는 것이다. 쉽게 생각해서 R을 회전시키는 것이다.
이런 방식으로 동작하는 배열 기반의 큐를 가리켜 '원형 큐(Circular queue)'라 한다.

원형 큐(Circular Queue)

위에서 설명한 배열 기반의 큐를 원형큐로 나타내면 바로 위 그림과 같다.
위 그림과 같은 다음 그림과 같은 과정을 거치면서 완성된 모습니다.

그리고 위 그림에서 dequeue 연산 2회를 진행하면 다음과 같아진다.

이제 이 모습들을 구현하면 되는데...
그 전에 먼저 그림 07-6 상황에서 enqueue 연산을 진행해 데이터가 큐에 다 채워진 모습을,

그림 07-7 상황에서 dequeue 연산을 진행해 데이터가 큐에 하나도 없는 모습을 생각해보자.

위 두 상황 모두 F가 R보다 한칸 앞 서 있다는 것을 알 수 있다.
이걸로 우리는 큐가 꽉 찬 상황과 큐가 텅 빈 상황을 구분할 수 없다는 것을 알 수 있다.
이를 해결하기 위해서 배열의 길이가 N이라면 N-1개 채워졌을 때 이를 꽉찬 것으로 간주한다.

그럼 텅 빈 상황에서 큐의 상황은 아래와 같고,

일련의 과정을 거쳐서 데이터가 다 찬 상황에서 큐의 상황은 아래와 같다.

enqueue 연산시 R이 가리키는 위치를 한 칸 이동시킨 다음에 R이 가리키는 위치에 데이터를 저장한다.
dequeue 연산시에는 F가 가리키는 위치를 한 칸 이동시키고 F가 가리키는 위치에 저장된 데이터를 반환 및 소멸한다.

그리고 원형 큐가 텅 빈 상태에는 F와 R이 동일한 위치를 가리키고,
원형 큐가 꽉 찬 상태에는 R이 가리키는 앞을 F가 가리키고 있다.

우리는 이러한 특성들을 코드 구현할 때 명심하고 옮겨야한다.

원형 큐의 구현

배열 기반의 큐라 하면 대부분의 경우 원형 큐를 의미한다고 생각해도 된다.
따라서 배열 기반의 큐를 대표하는 원형 큐를 구현해보도록 하자.

1) 헤더파일(CircularQueue.h)

우선 정의한 큐의 ADT를 바탕으로 헤더파일을 정의하자.
큐를 나타내는 구조체를 CQueue라고 하며 그 안에는 front와 rear라는 변수가 있다.

#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);
int Dequeue(Queue * pq);
int QPeek(Queue * pq);

#endif

2) 소스파일(CircularQueue.c)

앞서 헤더파일에서 선언된 함수들을 정의할 차례다.
그 전에 원형 큐의 핵심이 되는 함수를 하나 먼저 알고가자.

int NextPosIdx(int pos)	// 큐의 다음 위치에 해당하는 인덱스 값 반환 함수
{
	if(pos == QUE_LEN-1)
    	return 0;
    else
    	return pos+1;
}

이 함수는 1을 전달하면 2를 반환하고, pos를 전달하면 pos+1을 반환한다.
큐의 길이보다 하나 작은 값이 인자로 전달되면 0을 반환해 F와 R의 회전을 할 수 있게 도와준다.

이제 함수들을 정의해보자.

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

void QueueInit(Queue * pq)
{   
    // 큐의 첫 시작은 front와 rear 모두 동일한 위치(0)를 가리킴
    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, int data)
{
    if(NextPosIdx(pq->rear) == pq->front)   // 큐가 다 찬 경우
    {
        printf("Queue Memory Error!");
        exit(-1);
    }

    pq->rear = NextPosIdx(pq->rear);    // rear을 한 칸 이동
    pq->queArr[pq->rear] = data;        // rear이 가리키는 곳에 데이터 저장
}

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

    pq->front = NextPosIdx(pq->front);    // front를 한 칸 이동
    return pq->queArr[pq->front];        // front가 가리키는 데이터 반환
}

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

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

3) 실행파일(CircularQueueMain.c)

구현한 원형 큐의 enqueue 연산과 dequeue 연산을 실행파일을 통해 살펴보자.

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

int main()
{
    // Queue의 생성 및 초기화
    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;
}

> gcc .\CircularQueue.c .\CircularQueueMain.c
> .\a.exe
> 출력
1 2 3 4 5

07-3. 큐의 연결 리스트 기반 구현

연결 리스트로 큐를 구현할 경우 배열 기반으로 원형 큐를 구현했던 것에 비해 신경쓸 부분이 좀 줄어든다.

1) 헤더파일 정의(ListBaseQueue.h)

스택과 큐의 유일한 차이점은 데이터를 앞에서 꺼내느냐 뒤에서 꺼내느냐의 차이기 때문에 구현해 놓은 스택을 대상으로 꺼내는 방법만 조금만 변경하면 큐가 될 것 같다!라는 생각이
연결 리스트 기반으로 큐를 구현할 때는 어느정도 맞다!
단, 구현할 때 스택은 push와 pop이 이뤄지는 위치가 동일했지만, 큐는 enqueue와 dequeue가 이뤄지는 위치가 다르다는 점에 유의하면 된다.

따라서 헤더파일을 작성하면 다음과 같다.

#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

2) 소스파일 정의(ListBaseQueue.c)

우선 연결 리스트 기반의 큐에 대해 이해해보자.
큐가 생성되고 처음 초기화된 모습은 아래와 같이 F(front)와 R(rear)이 가리킬 대상이 없어 NULL을 가리킨다.

따라서 함수 QueueInit은 다음과 같이 정의된다.

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

그리고 큐가 비었는지 확인하는 함수인 QIsEmpty는 dequeue 연산이 F를 참조하여 이뤄지기 때문에 F가 NULL인지 확인하면 된다.
따라서 QIsEmpty 함수는 다음과 같다.

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

Enqueue 함수는 노드를 추가하는 과정으로 노드의 추가 유형이 두개로 나뉜다.
첫 번째는, 첫 노드가 추가 될 때로 F와 R 모두 첫 노드를 가리키도록 설정해야한다.
두 번째 이후 노드는 R만 새 노드를 가리키게 하고 노드간의 연결을 위해 가장 끝에 있는 노드가 새 노드를 가리키게 해야한다.

첫 번째 노드 추가	두 번째 이후 노드 추가

F와 R 모두 new node 가리킴	R만 새 노드 가리키게

따라서 함수 Enqueue를 구현하면 다음과 같다.

void Enqueue(Queue * pq, Data data)
{
	Node * newNode = (Node *)malloc(sizeof(Node));
    newNode->next = NULL;
    newNode->data = data;
    
    if(QIsEmpty(pq))	// 첫 번째 노드 추가
    {
    	pq->front = newNode;
        pq->rear = newNode;
    }
    else				// 두 번째 이후 노드 추가
    {
    	pq->rear->next = newNode;	// 마지막 노드가 새 노드 가리킬 수 있도록
        pq->rear = newNode;			// rear도 새 노드 가리킬 수 있도록
    }
}

Dequeue 함수는 Enqueue 함수에 비해 고려할 것이 작다. F만 고려하면 되기 때문이다!

위 그림에서 볼 수 있듯이 1) F가 다음 노드를 가리키게 하고 2) F가 이전에 가리키던 노드를 삭제하면 된다.

노드 하나만 남았을 경우에도 동일하게 1) F가 NULL을 가리키고 2) F가 이전에 가리키던 노드를 삭제하면 된다.
그럼 R은 노드가 삭제되었기 때문에 무엇을 가리키게 될까? 이는 상관이 없다.
큐가 비었는지 확인할 때 큐의 F가 NULL을 가리키는지 고려해서 TRUE, FALSE를 결정했기 때문이다.
따라서 함수 Dequeue를 정의하면 다음과 같다.

Data Dequeue(Queue * pq)
{
	Node * delNode;
    Data retData;
    
    if(QIsEmpty(pq))
    {
    	printf("Queue Memory Error!")
        exit(-1);
    }
    
    delNode = pq->front;			// 삭제할 노드의 주소 값 저장
    retdata = delNode->data;		// 삭제할 노드가 지닌 값 저장
    pq->front = pq->front->next;	// 삭제할 노드의 다음 노드를 front가 가리킴
    
    free(delNode);
    return retData;
}

QPeek 함수는 Dequeue 함수에서 삭제하는 부분을 빼고 정의하면 된다.

위에서 설명한 모든 함수를 정리한 소스파일은 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#include "ListBaseQueue.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))
    {
        pq->front = newNode;
        pq->rear = newNode;
    }
    else
    {
        pq->rear->next = newNode;
        pq->rear = newNode;
    }
}

Data Dequeue(Queue * pq)
{
    Node * delNode;
    Data retData;

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

    delNode = pq->front;
    retData = delNode->data;
    pq->front = pq->front->next;

    free(delNode);
    return retData;
}

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

    return pq->front->data;
}

3) 실행파일 정의(ListBaseQueueMain.c)

구현한 큐를 테스트하기 위한 실행파일내 main 함수를 작성해보자.
원형 큐를 테스트할 때 정의한 main 함수와 동일하고
#include 문을 통해 포함하는 헤더파일 이름만 변경되었다.

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

int main()
{
    // Queue의 생성 및 초기화
    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;
}

> gcc .\ListBaseQueue.c .\ListBaseQueueMain.c
> .\a.exe
> 출력
1 2 3 4 5

07-4. 큐의 활용

큐는 운영체제 및 네트워크와 관련된 소프트웨어의 구현에 있어서 중요한 역할을 담당하는 자료구조다.
'큐잉 이론(queuing theory)'이라는 학문에서 수학적으로 모델링 된 결과의 확인을 위해서 특정 현상을 '시뮬레이션(simulation)'하게 되는데 이때에도 큐는 중요한 역할을 담당한다.
따라서 시뮬레이션이라는 주제를 통해 큐가 활용되는 형태에 대해 배워보자.

시뮬레이션(Simulation)

시뮬레이션이란, 특정 상황에 놓인 복잡한 문제의 해결을 위해서 실제와 비슷한 상황을 연출하는 것을 말한다.

예를 들어 햄버거 가게가 있는데 점심시간 1시간 동안에 고객이 15초당 1명씩 주문을 한다고 가정해보자.
햄버거 종류는 3가지로 치즈버거, 불고기버거, 더블버거가 있다.
각 햄버거별 만드는데 걸리는 시간은 치즈버거 12초, 불고기버거 15초, 더블버거 24초다.
이때 주문한 음식이 포장되어 나오기를 기다리는 고객들을 위한 대기실을 만들 때 필요한 수용 인원 사이즈를 결정하기 위해 시뮬레이션을 해보는 것이다.
그래서 대략 다음과 같은 결과를 얻을 수 있다.

수용인원이 30명인 공간 : 안정적으로 고객 수용할 확률 50%
수용인원이 50명인 공간 : 안정적으로 고객 수용할 확률 70%
수용인원이 100명인 공간 : 안정적으로 고객 수용할 확률 90%
수용인원이 200명인 공간 : 안정적으로 고객 수용할 확률 100%

여기서 확률은 10번의 시뮬레이션을 진행하면 5번의 시뮬레이션에서만 고객을 전부 수용할 수 있었다는 의미다.

시뮬레이션 예제의 작성

위와 같이 다양한 상황에서 시뮬레이션을 이용할 수 있는데
이러한 시뮬레이션에 큐가 도구가 될 수 있다는 점을 이해하기 위해서 위 시뮬레이션에 몇 가지 조건으로 상황을 정리해보자.

점심시간 1시간, 고객은 15초에 1명씩 주문
한 명의 고객은 하나의 버거만 주문
주문하는 메뉴의 가중치는 X, 모든 고객은 무작위로 메뉴 선정
햄버거 만드는 사람은 1명, 한번에 하나의 버거만을 만듦
주문한 메뉴를 받을 다음 고객은 대기실에서 나와서 대기

3번 조건을 위해 int rand(void)라는 함수를 사용해 무작위로 메뉴를 선정할 수 있게 할 것이다.
원형 큐 구현한 헤더파일과 소스파일을 사용해서 큐의 이용을 볼 것이다.
이 시뮬레이션을 코드로 구현하면 다음과 같다.

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

#define CUS_COME_TERM   15  // 고객의 주문 간격(초)

#define CHE_BUR     0   // 치즈버거 상수
#define BUL_BUR     1   // 불고기버거 상수
#define DUB_BUR     2   // 더블버거 상수

#define CHE_TERM    12  // 치즈버거 제작 시간(초)
#define BUL_TERM    15  // 불고기버거 제작 시간(초)
#define DUB_TERM    24  // 더블버거 제작 시간(초)

int main()
{
    int makeProc = 0;   // 햄버거 제작 진행상황
    int cheOrder = 0, bulOrder = 0, dubOrder = 0; // 각 버거 주문량
    int sec;

    // 큐 생성 및 초기화
    Queue que;
    QueueInit(&que);
    srand(time(NULL));

    // for문의 1회 = 1초의 시간
    for(sec=0; sec<3600; sec++)
    {
        if(sec % CUS_COME_TERM == 0)
        {
            switch(rand() % 3)
            {
            case CHE_BUR:
                Enqueue(&que, CHE_TERM);
                cheOrder++;
                break;
            
            case BUL_BUR:
                Enqueue(&que, BUL_TERM);
                bulOrder++;
                break;
            
            case DUB_BUR:
                Enqueue(&que, DUB_TERM);
                dubOrder++;
                break;
            }
        }

        if(makeProc<=0 && !QIsEmpty(&que))
            makeProc = Dequeue(&que);

        makeProc--;
    }

    printf("Simulation Report! \n");
    printf(" - Cheese burger: %d \n", cheOrder);
    printf(" - Bulgogi burger: %d \n", bulOrder);
    printf(" - Double burger: %d \n", dubOrder);
    printf("# Waiting room size: %d \n", QUE_LEN);
    return 0;
}

> gcc .\CircularQueue.c .\HamburgerSim.c
> .\a.exe
> 출력 1 (수용인원 100명)
Simulation Report!
 - Cheese burger: 75
 - Bulgogi burger: 93
 - Double burger: 72
??Waiting room size: 100

> 출력 2 (수용인원 200명)
Simulation Report! 
 - Cheese burger: 89 
 - Bulgogi burger: 64
 - Double burger: 87
# Waiting room size: 200

> 출력 3 (수용인원 30명)
Queue Memory Error!

주석을 보고도 충분히 이해할 수 있겠지만 한번 더 간략하게 정리하면 다음과 같다.

헤더파일 "CircularQueue.h"를 포함한 것을 통해 원형 큐를 이용해 시뮬레이션을 진행한 것을 알 수 있다.
헤더파일 내 #define QUE_LEN 50는 수용인원을 의미한다.
for문의 조건을 보면 1시간(3600초)를 기준으로 1초에 1회 반복되는 것을 알 수 있고 if(sec % CUS_COME_TERM == 0) 문을 통해 15초에 한번씩 주문이 들어오는 것을 알 수 있다.
if(makeProc<=0 && !QIsEmpty(&que))을 통해 주문을 받은 고객은 대기실 밖으로 나갈 수 있게 해준다.

07-5. 덱(Deque)의 이해와 구현

덱의 이해와 ADT 정의

덱(Deque)이란 앞으로도 뒤로도 데이터를 넣을 수 있고, 앞으로도 뒤로도 데이터를 뺄 수 있는 자료구조다.
deque가 double-ended queue를 줄여서 표현한 것으로 양방향으로 넣고 뺄 수 있다는 것을 의미한다.
스택과 큐를 조합한 형태로도 이해할 수 있다.
따라서 덱의 ADT를 구성하는 핵심 함수 네 가지의 기능은 다음과 같다.

앞으로 넣기(AddFirst)
뒤로 넣기(AddLast)
앞에서 빼기(RemoveFirst)
뒤에서 빼기(RemoveLast)

이를 정리하면 다음과 같다.

✅Operations:

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(Deque * pdeq);
- 덱의 머리에 위치한 데이터를 반환 및 소멸.
Data DQRemoveLast(Deque * pdeq);
- 덱의 꼬리에 위치한 데이터를 반환 및 소멸.
Data DQGetFirst(Deque * pdeq);
- 덱의 머리에 위치한 데이터를 소멸하지 않고 반환.
Data DQGetLast(Deque * pdeq);
- 덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환.

덱의 구현

덱도 스택이나 큐와 같이 배열 기반으로, 연결 리스트 기반으로 구현할 수 있다.
덱은 양방향 연결 리스트와 비슷하므로 양방향 연결 리스트 기반으로 구현할 것이다.
예를 들어 덱의 꼬리에 위치한 데이터를 삭제하는 함수 DQRemoveLast의 경우 양방향 리스트로 구현하지 않은 경우 굉장히 까다롭다.

따라서 양방향 연결 리스트 기반의 덱 구현을 위해 첫 번째로 헤더파일을 정의해보자.

// 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

양방향 연결 리스트 기반으로 덱을 구현하긴 하지만 완전히 동일한 구조를 갖지 않는다.
이전에 양방향 연결 리스트를 구현할 때 tail이 없는 구조로 구현했었다. (양방향 연결 리스트 구현 📚)

이번에는 tail을 넣어 덱을 구현할 것이다.

이를 바탕으로 소스파일과 실행파일도 정의해보자.

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

// 덱의 초기화
void DequeInit(Deque * pdeq)
{
    pdeq->head = NULL;
    pdeq->tail = NULL;
}

// 덱의 차고 빔 확인
int DQIsEmpty(Deque * pdeq)
{
    if(pdeq->head == NULL)
        return TRUE;
    else
        return FALSE;
}

// 덱에 데이터 추가
void DQAddFirst(Deque * pdeq, Data data)    // 머리
{
    Node * newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = pdeq->head;

    if(DQIsEmpty(pdeq))
        pdeq->tail = newNode;
    else
        pdeq->head->prev = newNode;
    
    newNode->prev = NULL;
    pdeq->head = newNode;
}
void DQAddLast(Deque * pdeq, Data data)     // 꼬리
{
    Node * newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = pdeq->tail;

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

// 덱에 데이터 제거 및 반환
Data DQRemoveFirst(Deque * pdeq)    // 머리
{
    Node * rnode = pdeq->head;
    Data rdata;
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error!\n");
        exit(-1);
    }
    rdata = pdeq->head->data;

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

    if(pdeq->head == NULL)
        pdeq->tail = NULL;
    else  
        pdeq->head->prev = NULL;
    
    return rdata;
}
Data DQRemoveLast(Deque * pdeq)     // 꼬리
{
    Node * rnode = pdeq->tail;
    Data rdata;
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error!\n");
        exit(-1);
    }
    rdata = pdeq->tail->data;

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

    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!\n");
        exit(-1);
    }
    return pdeq->head->data;
}
Data DQGetLast(Deque * pdeq)    // 꼬리
{
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error!\n");
        exit(-1);
    }
    return pdeq->tail->data;
}

//DequeMain.c
#include <stdio.h>
#include "Deque.h"

int main()
{
    // Deque 생성 및 초기화
    Deque deq;
    DequeInit(&deq);

    // 데이터 넣기 1차
    DQAddFirst(&deq, 3);
    DQAddFirst(&deq, 2);
    DQAddFirst(&deq, 1);

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

    printf("<First Insert & delete in deque>\n");
    // 데이터 꺼내기 1차
    while(!DQIsEmpty(&deq))
        printf("%d ", DQRemoveFirst(&deq));

    printf("\n");

    // 데이터 넣기 2차
    DQAddFirst(&deq, 3);
    DQAddFirst(&deq, 2);
    DQAddFirst(&deq, 1);

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

    // 데이터 꺼내기 2차
    while(!DQIsEmpty(&deq))
        printf("%d ", DQRemoveLast(&deq));

    return 0;
}

> gcc .\Deque.c .\DequeMain.c        
> .\a.exe
> 출력
<First Insert & delete in deque>
1 2 3 4 5 6 
6 5 4 3 2 1

[추가] 덱을 기반으로 큐 구현하기

1. ADT

✅Operations:

void QueueInit(Queue * pq);
- 큐의 초기화
int QIsEmpty(Queue * pq);
- 큐가 비었는지 확인
void Enqueue(Queue * pq, Data data);
- enqueue 연산
Data Dequeue(Queue * pq);
- dequeue 연산
Data QPeek(Queue * pq);
- peek 연산

2. 헤더파일 (DequeBaseQueue.h)

#ifndef __DEQUE_BASE_QUEUE_H__
#define __DEQUE_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

3. 소스파일 (DequeBaseQueue.c)

#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);
}

이미 덱의 소스파일에서 구현을 다 해놨기 때문에 간편하게 함수만 가져오는 것으로 구현할 수 있다. 단 우리는 여기서 꼬리를 가리키는 포인터 변수가 움직여야 하는지, 머리를 가리키는 포인터 변수가 움직여야 하는지 확인해서 사용하면 된다.

4. 실행파일 (DequeBaseQueueMain.c)

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

int main()
{
    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;
}

> gcc .\Deque.c .\DequeBaseQueue.c .\DequeBaseQueueMain.c
> .\a.exe
> 출력
1 2 3 4 5

`<Review>`

드디어 큐까지 끝냈다.
다음은 어려운 트리가 진행될 예정...!
큐랑 덱은 앞서 배열, 리스트, 스택을 이용해서 구현하다 보니 이해하는 속도가 빨라졌다는 것을 느끼며 배울 수 있었다...!
오늘도 고생했다~

김민정

백엔드 코린이😁

이전 포스트

Chapter 06. 스택(Stack)

다음 포스트

Chapter 07. 큐(Queue)

윤성우 열혈 자료구조

07-1. 큐의 이해와 ADT 정의

큐(Queue)의 이해

큐(Queue) ADT 정의

07-2. 큐의 배열 기반 구현

큐의 구현에 대한 논리

원형 큐(Circular Queue)

원형 큐의 구현

1) 헤더파일(CircularQueue.h)

2) 소스파일(CircularQueue.c)

3) 실행파일(CircularQueueMain.c)

07-3. 큐의 연결 리스트 기반 구현

1) 헤더파일 정의(ListBaseQueue.h)

2) 소스파일 정의(ListBaseQueue.c)

3) 실행파일 정의(ListBaseQueueMain.c)

07-4. 큐의 활용

시뮬레이션(Simulation)

시뮬레이션 예제의 작성

07-5. 덱(Deque)의 이해와 구현

덱의 이해와 ADT 정의

덱의 구현

[추가] 덱을 기반으로 큐 구현하기

1. ADT

2. 헤더파일 (DequeBaseQueue.h)

3. 소스파일 (DequeBaseQueue.c)

4. 실행파일 (DequeBaseQueueMain.c)

`<Review>`

Chapter 06. 스택(Stack)

Chapter 08. 트리(Tree)

0개의 댓글