큐는 FIFO (First In First Out), 즉 선입선출 방식의 자료구조이다
그렇기 때문에 데이터가 삽입되는 곳과 삭제되는 곳이 정해져있다
데이터가 삽입되는 곳을 tail, rear, arrival 등으로 표현하고 데이터가 삭제되는 곳을 head, front, service 등으로 표현하는데, 본 글에서는 데이터가 삽입되는 곳을 tail, 삭제되는 곳을 head로 명명할 예정이다
큐도 마찬가지로 배열과 연결 리스트로 생성가능한데, 연결 리스트 큐를 알아보기 전에 큐의 ADT 먼저 확인해보자
// 최대 크기가 max_size인 공백 큐를 생성
create(max_size)
// 큐 초기화
init(q)
// 큐가 비었는지 확인
is_empty(q)
{
if (size == 0) return TRUE; // 큐가 비었을 때
else return FALSE;
}
// 큐가 가득 차있는지 확인
is_full(q)
{
if (size == max_size) return TRUE; // 큐가 가득 차있을 때
else return FALSE;
}
// 큐에 데이터 하나 삽입
enQ(q, e)
{
if (is_full(q)) return ERROR;
else q의 맨 뒤에 데이터 e 추가
}
// 큐에서 데이터 하나 삭제
deQ(q)
{
if (is_empty(q)) return ERROR;
else q의 맨 앞에 있는 데이터를 읽고 반환
}큐를 사용할 때, 위와 같은 기능들을 고려하여 구현하면 된다
SLL 큐
정의
typedef int Data;
typedef struct
{
Data data;
struct Node *Next;
} Node;
생성
Node *head, *tail;
head = (Node *)malloc(sizeof(Node));
head -> data = 10;
head -> Next = NULL;
tail = head;정의와 생성도 일반적인 단순 연결 리스트를 정의하고 생성하는 것과 같다
하지만 다른 점이 있다면 tail 포인터를 추가적으로 생성해서 삽입된 노드를 가리키고 있어야 한다는 점이다
위의 코드에서는 아직 노드가 한개뿐이므로 head와 tail이 가리키는 값이 동일하다
그림으로 확인하면 아래와 같다
삽입
큐의 삽입은 enQ라고 명명하고 구현 코드는 아래와 같다
void enQ(Data value)
{
Node *p = (Node *)malloc(sizeof(Node));
p -> data = value;
p -> Next = NULL;
if (tail != NULL) // 큐에 데이터가 있으면
{
tail -> Next = p; // ①
tail = p; // ②
}
else head = tail = p; // 큐가 비었으면
}SLL 큐의 경우에는 동적으로 큐가 계속 삽입될 수 있기 때문에 is_full() 함수가 필요 없이 큐에 데이터가 있을 때와 없을 때, 두 가지 경우로 나누어 구현하면 된다
그림으로 표현하면 아래와 같다
삭제
큐의 삭제는 deQ라고 명명하고 구현 코드는 아래와 같다
Node* deQ()
{
Node *p = (Node *)malloc(sizeof(Node));
if (head == NULL)
{
printf("underflow!!!\n");
exit(-1);
}
else
{
p = head; // ①
head = head -> Next; // ②
return p; // ③
}
}
배열 큐
이제 배열로 만든 큐를 알아볼 차례다
배열 큐의 특징은 head와 tail 변수를 따로 선언해서 head와 tail이 각각 삭제할 데이터와 최근 삽입된 데이터를 가리키게 한다는 점이다
정의와 생성
#define MAX_SIZE 10
int Q[MAX_SIZE];
int head = 0, tail = 0;
삽입과 삭제
void enQ(int data)
{
Q[++tail] = data;
}
int deQ()
{
return Q[head++];
}리스트 큐에 비해 훨씬 간단하게 구현이 가능하다
하지만 이렇게 구현하면 deQ()가 진행될 때마다 큐 앞쪽의 빈 공간이 생겨버리는 단점이 생긴다
배열 크기만큼 enQ()를 진행하고 어느정도 deQ()를 진행했다고 가정했을 때, 비어 있는 앞쪽 공간에 더 데이터를 삽입할 수 없을까?
이런 생각으로 만들어진 것이 원형 큐이다
보통 원형 큐를 묘사하는 그림은 위의 왼쪽과 같이 동그란 자료구조에 데이터를 삽입하고 삭제하는 형태를 띈다
하지만 이는 알기 쉽게 보여주기 위한 수단일 뿐, 실제 원형 큐는 1차원 배열로 생성되며 아까 선언했던 head와 tail 값이 배열 크기를 넘어가면 다시 배열의 맨 처음 값으로 돌아와 삽입과 삭제를 반복한다
그림처럼 원형 큐를 잘라 똑바로 편다면 일차원 배열이 되는 것을 확인할 수 있다
이제 이러한 원형 큐를 어떻게 구현하는지 알아보자
정의과 생성
원형 큐의 정의과 생성은 일반 배열 큐와 같다
삽입과 삭제
void enQ(int data)
{
if (head == tail) return; // 큐가 가득 차 있을 때
Q[tail] = data; // 큐에 자리가 있을 때
tail = (tail + 1) % MAX_SIZE;
}
int deQ()
{
if (head == tail) return; // 큐가 텅 비었을 때
int p; // 큐에 꺼내갈 데이터가 있을 때
p = Q[head];
head = (head + 1) % MAX_SIZE;
return p;
}원형 큐와 일반 배열 큐의 차이점은 두 가지다
① 연산 전에 큐가 비었는지, 가득 차 있는지 확인 후 연산을 시작
② head와 tail 값의 증감을 배열의 크기로 나눈 나머지로 계산
그러나 이렇게 배열을 구현해도 큐 내부 상태 조건식(3번과 10번 라인)이 동일하기 때문에 실질적으로 사용이 불가능하다
이에 대한 해결 방안은 아래와 같다
1. head, tail의 초기치 변경
안된다
2. counter 변수 사용
counter 변수를 사용해 배열 안의 데이터 갯수를 세어 삽입, 삭제를 돕는다
가득 차 있을 때의 조건은 couter == MAX_SIZE, 텅 비어 있을 때 조건은 counter == 0인데,
이러한 방법은 운영체제 입장에서 달갑지 않은 방법이라고 하여 사용하지 않는다고 한다
3. 배열을 한 칸 덜 사용하기
가득 차 있을 때의 조건은 head == (tail + 1) % MAX_SIZE, 텅 비어 있을 때 조건은 head == tail이며, 보통 3번 방법을 사용하여 원형 큐를 구현한다
그림으로 표현하면 위와 같다
FULL 조건의 경우 몇 번의 삽입과 삭제가 이루어져 head와 tail 모두 초기치와 다른 위치에 있는 것을 확인할 수 있고 EMPTY 조건의 경우 한번도 삽입, 삭제가 이루어지지 않았거나, 우연히 head, tail 값이 초기치와 같은 경우이며, 물론 head, tail이 동일한 위치를 가리키기만 하면 어느 인덱스를 가리켜도 상관 없다
정의와 생성
#define MAX_SIZE 10
int circular_queue[MAX_SIZE];
int head = 0, tail = 0;
삽입과 삭제
void enQ(int data)
{
if (head == ((tail + 1) % MAX_SIZE) return; // 큐가 가득 차 있을 때
Q[tail] = data; // 큐에 자리가 있을 때
tail = (tail + 1) % MAX_SIZE;
}
int deQ()
{
if (head == tail) return; // 큐가 텅 비었을 때
int p; // 큐에 꺼내갈 데이터가 있을 때
p = Q[head];
head = (head + 1) % MAX_SIZE;
return p;
}위 코드의 3번 라인처럼, 기존 큐 삽입과 삭제 코드에서 큐가 가득 차 있을 때의 조건식만 변경해주면 원형 큐의 삽입, 삭제를 간단히 구현할 수 있다
마지막으로 큐의 장단점을 알아보자
장점 : 데이터의 삽입, 삭제가 용이하다
단점 : 중간 데이터에 접근이 불가능하다