이번 시간에는 "큐"입니다. 버스나 지하철을 보시면 먼저 대기한 사람이 먼저 들어가죠? 바로 그런 선입선출의 순서를 따르는 것이 큐입니다.
큐 ADT란?
큐도 어떠한 개체를 저장하는 자료구조이고 삽입과 삭제를 아까 말씀드린 선입선출의 방식으로 구현합니다.
따라서 삽입은 큐의 뒤에서 삭제는 큐의 앞에서 수행하게 됩니다.
큐 ADT 메쏘드는 무엇이 있을까?
주로 쓰이는 큐 메쏘드는 대표적으로
- push : 원소 삽입
- pop : 원소를 삭제하고 반환
그리고 보조적으로 쓰이는
- seek : 큐의 앞부분에 있는 원소를 삭제하지 않고 반환
- size : 원소 개수 반환
- isEmpty : 큐가 비어있는지 여부를 반환
- printQueue : 큐의 원소들 전부를 출력
주로 이러한 메쏘드가 존재하고 있고 이것을 활용해서 큐의 작업을 할 수 있겠습니다~
이러한 큐를 응용한다면?
우리는 큐를 활용해서 무엇을 할 수 있을까요?
큐의 의미처럼 보통 먼저 입력된 데이터를 먼저 처리해야 하는 상황에서 주로 쓰이는 데요
직접적으로 응용을 해서
- 은행의 대기열 같은 시스템을 만듭니다.
- 프린터의 인쇄 대기열 시스템을 만들 수 있습니다.
그리고 간접적으로 응용을 한다면 보조적인 데이터 구조로 활용할 수 있습니다.
큐 ADT 구현을 위해서...
큐도 스택의 경우처럼 배열과 연결 리스트로 구현할 수 있습니다.
먼저 배열로 구현을 해봅시다.
우리는 배열로 큐 ADT를 구현할 때 원형 배열을 통해서 만들어낼 수 있습니다. 그리고 이러한 원형 배열에서 큐의 앞과 뒤를 알려줄 front, rear에 관련된 변수가 필요합니다.
그러면 먼저 빈큐인지 아닌지 판단하는 isEmpty() 함수와 큐가 full인지 판단하는 isFull() 함수를 보도록 하겠습니다.
int isEmpty(QUEUE* pque)
{
if ((pque->r % pque->N) == pque->f) //
return 1;
return 0;
}
int isFull(QUEUE* pque)
{
if ((pque->r + 1 % pque->N) == pque->f)
return 1;
return 0;
}
여기서 r은 rear의 index값을 가지고 있는 변수이고 f는 front의 index값을 가지고 있는 변수입니다. N은 큐의 전체 크기를 나타내는 변수입니다. 따라서 r과 f가 동일한 위치를 가리킬 때 원형 큐가 텅 빈 상태라는 뜻을 가지고 r의 한 칸 앞에 f가 있다면 큐가 꽉 찼다는 뜻입니다. 여기서 N으로 나눠준 이유는 혹시라도 r의 값이 N을 넘을 수도 있으니 r값이 N 보다 작은 값을 가질 수 있도록 N으로 나눴습니다.
이제 주로 쓰이는 enqueue함수와 dequeue함수를 살펴보도록 하겠습니다.
void enqueue(QUEUE* pque, int e) //원소 삽입
{
if (isFull(pque)) //꽉찬 큐에서 삽입을 시도한다면
{
printf("overflow\n");
printQueue(pque);
freeQueue(pque);
exit(1);
}
pque->r = (pque->r + 1) % pque->N;
pque->que[pque->r] = e;
}
int dequeue(QUEUE* pque) //원소 제거 후 반환
{
if (isEmpty(pque)) //비어있는 큐에서 제거를 시도한다면
{
printf("underflow\n");
free(pque);
exit(1);
}
int elem;
pque->f = (pque->f + 1) % pque->N;
elem = pque->que[pque->f];
pque->que[pque->f] = 0;
return elem;
}
이렇게 enqueue함수에서 먼저 원형 큐가 꽉 찬 상태에서 삽입이 이뤄지면 안 되니까 isFull() 함수로 꽉 찬 상태에서의 삽입을 피해 갈 수 있게 했습니다. 그리고 삽입을 할 때에는 r의 값을 1 올리고 그 index에서 원소를 넣을 수 있도록 했습니다.
그리고 dequeue에서도 큐가 비어있을 때 제거를 할 수 없으니 isEmpty() 함수를 통해서 이를 피해 갈 수 있도록 설정했습니다. 이후 f의 값을 1 올리고 그곳의 원소를 따로 반환할 수 있도록 저장한 후 0으로 초기화해서 삭제를 합니다.
전체 코드!
그리고 연결리스트로 구현해보겠습니다.
우선 연결리스트로 구현할 때는 아까와 달리 꽉 찬다는 개념이 없습니다. 계속해서 노드를 만들고 연결시키면 되기 때문이죠! 따라서 isFull() 함수는 없어지고 isEmpty() 함수만 쓰입니다.
이제 구조체 정의와 초기화 함수를 알아보겠습니다.
typedef struct _node
{
struct _node* next;
int elem;
} Node;
typedef struct _queue
{
Node* f; //front, rear
Node* r;
} QUEUE;
void initQueue(QUEUE* pque)
{
pque->f = NULL;
pque->r = NULL;
}이렇듯 구조체 QUEUE에서 구조체 Node포인터 변수 f와 r을 선언한 것을 볼 수 있습니다. 이 포인터 변수들로 큐의 front와 rear를 가리킬 수 있습니다. 그리고 초기화할 때는 NULL을 가리키도록 설정합니다. 여기에서 알 수 있듯이 포인터가 NULL을 가리킨다면 큐가 비어있다는 것으로 알 수 있습니다.
그리고 enqueue와 dequeue함수도 보겠습니다.
void enqueue(QUEUE* pque, int e)
{
Node* new_Node = (Node*)malloc(sizeof(Node));
new_Node->elem = e;
new_Node->next = NULL;
if (isEmpty(pque))
{
pque->f = new_Node;
pque->r = new_Node;
}
else
{
pque->r->next = new_Node;
pque->r = new_Node;
}
}
따라서 enqueue작업을 할 때 만약 큐가 비어있는 상태였다면 포인터 f, r을 새로 만든 노드를 가리키도록 합니다. 그리고 비어있지 않다면 먼저 r의 next가 new_Node를 가리키도록 합니다. 그 후에 여전히 r이 추가한 노드 이전을 가리키고 있는 상태겠죠? 따라서 갱신을 하기 위해서 r을 다시 new_Node를 가리키도록 합니다. 이렇게 해서 연속적으로 enqueue작업을 할 수 있습니다. 이 과정을 좀 더 이해하기 쉽게 제 허접한 그림실력으로 표현해보았습니다.....
int dequeue(QUEUE* pque)
{
if (isEmpty(pque))
{
printf("EmptyQueueException!\n");
freeQueue(pque);
exit(1);
}
int tmp = pque->f->elem;
Node* ptr = pque->f;
pque->f = pque->f->next;
if (pque->f == NULL)
pque->r = NULL;
free(ptr);
return tmp;
}먼저 f의 원소를 따로 저장하고 ptr포인터로 f위치를 가리키게 합니다. 그리고 f의 위치를 next로 바꾸고 만약에 이때 f가 NULL을 가리키고 있다면 r도 NULL을 가리키게 합니다. 그리고 원래 f위치를 가리키고 있었던 ptr포인터를 활용해서 f위치에 있던 노드를 할당 해제하고 따로 저장했던 원소를 반환합니다. 이것도 그림을 그려서 표현해봤습니다.
전체 코드!
데크 ADT
사실 데크는 다른 책들에서는 그렇게 중요하게 짚고 넘어가는 게 아니라서 편하게 보시면 될 것 같습니다.
먼저, 간단히 설명하자면 삽입과 삭제가 앞 뒤 어디에서든 가능한 스택과 큐를 합친 듯한 느낌의 ADT입니다.
그림에서 볼 수 있듯이 front에서도 삽입과 삭제가 가능하고 rear에서도 삽입과 삭제가 가능한 것을 볼 수 있습니다.
이러한 데크 ADT에서는 front에서 원소를 삽입, 삭제를 하는 기능과 rear에서 원소를 삽입, 삭제하는 기능이 대표적입니다.
데크 설명은 여기까지 하고 끝내도록 하겠습니다~ 감사합니다
