큐(Queue)의 정의와 구현

Yuta 2021. 5. 17. 19:01

2021. 5. 17. 19:01

스택만큼이나 기본적인 자료구조인 큐에 대해 알아보려고 한다.

큐란

가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 형태의 자료구조이다.

이러한 형태를 선입선출(FIFO, First-In First-Out)이라 한다.

큐는 특히 일상생활에서 매우 쉽게 볼 수 있는 형태의 자료구조인데, 가장 쉽게 생각해볼 수 있는 것이 줄을 서는 것이다.

일렬로 줄을 서서 어떤 서비스를 받기 위한 차례를 기다릴 때 제일 먼저 줄을 선 사람이 제일 먼저 서비스를 받는다.

이것이 큐이다.

스택에서와 달리 큐를 구현할 때에는 데이터의 맨 앞과 맨 뒤를 가리키도록 하는 변수가 각각 필요하다.

데이터의 맨 앞에서는 삭제가 일어나고 맨 뒤에서는 삽입이 일어난다.

여기에서 맨 앞을 가리키는 것을 front라 하고 맨 뒤를 가리키는 것을 rear라 한다.

이러한 개념을 가지고 큐를 직접 구현해보면서 동작 방식에 대해 설명하겠다. (구현에는 C언어를 사용하였다.)

쉬운 이해를 위해 선형 배열을 사용하여 구현하려고 한다. (선형 배열을 사용할 경우에 발생하는 문제는 잠시 후에 살펴보려고 한다.)

1. 초기화

#define SIZE 5

int queue[SIZE] = { 0 };
int front = 0, rear = 0;

우선 크기가 5인 배열을 선언하고 0으로 초기화를 하였다.

그런 뒤, front와 rear의 값을 모두 0으로 초기화하였는데, 이 값은 구현하려고 하는 방식에 따라 달라질 수 있다.

여기서 front에는 삭제가 될 곳을 가리키는 곳을 저장하도록 하였고, rear는 추가가 될 곳을 저장하도록 하였다.

2. 삽입

다음으로, 큐에 데이터를 추가하는 메소드인 enqueue()를 구현해보자.

void enqueue(int *queue, int front, int *rear, int data){
	if(*rear - front + 1 == SIZE){
    	fullQueueException();
    }
    
    queue[*rear] = data;
    *rear += 1
}

큐에 데이터를 추가할 때에는 front의 값은 변화하지 않으므로 rear만 call by reference 형태로 하였다.

배열을 사용하여 구현하고 있기 때문에 최대 삽입 가능 원소 개수에 제한이 있는 배열의 특성상 가득 찰 경우에 대한 예외 처리를 해주어야 한다.

만약 큐가 가득 찬 상태가 아닐 경우 queue의 rear 위치에 data를 넣고 rear의 값을 하나 증가시킨다.

3. 삭제

이번에는 큐에 있는 데이터를 삭제하는 메소드인 dequeue()를 구현해보자.

int dequeue(int *queue, int *front, int rear){
	int data;
	if(rear == front){
    	emptyQueueException();
    }
    
    data = queue[*front];
    *front += 1;
    return data;
}

dequeue를 할 때에는 front에서 작업이 일어나므로 값이 변경될 일이 없는 rear는 call by value로 넘겨받도록 하였다.

또한, 큐에 있는 데이터를 삭제할 때에는 구현방법과 관계없이 큐가 비어있을 때에 대한 예외처리를 꼭 해주어야 한다.

큐가 비어있지 않을 경우에는 큐의 front 에 위치한 값을 저장해둔 뒤에 front의 값을 하나 증가시킨다.

이렇게 선형 배열을 사용하여 큐를 구현하면 구현이 단순하다는 장점은 있지만.. 일회성 큐가 되어버린다.

왜냐하면 지금과 같이 크기가 5인 배열을 이용하여 큐를 만들게 되면

5개의 값을 삽입하고 5개의 값을 삭제할 경우 front와 rear값이 모두 배열의 마지막 인덱스를 가리키게 될 것인데,

이후로는 더 이상 가리킬 수 있는 곳이 없어 데이터를 삽입하거나 삭제할 수 없다.

따라서 이를 해결하기 위해 원형 배열이라는 것을 사용하여 다시 구현해보려고 한다.

원형 배열이란

물리적으로는 선형 배열과 다를 것이 없는 일반 배열이지만,

프로그래밍을 할 때 배열의 인덱스를 나타내는 값을 증가시켜줌과 동시에 그것을 다시 배열의 크기로 나눈 나머지를 인덱스로 이용하는 것이다.

원형 배열을 사용할 경우 배열의 인덱스를 마지막 위치(7)까지 가리키게 된다고 하더라도, 여기에 하나 증가시킨 값인 8을 배열의 크기인 8로 나눠 다시 0번째 인덱스를 가리키는 방식으로 사용할 수 있으므로, 배열이 가득 차지 않는 한 배열의 나머지 공간을 계속해서 사용할 수 있게 된다.

이러한 개념을 이용하여 enqueue와 dequeue를 다시 구현하면 다음과 같다.

#define SIZE 5

int queue[5] = { 0 };
int front = 0, rear = 0;

void enqueue(int *queue, int front, int *rear, int data){
	if((SIZE + rear - front) % SIZE == SIZE){
    	fullQueueException();
    }
    
    queue[*rear] = data;
    *rear = (*rear + 1) % SIZE;
}

