Queue(C언어)

Queue

 Queue는 데이터를 담는 자료구조로, Stack과 다르게 데이터를 순서대로 저장하는 자료구조이다. Queue는 가장 먼저 저장한 데이터를 가장 앞(front)에 저장하고, 가장 나중에 받은 데이터를 가장 뒤(rear)에 저장하는 FIFO(First In First Out) 구조이다.

 

 

Queue는 다음과 같은 연산을 가진다.

1. enqueue() - Queue에 데이터를 넣는다

2. dequeue() - Queue의 front에 있는 데이터를 제거, 반환한다 

3. peek() - Queue의 front에 있는 데이터를 제거하지 않고 반환한다

4. isEmpty() - Queue가 비어있는지 여부를 반환한다

5. size() - Queue의 크기를 반환한다

 

상황에 따라 추가적인 연산을 구현할 수 있다.

 

 

그림을 통해 Queue를 이해해 보자.

 

비어 있는 Queue이다.

 

 

 

enqueue 연산

 enqueue를 하면 새로운 데이터가 Queue의 front에 위치하게 된다. 여기서 의문이 생길 수 있다.

 

LinkedList의 방향이 왜 front에서 rear로 가는가?

 rear에서 front로 가는 것이 언뜻 보면 더 직관적이고 쉬워 보일 수 있다. 하지만, dequeue에서 문제가 발생한다. dequeue 연산을 한번 보자.

 

 

 

dequeue 연산

 dequeue 연산은 Queue의 front에 있는 데이터를 삭제하고 반환한다.

 아까의 의문에 대해 답해보자.

LinkedList의 방향이 왜 front에서 rear로 가는가?

만약, rear에서 front 방향으로 LinkedList가 연결되어 있다고 가정해 보자.

그럼 enqueue는 쉬울 것이다. front->next를 추가할 데이터를 담을 newLinkedList를 만들어주고, front를  newLinkedList로 만들어주면 된다. 

 하지만, dequeue를 하려면, next가 front인 LinkedList를 찾아서 그 LinkedList를 front로 만들어주어야 한다. 이 방법이 어떤 문제가 있을까? 

 

 시간복잡도를 따져 보았을 때, rear부터 next를 front로 가지는 LinkedList까지 탐색하려면 O(n)이다.

 하지만, 지금 사용하는 방식대로 LinkedList의 방향이 front에서 rear로 되어 있으면 O(1)이다. 

 

 성능 차이가 있다는 것이다. 성능은 컴퓨터공학에 있어 중요한 요소 중 하나이므로, 어떤 것을 구현하는 데에 있어 필수적으로 생각하는 습관을 길러야 한다. 

 

 

 

peek 연산

 peek 연산은 Queue의 front를 반환해 주면 된다.

 

 

 

isEmpty 연산

 isEmpty 연산은 Queue가 비어있으면 true, Queue가 비어있지 않으면 false를 반환한다.

 

 

 

size 연산

size 연산은 Queue에 저장되어 있는 데이터의 개수를 반환한다.

 

 

 

 

 

 

구현

Queue를 LinkedList를 사용해 구현해 보자.

 

Queue 선언

struct Queue {
	LinkedList* front;//Queue의 front(맨 앞)를 저장하는 Linked List
	LinkedList* rear;//Queue의 rear(맨 뒤)를 저장하는 Linked List
	int size;//Queue의 크기
}typedef Queue;

 Queue는 멤버 변수로 front, rear, size를 가진다. front는 맨 앞에 있는(맨 처음에 추가된) 데이터를 담는 LinkedList의 주소를 가진다. rear는 맨 뒤에 있는(맨 마지막에 추가된) 데이터를 담는 LinkedList의 주소를 가진다. 

 

 

 

enqueue

