CS/자료구조

Ch07. 큐(Queue)

박 성 하 2022. 4. 7. 14:16

728x90

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의 회전을 돕는 함수
```c
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. 큐의 연결 리스트 기반 구현
### 연결 리스트 기반 큐의 헤더파일 정의
```c
#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


_덱의 구현은 **양방향 연결리스트**를 기반으로 한다_
![](https://images.velog.io/images/www_castlehi/post/a5eeedc8-4366-4de4-afcd-77ba58a28e50/F4726354-98AA-47B2-9CC5-4B348AEA2748.jpeg)

- 코드
```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)  //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;
}

728x90

저작자표시 비영리

'CS > 자료구조' 카테고리의 다른 글

Ch09. 우선순위 큐(Priority Queue)와 힙(Heap) (0)	2022.04.07
Ch08. 트리(Tree) (0)	2022.04.07
Ch06. 스택(Stack) (0)	2022.04.07
Ch05. 연결리스트-3 (0)	2022.04.07
Ch04. 연결리스트-2 (0)	2022.04.07

현재글Ch07. 큐(Queue)

백엔드 개발자의 IT 공부 블로그

자료구조, SWEA, 리눅스마스터 2급, wan, 코딩테스트, 트리의 지름, 프로그래머스, 컴퓨터 구조, lan, 부분수열의 합, 나머지, 큐, 자바, 알고리즘, 구름톤 챌린지, 연결리스트, 백준, 네트워크, 컴퓨터구조, 객체지향,

일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

www.castlehi.com

Ch07. 큐(Queue)

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

큐의 이해

큐의 ADT 정의

큐의 배열 기반 구현

원형큐의 소개

원형 큐의 구현

연결 리스트 기반 큐의 구현

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

덱의 이해와 ADT의 정의

덱의 구현

'CS > 자료구조' 카테고리의 다른 글

'CS/자료구조'의 다른글

티스토리툴바

Ch07. 큐(Queue)

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

큐의 이해

큐의 ADT 정의

큐의 배열 기반 구현

원형큐의 소개

원형 큐의 구현

연결 리스트 기반 큐의 구현

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

덱의 이해와 ADT의 정의

덱의 구현

'CS > 자료구조' 카테고리의 다른 글

'CS/자료구조'의 다른글

관련글

티스토리툴바