int dequeue(int *queue, int *front, int rear){
	int data;
    
    if(front == *rear){
    	emptyQueueException();
    }
    
    data = queue[*front];
    *front = (*front + 1) % SIZE;
    return data;
}

enqueue와 dequeue에서 각각에 대한 처리를 한 후, front와 rear에 1을 더해주지만 이 때 더해준 값을 배열의 전체 크기로 나눈 나머지 값을 front와 rear의 값으로 사용하기 때문에 배열의 범위를 넘어서게 되더라도 다시 0번 인덱스로 돌아오게 된다.

이렇게 원형 배열을 이용하여 구현하면 단순 선형 배열로 큐를 구현할 때에 발생되는 일회적인 사용에 대한 문제는 해결이 된다.

하지만 원형 배열은 새로운 문제점을 야기한다.

바로, 배열이 비어있는 상태일 때와 가득찬 상태에 대한 구분이 안된다는 것이다.

이렇게 코딩을 한 후 실행하면 배열이 꽉 찼음에도 불구하고 비어있는 배열처럼 인식하여 fullQueueException이 발령되지 않는다.

배열이 비어있는 경우 front와 rear 값이 같아지게 되는데, 배열이 꽉 찼을 때에도 front와 rear값이 같아지기 때문이다.

여기에는 이를 해결하기 위한 두 가지 방법이 있다.

첫 번째는 배열에 저장되어있는 원소의 개수를 저장하는 것이고,

두 번째는 배열의 한 자리를 남겨둔 채로 사용하는 것이다.

첫 번째 방법을 사용하면 배열의 메모리를 모두 사용할 수 있지만, 매번 저장되어있는 원소의 개수를 유지해야 한다는 단점이 있고

두 번째 방법을 사용하면 배열의 메모리 한 칸을 낭비하게 되지만, 원소의 개수를 유지하지 않아도 된다.

둘 중 어느 방법을 사용할지는 개발하는 사람의 몫이다.

각각의 방법을 사용하여 구현한 경우를 남겨두겠다.

- 첫번째: 원소의 개수를 저장하는 방법

#define SIZE 5

int queue[SIZE] = { 0 };
int front = 0, rear = 0;
int count = 0; // 원소의 갯수를 저장할 변수

void enqueue(int *queue, int front, int *rear, int *count, int data){
	if(*count == SIZE){
    	fullQueueException();
    }
    
    queue[*rear] = data;
    *rear = (*rear + 1) % SIZE;
    *count += 1;
}

int dequeue(int *queue, int *front, int rear, int *count){
	int data;
    
    if(*count == 0){
    	emptyQueueException();
    }
    
    data = queue[*front];
    *front = (*front + 1) % SIZE;
    *count -= 1;
    return data;
}

- 두번째: 배열의 한 칸을 비우고 사용하는 방법

#define SIZE 5

int queue[SIZE] = { 0 };
int front = 0, rear = 0;

void enqueue(int *queue, int front, int *rear, int data){
	if((*rear + 1) % SIZE == front){
    	fullQueueException();
    }
    
    queue[*rear] = data;
    *rear = (*rear + 1) % SIZE;
}

int dequeue(int *queue, int *front, int rear){
	int data;
    
	if(*front == rear){
    	emptyQueueException();
    }
    
    data = queue[*front];
    *front = (*front + 1) % SIZE;
    return data;
}

시간 복잡도

배열을 사용하여 큐를 구현한 경우 각 작업의 시간 복잡도는 선형 배열에서와 원형 배열에서 모두 O(1)이 된다.

그 밖에도 배열로 큐를 구현하여 사용하게 될 경우, 배열의 특성상 front와 rear 위치가 아닌 다른 위치의 인덱스에도 곧장 접근이 가능하다. 그러나 큐를 큐답게 쓰기 위해서는 꼭 enqueue와 dequeue 작업을 이용하여 삽입과 삭제 위치를 지키면서 사용해야 한다.

끝으로 연결 리스트를 이용하여 큐를 구현한 코드를 첨부하고 마무리하려고 한다.

연결리스트를 이용하여 큐를 구현한 경우에도 시간 복잡도는 배열에서와 마찬가지로 O(1)이 되고,

배열에서와 달리 메모리의 한계가 존재하지 않으므로 fullQueueException 처리를 할 필요가 없게 된다.

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
	int data;
    struct _node *next;
} NODE;

int *front = NULL, *rear = NULL;

NODE* getnode(int data){
	NODE *node = (NODE*)malloc(sizeof(NODE));
    node->next = NULL;
    return node;
}

void enqueue(int **front, int **rear, int data){
	NODE *node = getnode(data);
    
    if(*rear == NULL) *front = node;
    else (*rear)->next = node;
    *rear = node;
}

int dequeue(int **front, int **rear){
	int data;
    NODE *tmp = NULL;
    
    if(*front == NULL){
    	emptyQueueException();
    }
    
    data = (*front)->data;
    tmp = *front;
    *front = (*front)->next;
    
    if(*front == NULL) *rear = NULL; // 값을 삭제한 뒤 남은 노드가 없는 경우 rear에도 NULL 대입
    
    free(tmp);
    return data;
}

저작자표시

'DataStructure' 카테고리의 다른 글

힙(Heap)의 정의와 구현 (0)	2021.10.22
스택(Stack)의 정의와 구현 (0)	2021.05.17

Security Note