/*
* Description: Queue에 데이터를 추가하는 함수
* 
* Parameter:
* queue: Queue 포인터
* data: Queue에 추가할 데이터
* 
* Return:
* 성공 시 data, 실패 시 0
* */
int enqueue(Queue* queue, int data) {
	if (isFull(queue)) {
		return 0;
	}
	else {
		LinkedList* newLinkedList = (LinkedList*)malloc(sizeof(LinkedList));
		newLinkedList->data = data;
		newLinkedList->next = NULL;
		if (isEmpty(queue)) {
			queue->front = newLinkedList;
			queue->rear = newLinkedList;
		}
		else {
			queue->rear->next = newLinkedList;
			queue->rear = newLinkedList;
		}
		queue->size++;
		return data;
	}
}

 매개변수로 받은 데이터를 담는 newLinkedList를 만들고, rear의 next를 newLinkedList로 만든다. 그러고 나서 rear를 newLinkedList로 만들어주면 된다. 흐름은 다음과 같다.

 

 

 

dequeue

/*
* Description: Queue에서 데이터를 삭제, 반환하는 함수
* 
* Parameter:
* queue: Queue 포인터
* 
* Return:
* 성공 시 삭제한 데이터, 실패 시 -1
*/
int dequeue(Queue* queue) {
	if (isEmpty(queue)) {
		return -1;
	}
	else {
		LinkedList* temp = queue->front;
		int data = temp->data;
		queue->front = temp->next;
		free(temp);
		queue->size--;
		return data;
	}
}

 front를 temp에 담아둔 후, 반환할 데이터를 미리 저장해 놓고, front를 temp의 next로 만들어 준다. 그다음, temp를 free 시키고 데이터를 반환하면 된다. 다음과 같은 순서를 따르면 된다. 

1. Queue의 front를 임시로 저장하는 temp를 만든다.

2. return 할 데이터를 저장할 변수를 만들고 temp->data( front의 데이터)를 넣어준다.

3. Queue의 front를 temp->next로 바꿔준다.

4. temp를 free 시킨다.

5. 2에서 저장한 변수를 return 한다. 

 

 temp를 사용해 Queue의 front를 임시 저장하고 return 할 데이터를 저장하는 변수를 만드는 이유는 Queue의 front를 temp의 next로 바꿔주면 기존 front의 주소를 잃어버려 free 할 수 없고, 이에 따라 기존 front에 있던 데이터에도 접근할 수 없기 때문이다.

 

 

 

peek

/*
* Description: Queue의 front를 반환하는 함수
* 
* Parameter:
* queue: Queue 포인터
* 
* Return:
* 성공 시 front의 데이터, 실패 시 -1
* */
int peek(Queue* queue) {
	if (isEmpty(queue)) {
		return -1;
	}
	else {
		return queue->front->data;
	}
}

 peek는 정말 쉽다. 그냥 front에 있는 데이터를 반환하기만 하면 된다. 

 

 

 

isEmpty

/*
* Description: Queue가 비어 있는지 확인하는 함수
* 
* Parameter:
* queue: Queue 포인터
* 
* Return:
* 비어 있으면 1, 비어 있지 않으면 0
* */
int isEmpty(Queue* queue) {
	return queue->size == 0;
}

 

 isEmpty도 마찬가지로 쉽다. Queue의 size가 0과 같은지 여부를 반환하면 된다.

 

 

 

size

/*
* Description: Queue의 크기를 반환하는 함수
* 
* Parameter:
* queue: Queue 포인터
* 
* Return:
* Queue의 크기
*/
int getSize(Queue* queue) {
	return queue->size;
}

 enqueue, dequeue 연산에서 size를 ++, -- 했으므로, size연산은 Queue의 size를 반환하면 된다. 

 

 

 

 

 

 

 

 Queue는 알고리즘, 컴퓨터 하드웨어, 운영체제 등, 전반적인 컴퓨터공학 분야에서 사용되는 개념이다. Queue를 이해하고 사용할 줄 안다면, 컴퓨터공학을 배울 때 도움이 될 것이다. 

 

 

 

 

 

 

 

 

과제

Queue1.cpp

0.00MB

Queue2.cpp

0.00MB