[C programming] 큐(Queue)

C programming -큐(Queue)

 

 

리눅스 환경에서 네트워크 프로그래밍을 공부하기 위해서 C언어를 다시 복습해야 할 필요성을 느꼈습니다. 따라서 이번 기회에 배열부터 전처리기까지 내용들을 정리하겠습니다.

 

---

큐란?

출처 : https://www.geeksforgeeks.org/what-is-queue-data-structure/

 

스택은 선형 자료구조로서 First In First OUT (FIFO) 규칙을 따릅니다. 즉, 처음에 들어온 요소가 가장 먼저 제거된다는 뜻입니다.

 

#define MAX 10
int queue[MAX];
int front, rear;

void put(int k) {
	// rear가 한계를 넘지 않았으면
	queue[++rear] = k;
}
int get() {
	// 큐가 비어있지 않으면
	return queue[front++];
}

 

큐의 기본적인 구현은 위와 같습니다. 스택과 마찬가지로 배열을 통해 구현이 가능합니다. 큐의 가장 앞을 가리키는 front와 가장 마지막을 가리키는 rear가 존재합니다. put() 함수를 통해서 rear를 1 증가시키고 큐의 가장 후방에 요소를 추가합니다. get() 함수는 front의 값을 1 증가시키고 큐의 가장 선두에 위치하는 값을 반환합니다.

 

하지만 이런 방식으로 구현된 큐는 계속해서 front와 rear가 뒤로 밀리면서 결국은 큐를 사용할 수 없게 됩니다. 따라서 원형 큐라는 방식을 이용해 볼 수 있습니다.

 

---

원형 큐란?

 

 

원형 큐는 일반 큐의 확장된 버전으로 큐의 마지막 요소가 첫 번째 요소와 원형으로 연결되어 있습니다.

 

출처 : https://www.geeksforgeeks.org/introduction-to-circular-queue/

 

위와 같이 enQueue()를 통해 요소를 추가하면 rear의 위치가 이동하고 deQueue()를 통해 요소를 제거하면 front의 위치가 이동합니다. 둘의 위치가 원형으로 이루어져 큐를 재활용 하는 것이 가능해집니다.

 

void put(int k) {
	// rear가 한계를 넘으면
	if ( (rear+1) % MAX == front ) {
		printf(“Queue overflow\n”);
		return -1;
	}
	queue[rear] = k;
	rear = ++rear % MAX;
}
int get() {
	int i;
	if (front == rear) { // 큐가 비어있으면
		printf(“Queue underflow\n”);
		return -1;
	}
	i = queue[front];
	front = ++front % MAX;
	return i;
}

 

 

 

---

큐와 연결리스트

연결리시트로 큐를 구현한다면 put 혹은 get을 하기 위해서 리스트 전체를 반드시 다 탐색해야 합니다. 이를 위해 이중 연결 리스트를 사용할 수 있습니다. 기존 연결리스트가 하나의 연결(next node)만 존재했다면 이중 연결리스트는 각 노드가 두 개의 연결(prev node, next node)을 가집니다.

 

출처 : https://www.prepbytes.com/blog/c-programming/how-to-implement-queue-using-doubly-linked-list-in-c/

 

struct node {
	int key;
	struct node *prev;
	struct node *next;
};
struct node *head, *tail;

void init_queue() {
	head = (struct node*)malloc(sizeof(struct node));
	tail = (struct node*)malloc(sizeof(struct node));
	head->prev = head;
	head->next = tail;
	tail->prev = head;
	tail->next = tail;
}

 

위와 같이 이중 연결 리스트(double linked list)와 큐를 구현했습니다. 이제 head 와 tail 사이에 값을 입력 해보겠습니다.

 

void put(int k) {
	struct node *t;
	if( ( t=(struct node*)malloc(sizeof(struct node)) == NULL ) {
		printf(“out of memory\n”);
		return -1;
	}
	t->key = k;
	tail->prev->next = t; // t를 꼬리 앞에 삽입
	t->prev = tail->prev;
	tail->prev = t;
	t->next = tail;
}

 

기존 연결 리스트에 값을 추가하는 것과 비슷합니다. 새로운 노드 t를 만들고 값을 추가합니다. 큐는 값을 뒤쪽에 추가하므로 tail 의 앞에 값을 추가합니다.

 

따라서 tail 의 이전 노드가 다음 노드로 t를 가리키도록 합니다. 여기서는 head 가 t 노드를 가리키게 됩니다. 다음으로 t 노드가 가리키는 이전 노드를 tail 의 이전 노드를 가리키도록 합니다. 마찬가지로 head 가 해당됩니다. 마지막으로 tail 의 연결을 t로 향하게 바꾸어줍니다.

 

int get(void) {
    struct node *t;
    int i;
	t = head->next;
	if( t==tail ) { // 큐가 비어있으면
		printf(“Queue underflow\n”);
		return -1;
	}
	i = t->key;
	head->next = t->next; // head 다음 노드를 삭제
	t->next->prev = head;
	free(t);
	return i;
}

 

head의 다음 노드를 삭제하기 위해서 head 가 삭제할 노드의 다음 노드를 가리키도록 합니다. 그리고 삭제할 노드의 다음 노드는 이전 노드로 head를 가리키게 됩니다.

void clear_queue() {
	struct node *t;
	struct node *s;
	t = head->next;
	while( t =! tail ) {
		s = t; // 삭제를 위해 복사
		t = t->next; // t는 다음으로
		free(s); // 삭제
	}
	head->next = tail;
	tail->prev = head;
}

 

큐를 전체 삭제하는 함수입니다. tail을 만날 때 까지 노드를 이동하며 메모리를 해제시킵니다. 마지막에는 head와 tail만 남게됩니다.

 

원형 큐는 많은 공간을 차지하지만 연결리스트는 필요할 때마다 공간을 할당할 수 있습니다. 하지만 특정 요소를 접근하기 위해서는 리스트 탐색을 해야한다는 단점이 있습니다. 또한 구현에 있어 조금 더 복잡한 문제를 가지고 있습니다.

 

---