Chater 5-2 연결리스트로 큐 구현하기

Date: 2021.03.03 Updated: 2021.03.03

홍정모 교수님의 강의 홍정모의 따라하며 배우는 C언어(부록) 를 듣고 정리한 필기입니다. 😀
ppt 캡처는 모두 교수님 강의에서 캡처한 것임을 밝힙니다.

Chapter 5. 큐

🚀 연결리스트로 큐 구현하기

연결리스트는 삭제 연산시 뒤의 모든 원소들을 앞으로 땡겨올 필요가 없다. 그저 체인만 끊으면 되기 때문에 O(1)의 시작 복잡도를 가진다. 따라서 배열과 달리 연결리스트로 큐를 구현할 땐 원형 큐로, 순환 구조로 구현할 필요가 없다.

📜 LinkedQueue.h

#pragma once

#include <stdbool.h>

#define TSIZE 45
#define MAXITEMS 3 // 연결리스트이기 때문에 Optional (OS가 허락하는 한 연결리스트 크기는 무제한적)

typedef struct element
{
	char name[TSIZE];
} Item;

typedef struct node
{
	Item item;
	struct node* next;	// Single LinkedList
}Node;

typedef struct queue
{
	Node* front; // 큐의 첫번째 원소 위치
	Node* rear;  // 큐의 마지막 원소 위치
	int n_items;
} Queue;

void InitializeQueue(Queue* pq);
bool QueueIsFull(const Queue* pq);
bool QueueIsEmpty(const Queue* pq);
int QueueItemCount(const Queue* pq);
bool EnQueue(Item item, Queue* pq);
bool DeQueue(Item* pitem, Queue* pq);
void EmptyTheQueue(Queue* pq);
void TraverseQueue(Queue* pq, void (*func)(Item item));

📜 LinkedQueue.c

// 📜LinkedQueue.c 안에서만 사용할 수 있는 static 전역 함수
static void CopyToNode(Item item, Node* pn)
{
	pn->item = item;
}

// 📜LinkedQueue.c 안에서만 사용할 수 있는 static 전역 함수
static void CopyToItem(Node* pn, Item* pi)
{
	*pi = pn->item;
}

void InitializeQueue(Queue* pq)
{
	pq->front = NULL;
	pq->rear = NULL;
	pq->n_items = 0;
}

bool QueueIsFull(const Queue* pq)
{
	return pq->n_items == MAXITEMS;
}

bool QueueIsEmpty(const Queue* pq)
{
	return pq->n_items == 0;
}

int QueueItemCount(const Queue* pq)
{
	return pq->n_items; // 순회하며 카운트하기엔 연결리스트는 너무 느리다. O(N)이다. 그래서 n_items 를 저장해두고 이를 리턴하는 것이 효율적
}

bool EnQueue(Item item, Queue* pq)
{
	if (QueueIsFull(pq))
	{
		printf("Queue is full. Cannot enqueue.\n");
		return false;
	}

	Node* pnew;
	pnew = (Node*)malloc(sizeof(Node));
	if (pnew == NULL)
	{
		printf("Malloc() failed.\n");
		return false;
	}
	CopyToNode(item, pnew);
	pnew->next = NULL;

	if (QueueIsEmpty(pq))
		pq->front = pnew;
	else
		pq->rear->next = pnew; // 뒤에 추가
	pq->rear = pnew;

	pq->n_items++;

	return true;
}

bool DeQueue(Item* pitem, Queue* pq)
{
	if (QueueIsEmpty(pq))
	{
		printf("Queue is empty. Cannot enqueue.\n");
		return false;
	}

	Node* pn;
	CopyToItem(pq->front, pitem);

	pn = pq->front; // pq 큐의 맨 앞 노드
	pq->front = pq->front->next;

	free(pn); // 큐는 맨 앞 원소를 삭제 (FIFO)
	pq->n_items--;
	if (pq->n_items == 0)
		pq->rear = NULL;
}

void EmptyTheQueue(Queue* pq)
{
	Item temp;
	while (!QueueIsEmpty(pq))
		DeQueue(&temp, pq);
}

void TraverseQueue(Queue* pq, void (*func)(Item item))
{
	Node* temp = pq->front;
	while (temp != NULL) {
		(*func)(temp->item);
		temp = temp->next;
	}
}

📜 main.c

#include <stdio.h>
#include <string.h>
#include "LinkedQueue.h"

Item get_item(const char* name)
{
	Item new_item;
	strcpy(new_item.name, name);
	return new_item;
}

void print_item(Item item)
{
	printf("%s ", item.name);
}

void print_queue(Queue* pq)
{
	printf("Front: %s at %p, Rear: %s at %p, Size %d\n", 
			pq->front == NULL ? "NULL" : pq->front->item.name, pq->front, 
			pq->rear == NULL ? "NULL" : pq->rear->item.name, pq->rear, pq->n_items);
	
	printf("Queue : ");
	if (QueueIsEmpty(pq))
		printf("Empty");
	else
		TraverseQueue(pq, print_item);
	printf("\n\n");
}

