Ch07. 큐(Queue)

castlehi·2021년 8월 5일
자료구조
0

DataStructure

목록 보기
7/14
post-thumbnail

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

큐의 이해

선입선출의 자료구조
FIFO(First-In, First-Out)의 자료구조

큐의 ADT 정의

  • enqueue : 큐에 데이터를 넣는 연산
  • dequeue : 큐에서 데이터를 꺼내는 연산
  • 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연산의 방식

F : 큐의 머리
R : 큐의 꼬리

일반적이지 않은 dequeue연산의 방식
저장된 데이터를 한 칸씩 이동시켜야 한다는 단점이 있다

일반적인 dequeue연산의 방식
하지만 끝까지 갔지만 꽉 차지 않은 다음과 같은 상황이 발생할 수 있다

원형큐의 소개

R을 배열의 앞부분으로 이동시키면 해결할 수 있다
즉, 이를 원형 큐(circular queue)라 한다

원형 큐의 enqueue연산

원형 큐의 dequeue연산

F와 R 위치만 가지고는 꽉 찬 경우와 비어있는 경우를 구분할 수 없다
그러므로 큐를 꽉 채우지 않는다
배열의 길이가 n일 때 데이터가 n-1개 채워졌을 때 꽉 채워졌다고 간주한다

개선된 원형 큐

F와 R이 같은 위치를 가리키는 상태가 텅 빈 상태이다

개선된 원형 큐의 enqueue연산

  • enqueue 연산 : R이 가리키는 위치를 한 칸 이동시킨 다음, R이 가리키는 위치에 데이터를 저장
  • dequeue 연산 : F가 가리키는 위치를 한 칸 이동시킨 다음, F가 가리키는 위치의 데이터를 반환

개선된 원형 큐가 꽉 찬 상황

  • 원형 큐가 텅 빈 상태 : F와 R이 동일한 위치를 가리킨다
  • 원형 큐가 꽉 찬 상태 : R이 가리키는 위치의 앞을 F가 가리킨다

원형 큐의 구현

  • 헤더파일
#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;  // 그림을 통해서 F라 표현했던 멤버
    int rear;   // 그림을 통해서 R이라 표현했던 멤버
    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
  • F와 R의 회전을 돕는 함수
int NextPosIdx(int pos) // 큐의 다음 위치에 해당하는 인덱스 값 반환
{
    if(pos == QUE_LEN-1)
         return 0;
    else
         return pos+1;
}
  • 구현
#include <stdio.h>
#include <stdlib.h>
#include "CircularQueue.h"

void QueueInit(Queue *pq)   //텅 빈 경우 front와 rear은 동일위치 가리킴
{
    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);    //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)];
}

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

연결 리스트 기반 큐의 헤더파일 정의

#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;   //그림을 통해서 F라 표현한 멤버
    Node * rear;    //그림을 통해서 R이라 표현한 멤버
} LQueue;

typedef LQueue Queue;

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

void Enqueue(Queue *pq, Data data); //enqueue 연산 담당 함수
Data Dequeue(Queue *pq);    //dequeue 연산 담당 함수
Data QPeek(Queue *pq);

#endif

연결 리스트 기반 큐의 구현

처음 큐가 생성된 이후 F와 R이 가리킬 대상이 없으니 초기에는 NULL을 가리킨다

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

연결 리스트 기반의 큐가 비었다면 F에 NULL이 저장된다

int QIsEmpty(Queue *pq)
{
    if(pq->front == NULL) // F에 NULL이 저장되어 있으면,
        return TRUE; // 큐가 텅 빈 것이니 TRUE를 반환한다
    else
        return FALSE;
}

첫 번째 노드가 추가될 때에는 F뿐만 아니라 R도 새 노드를 가리키도록 설정한다
두 번째 이후의 노드가 추가될 때에는 F는 변함이 없고 R이 새 노드를 가리키게 한다

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

    if(QIsEmpty(pq)) // 첫 번째 노드의 추가라면,
    {
        pq->front = newNode; // front가 새 노드를 가리키게 하고,
        pq->rear = newNode; // rear도 새 노드를 가리키게 한다
    }
    else // 두 번째 이후의 노드 추가라면,
    {
         pq->rear->next = newNode; // 마지막 노드가 새 노드를 가리키게 하고,
         pq->rear = newNode; // rear가 새 노드를 가리키게 한다
    }
}

dequeue과정

  • F가 다음 노드를 가리키게 한다
  • F가 이전에 가리키던 노드를 소멸시킨다

이후의 과정은 모두 F에 저장된 값만을 참조하기 때문에, R에 쓰레기 값이 저장되는 상황은 문제가 되지 않는다

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

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

덱의 이해와 ADT의 정의

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

덱의 구현

  • 헤더파일
#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

덱의 구현은 양방향 연결리스트를 기반으로 한다

  • 코드
#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)  //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 = pdeq->head->data;
    
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error!");
        exit(-1);
    }
    
    pdeq->head = pdeq->head->next;
    free(rnode);
    
    if(pdeq->head == NULL)
        pdeq->tail = NULL;
    else
        pdeq->head->prev = NULL;
}

Data DQRemoveLast(Deque *pdeq)
{
    Node *rnode = pdeq->tail;
    Data rdata = pdeq->tail->data;
    
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error!");
        exit(-1);
    }
    
    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!");
        exit(-1);
    }
    
    return pdeq->head->data;
}

Data DQGetLast(Deque *pdeq)
{
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error!");
        exit(-1);
    }
    
    return pdeq->tail->data;
}
profile
castlehi
Back-end Developer
이전 포스트

Ch06. 스택(Stack)

다음 포스트

Ch08. 트리(Tree)

0개의 댓글