211124, 자료구조 Ch 07-1

오늘은 스택만큼 유명한 "Queue (큐)" 를 알아보자.

Ch.07 Queue

07-1

액션~ 큐!!

가 아니고, 스택이랑 거의 비슷하다.

스택은 후입선출 구조였다. 나중에 넣은 애일수록 먼저 나온다는거다.

이거는 그냥 거의 개념은 비슷한데, 다르다. 선입선출(先入先出)이다. 먼저 넣은 애가 먼저 나온다는거다. 그냥 그게 끝이다.

이 큐의 ADT도 그냥 stack이랑 큰 차이가 없다.

Q. 앞서 Stack의 ADT는 뭐였을까? (복습해보자)

A. Push(저장), Pop(데이터 뽑기), Peek(맨 위에 뭐있나 훑어보기), Empty(비었는지 확인), Init(초기화).

놀랍게도, 큐도 똑같다. 저장, 뽑기, 훑기, empty, 초기화.

void QueueInit (Queue *pq); // 초기화
int QIsEmpty (Queue *pq); // 비었냐?

void Enqueue (Queue *pq, Data data); // 넣기
Data Dequeue (Queue *pq); // 뽑기

Data QPeek (Queue *pq); // 훑기

이렇게 다섯개다.

그리고, 이 큐도 배열 기반 / 연결 리스트 기반 각각의 방법으로 구현해낼 수 있다.

스택이랑 뭐 큰 차이 없을거같지? 어림도없다. 한번 보자.

07-2

우선, 큐의 논리적인 구조에 대해 이해해보자.

직접 그린 그림으로 설명해주겠따.

위와 같은 구조로 QueueInit을 해주면 초기상태로 초기화가 된다.

그 다음, 각각 A, B, D를 En (enqueue, 데이터 추가 과정) 해주면 위와같이 데이터가 하나씩 쌓인다. 그리고 F(Front), R(Rear)이 있는데, 이는 연결리스트의 head포인터와 tail포인터를 생각해주면 된다.

마지막으로 Dequeue 과정을 해주면 먼저 들어간 A가 빠져나오게 된다.

근데, 이 과정엔 단점이 하나 있다.

만약 Queue의 마지막 두 박스에 문자 B,D 가 각각 들어가있다고 가정을 하자. 근데 여기서 데이터를 더 추가하려면 어떻게 해야할까.

.. 이 단점을 해소하기 위해 흔히 사용하는 개념이 "원형 큐" 이다.

Circular Queue

아래와 같은 구조다. 현재 F와 R이 가리키고 있는 곳이 0인 지점이고, 이 원형큐는 ARR_LEN이 4인 큐가 되는 것이다.

그리고, 지금 여기서 F와 R이 가리키고 있는 이 지점은 채우지 않을 것이다. 연결리스트의 더미노드같은 느낌이라고 생각하면 된다.

한 줄로 요약하면, 배열의 길이가 N이라면, 데이터가 N-1개가 채워지면 이것이 꽉 찬 상태(Full)이라고 한다.

"엥? 굳이 네개의 공간에서 하나를 왜 버려요?"

왜냐면, 이 네개의 공간을 다 쓰면 F와 R이 꽉 찬 경우와 비어있는 경우를 구분할 수 없기 때문이다.

만약 위의 비어있는 상태에서 enqueue, dequeue를 해주면

이렇게 될 거다.

Enqueue를 해주면 Rear이 한 칸 뒤로 이동한 후 데이터를 삽입.

Dequeue를 해주면 Front가 한 칸 뒤로 이동한 후 데이터를 삭제.

만약 데이터가 꽉 차있으면 R의 앞에 F가 있을거고,

만약 데이터가 텅 비어있다면 F와 R이 같은 곳을 가리킬거다.

이런 것들을 감안해서, 원형큐를 구현해주면 되겠다.

/* CirQ.h */

#ifndef __CIR_Q_H__
#define __CIR_Q_H__

#define TRUE	1
#define FALSE   0

#define QUE_LEN 100
typedef int Data;

typedef struct _que {
    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

그 다음은 여기서 정의한 ADT들의 함수를 직접 구현해줘야 하는데, 그 전에 한가지 함수의 구현을 하겠다.

int NextPosIdx(int pos) { // F나 R을 다음 위치로 옮겨주는 함수
    if (pos == QUE_LEN-1) return 0;
    else return pos+1;
}

내가 얘를 보고 이해를 못해서 어제 머리가 조금 아팠었다.

조금 디테일하게 읊어보겠다.

일단. 위에 주석을 달아놓은것 처럼 NextPosIdx 라는 함수는 큐의 다음위치에 해당하는 배열의 인덱스 값을 반환하는 함수이다.

근데 여기서, 만약 전달받은 pos값이 이 Queue의 마지막 인덱스값에 있다면?

그러니까 쉽게 말해서, 위에 내가 그림으로 계속 설명한 Queue를 예로 들면, 이 큐의 QUE_LEN = 4이다. 네칸이니까.

그런데 이 데이터가 차고 차고 하다가 마지막인 네번째칸 (배열을 기준으론 세번째칸. arr[3]을 생각하자.) 에 다다랐을때가 Pos == QUE_LEN-1 이랑 같은 말이란거다.

그러면 0을 반환한다.

이 "0을 반환한다"의 의미는 뭘까?

우리가 지금 위에서 계속 그린 원형큐는 그냥 배열을 원형으로 휘어놓은것에 불과하다. 그래서 내가 지금 arr[3]에 다다르면 원래대로라면 다음 칸은 없어야하는데, 이 큐는 원형큐라서 계속 돌고 돌 수 있다. 그래서 arr[3]의 다음은 arr[0]이 된다. 다시 처음으로 돌아왔다는거지.

그래서 0을 반환한다.

아직 끝까지 안갔을 경우에는 그냥 다음 위치로 간다는 거고.

그렇다는거다.

/* CirQ.c */

#include <stdio.h>
#include <stdlib.h>
#include "CirQ.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("넣을 공간 없어요\n");
        exit(-1);
    }
    
    pq->rear = NextPosIdx(pq->rear); // rear을 한 칸 뒤로 옮기고
    pq->queArr[pq->rear] = data; // 현재 rear 위치에 데이터 넣기
}
Data Dequeue (Queue *pq) {
    if (QIsEmpty(pq)) {
        printf("뺄 게 없어요\n");
        exit(-1);
    }
    
    pq->front = NextPosIdx(pq->front); // front를 한 칸 뒤로 옮기고
    return pq->queArr[pq->front]; // 현재 front 위치에 데이터 넣기
}

Data QPeek (Queue *pq) {
    if (QIsEmpty(pq)) {
    	printf("볼 거 없어\n");
        exit(-1);
    }
    
    return pq->queArr[pq->front];
}

그렇다.

오늘은 일단

여기까지.