int main()
{
	Queue queue;
	Item temp;

	InitializeQueue(&queue);

	EnQueue(get_item("Jack"), &queue);
	print_queue(&queue);

	EnQueue(get_item("Henry"), &queue);
	print_queue(&queue);

	EnQueue(get_item("Stan"), &queue);
	print_queue(&queue);

	EnQueue(get_item("Butters"), &queue);
	print_queue(&queue);

	if (DeQueue(&temp, &queue))
		printf("Item from queue: %s\n", temp.name);
	print_queue(&queue);

	if (DeQueue(&temp, &queue))
		printf("Item from queue: %s\n", temp.name);
	print_queue(&queue);

	if (DeQueue(&temp, &queue))
		printf("Item from queue: %s\n", temp.name);
	print_queue(&queue);

	if (DeQueue(&temp, &queue))
		printf("Item from queue: %s\n", temp.name);
	print_queue(&queue);


	printf("....... Test........\n");

	InitializeQueue(&queue);

	for (int i = 0; i < 10; ++i)
	{
		EnQueue(get_item("Hello"), &queue);
		print_queue(&queue);

		if (DeQueue(&temp, &queue))
			printf("Item from queue: %s\n", temp.name);
		print_queue(&queue);
	}
}

💎출력💎

Front: Jack at 009B6528, Rear: Jack at 009B6528, Size 1
Queue : Jack

Front: Jack at 009B6528, Rear: Henry at 009B8B18, Size 2
Queue : Jack Henry

Front: Jack at 009B6528, Rear: Stan at 009BC548, Size 3
Queue : Jack Henry Stan

Queue is full. Cannot enqueue.
Front: Jack at 009B6528, Rear: Stan at 009BC548, Size 3
Queue : Jack Henry Stan

Item from queue: Jack
Front: Henry at 009B8B18, Rear: Stan at 009BC548, Size 2
Queue : Henry Stan

Item from queue: Henry
Front: Stan at 009BC548, Rear: Stan at 009BC548, Size 1
Queue : Stan

Item from queue: Stan
Front: NULL at 00000000, Rear: NULL at 00000000, Size 0
Queue : Empty

Queue is empty. Cannot enqueue.
Front: NULL at 00000000, Rear: NULL at 00000000, Size 0
Queue : Empty

.......Circulation Test........
Front: Hello at 009B6528, Rear: Hello at 009B6528, Size 1
Queue : Hello

Item from queue: Hello
Front: NULL at 00000000, Rear: NULL at 00000000, Size 0
Queue : Empty

Front: Hello at 009B6528, Rear: Hello at 009B6528, Size 1
Queue : Hello

Item from queue: Hello
Front: NULL at 00000000, Rear: NULL at 00000000, Size 0
Queue : Empty

Front: Hello at 009B6528, Rear: Hello at 009B6528, Size 1
Queue : Hello

Item from queue: Hello
Front: NULL at 00000000, Rear: NULL at 00000000, Size 0
Queue : Empty

Front: Hello at 009B6528, Rear: Hello at 009B6528, Size 1
Queue : Hello

Item from queue: Hello
Front: NULL at 00000000, Rear: NULL at 00000000, Size 0
Queue : Empty

Front: Hello at 009B6528, Rear: Hello at 009B6528, Size 1
Queue : Hello

Item from queue: Hello
Front: NULL at 00000000, Rear: NULL at 00000000, Size 0
Queue : Empty

Front: Hello at 009B6528, Rear: Hello at 009B6528, Size 1
Queue : Hello

Item from queue: Hello
Front: NULL at 00000000, Rear: NULL at 00000000, Size 0
Queue : Empty

Front: Hello at 009B6528, Rear: Hello at 009B6528, Size 1
Queue : Hello

Item from queue: Hello
Front: NULL at 00000000, Rear: NULL at 00000000, Size 0
Queue : Empty

Front: Hello at 009B6528, Rear: Hello at 009B6528, Size 1
Queue : Hello

Item from queue: Hello
Front: NULL at 00000000, Rear: NULL at 00000000, Size 0
Queue : Empty

Front: Hello at 009B6528, Rear: Hello at 009B6528, Size 1
Queue : Hello

Item from queue: Hello
Front: NULL at 00000000, Rear: NULL at 00000000, Size 0
Queue : Empty

Front: Hello at 009B6528, Rear: Hello at 009B6528, Size 1
Queue : Hello

Item from queue: Hello
Front: NULL at 00000000, Rear: NULL at 00000000, Size 0
Queue : Empty

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️

Chater 5-2 연결리스트로 큐 구현하기

Chapter 5. 큐

🚀 연결리스트로 큐 구현하기

📜 LinkedQueue.h

📜 LinkedQueue.c

📜 main.c

DataStructure2 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)