[자료구조(C언어] 연결리스트로 큐(Queue) 구현하기

※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.

---

단방향 연결리스트로 큐 구현하기

연결리스트의 맨 앞에서는 삽입과 삭제가 모두 어렵지 않다.

그러나 연결리스트의 맨 뒤에서는, 삽입은 괜찮지만 삭제를 하기가 어렵다.

단방향 연결리스트에서 어떤 노드를 삭제하기 위해서는 이전 노드의 주소를 알아야하기 때문이다.

따라서 연결리스트의 뒤쪽을 삽입이 일어나는 rear로,

앞쪽을 삭제가 일어나는 front로 하는 것이 유리하다.

삽입을 하기 위해서는 마지막 노드의 주소를 항상 기억해야 하므로,

연결리스트 포인터 구조체에 첫번째 노드의 주소를 저장하는 front변수(=head) 외에도 rear 변수를 따로 둬서 마지막 노드 주소를 저장하는 데 사용한다.

 

헤더파일 정의하기

queueADT.h

#ifndef QUEUEADT_H
#define QUEUEADT_H

#include <stdbool.h> /* C99 only */

typedef int Item;
typedef struct queue_type *Queue;

Queue create();
void destroy(Queue q);
void make_empty(Queue q);
bool is_empty(Queue q);
void enqueue(Queue q, Item i);
Item dequeue(Queue q);
Item peek(Queue q);
int get_size(Queue q);

#endif

스택을 구현할 때와 함수의 종류가 거의 비슷하지만,

큐에 현재까지 저장된 데이터의 수가 몇개인지 알아낼 수 있는 get_size()함수가 추가되었다.

 

구조체 정의하기

queueADT.c

#include <stido.h>
#include <stdlib.h>
#include "queueADT.h"

struct node {
	Item data;
	struct node *next;
};

struct queue_type {
	struct node *front;
	struct node *rear;
	int size;
};

 

함수 정의하기 1 - 기본 함수들

queueADT.c

void terminate(const char *message) /* 예외 처리 */
{
	printf("%s\n", message);
	exit(EXIT_FAILURE);
}

int get_size(Queue q)
{
	return q->size;
}

Queue create()
{
	Queue q = (Queue)malloc(sizeof(struct queue_type));
	if (q == NULL)
		terminate("Error in create: queue could not be created.");
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
	return q;
}

void destroy(Queue q)
{
	make_empty(q);
	free(q);
}

void make_empty(Queue q)
{
	while (!is_empty(q))
		dequeue(q);
	q->size = 0;
}

 

함수 정의하기 2 - enqueue() 함수

bool is_empty(Queue q)
{
	return q->front == NULL; 
	/* or return q->size == 0 */
}

void enqueue(Queue q, Item I)
{
	struct node *new_node = (struct node *)malloc(sizeof(struct node));
	if (new_node == NULL)
		terminate("Error in push: queue is full.");

	new_node->data = i;
	new_node->next = NULL;

	/* q가 비어있을 때 */
	if (q->front == NULL) {
		q->front = new_node;
		q->rear = new_node;
	}
	/* q에 하나 이상의 노드가 있을 때 */
	else {
		q->rear->next = new_node;
		q->rear = new_node;
	}
	q->size++;
}

 

함수 정의하기 3 - dequeue() 함수, peek() 함수

Item dequeue(Queue q)
{
	struct node *old_front;
	Item i;

	if (is_empty(q)) /* q가 비어있을 때 */
		terminate("Error in dequeue: queue is empty.");

	old_front = q->front;
	i = old_front->data;
	q->front = old_front->next;

	
	if (q->front == NULL) /* q에 하나의 노드만 있었을 때 */
		q->rear = NULL;
	
	free(old_front);
	q->size--;
	return i;
}


Item peek(Queue q)
{
	if (is_empty(q))
		terminate("Error in peek: queue is empty.");
	return q->front->data;
}

dequeue() 함수는 q의 front가 두번째 노드를 가리키도록 한다.

또한 첫번째 노드를 free시켜주고, 첫번째 노드에 담긴 데이터(Item)를 반환해주는 일도 한다.