오늘은 스택만큼 유명한 "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];
}그렇다.
오늘은 일단
여기까지.
