[C] 이중 연결 리스트로 구현한 큐

출처 - C로 배우는 알고리즘 (이재규 지음)

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

typedef struct _node
{
	int key;
	struct _node *prev;
	struct _node *next;
}node;

node *head, *tail;

void init_queue(); // head와 tail 메모리 할당 및 head와 tail의 prev, next 초기화
int put(int k); // Queue에 값을 넣음
int get(); // Queue에서 값을 얻어옴
void clear_queue(); // Queue를 모두 비움
void print_queue(); // Queue의 모든 내용 출력

int main(int argc, char *argv[], char **env)
{
	int i = 0;
	init_queue();

	printf("put 5, 4, 7, 8, 2, 1\n");
	put(5);
	put(4);
	put(7);
	put(8);
	put(2);
	put(1);
	print_queue();
	puts("");

	printf("get\n");
	i = get();
	print_queue();
	printf("getting value is %d\n", i);
	puts("");

	printf("put 3, 2, 5, 7\n");
	put(3);
	put(2);
	put(5);
	put(7);
	print_queue();
	puts("");

	printf("put 3\n");
	put(3);
	print_queue();
	puts("");

	printf("Initailize Queue\n");
	clear_queue();
	print_queue();
	puts("");

	printf("Now queue is empty, get\n");
	i = get();
	print_queue();
	printf("getting value is %d\n", i);

	return 0;
}

void init_queue()
{
	head = (node *)calloc(sizeof(node), 1); // head의 메모리 할당
	tail = (node *)calloc(sizeof(node), 1); // tail의 메모리 할당

	head->prev = head; // head의 prev는 자기자신을 가리키도록 함
	head->next = tail; // head의 next는 tail을 가리키도록 함
	tail->prev = head; // tail의 prev는 head를 가리키도록 함
	tail->next = tail; // tail의 next는 자기자신을 가리키도록 함
}

int put(int k)
{
	node *new_node = NULL;

	new_node = (node *)calloc(sizeof(node), 1); // 새로 추가할 노드 메모리 할당

	new_node->key = k; // 새로 할당한 노드의 key를 매개변수로 받은 k로 초기화

	new_node->next = head->next; // 새로 생성된 노드가 가리키는 다음 노드가 head가 가리키던 다음 노드를 가리키도록 함
	new_node->prev = head; // 새로 생성된 노드가 가리키는 이전 노드가 head를 가리키도록 함
	head->next = new_node; // head가 가리키는 다음 노드가 새로 생성된 노드를 가리키도록 함
	new_node->next->prev = new_node; // 원래 head 노드 다음에 있던 노드가 가리키는 이전 노드가 새로 생성된 노드를 가리키도록 함

	return k;
}

int get()
{
	node *temp_node = NULL;
	int val = 0;

	if(tail->prev == head) // head의 다음 노드가 tail일 경우
	{
		printf("Get failure, Queue is empty...\n");
		return -1;
	}

	temp_node = tail->prev; // 맨 마지막 노드

	val = temp_node->key; // 맨 마지막 노드의 key값을 저장

	temp_node->prev->next = tail; // 마지막 노드의 이전 노드가 가리키는 다음 노드가 tail을 가리키도록 함
	tail->prev = temp_node->prev; // tail의 이전 노드를 가리키는 노드가 마지막 노드의 전 노드를 가리키도록 함

	free(temp_node); // 메모리 해제

	return val;
}

void clear_queue()
{
	node *destroyer = NULL, *seeker = NULL;

	seeker = head->next; // 첫 노드로 초기화

	while(seeker != tail) // tail이 아니면 반복
	{
		destroyer = seeker; // destroyer 변수에 현재 노드로 초기화
		seeker = seeker->next; // seeker는 다음 노드로 넘어감
		free(destroyer); // 현재 노드 메모리 해제
	}

	head->next = tail; // head의 다음 노드를 가리키는 노드를 tail로 초기화
	tail->prev = head; // tail의 이전 노드를 가리키는 노드를 head로 초기화
}

void print_queue()
{
	node *seeker = NULL;

	if(head->next == tail) // head의 다음 노드가 tail이면
	{
		printf("Print failure, Queue is empty...\n");
		return;
	}

	seeker = head->next; // 첫 노드로 초기화

	while(seeker != tail) // tail이 아니면 반복
	{
		printf("%-4d", seeker->key); // 현재 노드의 key 값을 출력
		seeker = seeker->next; // 다음 노드로 넘어감
	}

	puts("");
}