공부하는 식빵맘 👱‍♀️

공부하는 식빵맘 👱‍♀️

반갑습니다 :)

Chater 5-1 배열로 원형 큐 구현하기

Date:     Updated:

카테고리:

태그:

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

Chapter 5. 큐

🚀 Queue 란?

  • 스택 👉 먼저 들어온게 가장 늦게 나간다. (Last In First Out)
  • 큐 👉 먼저 들어온게 가장 먼저 나간다. (First In First Out)
    • 들어온게 가장 뒤에 가고
    • 가장 앞에 있는게 제일 먼저 삭제되기 떄문에
    • top만 필요하던 스택과 달리, first, last 두 인덱스를 추적해야 한다.


🔥 큐의 구현

맨 앞 원소가 삭제될 때마다 뒤에 있는 원소들을 한 칸씩 모두 땡기는 작업을 매번 한다는 것은 매우 부담스러운 일이 될 것이다. 그래서 큐는 보통 "순환 큐" 구조로 구현된다. (큐가 원형인 것처럼 프로그래밍) 👉 싸그리 한 칸씩 앞으로 땡길 필요가 없음.

image


🚀 배열로 원형 큐 구현하기

image

image

image

image

1차원 배열을 원형으로 돌기 위해(순환하기 위해) 나머지 연산자 사용!

image

  • 비어있을 때 👉 Front == Rear 상태
  • 꽉 차 있을 때 👉 Front == (Rear + 1) % MAX_SIZE
    • 꽉 차 있을 때도 Front == Rear 이진 않다. 비어있을 때만 Front == Rear 가 되도록 구분할 것이기 때문에.
    • MAX_SIZE 보다 1 작은 개수의 원소들이 있을 때만 꽉찬 상태라고 판정할 것


📜ArrayQueue.h

#pragma once

#include <stdbool.h>

#define TSIZE 45
#define MAXSIZE 4 // MAXSIZE - 1 을 꽉찬 상태라고 볼 것!

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

typedef struct queue
{
	int front; // 큐의 첫번째 원소 위치
	int rear;  // 큐의 마지막 원소 위치
	int n_items;
	Item items[MAXSIZE];
} 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));


📜ArrayQueue.c

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

bool QueueIsFull(const Queue* pq)
{
	return (pq->rear + 1) % MAXSIZE == pq->front;
}

bool QueueIsEmpty(const Queue* pq)
{
	return pq->front == pq->rear;
}

int QueueItemCount(const Queue* pq)
{
	return pq->n_items;
}

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

	pq->rear = (pq->rear + 1) % MAXSIZE;
	pq->items[pq->rear] = item;
	pq->n_items++;

	return true;
}

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

	pq->front = (pq->front + 1) % MAXSIZE;
	*pitem = pq -> items[pq->front];
	pq->n_items--;
}

void EmptyTheQueue(Queue* pq)
{
	InitializeQueue(pq);
}

void TraverseQueue(Queue* pq, void (*func)(Item item))
{
	// i < pq->rear 가 아닌 i != pq->rear 인 것에 주의! 순환구조라 front 가 rear 을 초과할 때도 있기 때문이다.
	for (int i = pq->front; i != pq->rear; i = (i + 1) % MAXSIZE)
		(*func)(pq->items[(i + 1) % MAXSIZE]);
}


📜main.c

#include <stdio.h>
#include <string.h>
#include "ArrayQueue.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: %d, Rear: %d, Size %d\n", pq->front, 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(".......Circulation 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: 0, Rear: 1, Size 1
Queue : Jack

Front: 0, Rear: 2, Size 2
Queue : Jack Henry

Front: 0, Rear: 3, Size 3
Queue : Jack Henry Stan

Queue is full. Cannot enqueue.
Front: 0, Rear: 3, Size 3
Queue : Jack Henry Stan

Item from queue: Jack
Front: 1, Rear: 3, Size 2
Queue : Henry Stan

Item from queue: Henry
Front: 2, Rear: 3, Size 1
Queue : Stan

Item from queue: Stan
Front: 3, Rear: 3, Size 0
Queue : Empty

Queue is empty. Cannot enqueue.
Front: 3, Rear: 3, Size 0
Queue : Empty

.......Circulation Test........
Front: 0, Rear: 1, Size 1
Queue : Hello

Item from queue: Hello
Front: 1, Rear: 1, Size 0
Queue : Empty

Front: 1, Rear: 2, Size 1
Queue : Hello

Item from queue: Hello
Front: 2, Rear: 2, Size 0
Queue : Empty

Front: 2, Rear: 3, Size 1
Queue : Hello

Item from queue: Hello
Front: 3, Rear: 3, Size 0
Queue : Empty

Front: 3, Rear: 0, Size 1
Queue : Hello

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

Front: 0, Rear: 1, Size 1
Queue : Hello

Item from queue: Hello
Front: 1, Rear: 1, Size 0
Queue : Empty

Front: 1, Rear: 2, Size 1
Queue : Hello

Item from queue: Hello
Front: 2, Rear: 2, Size 0
Queue : Empty

Front: 2, Rear: 3, Size 1
Queue : Hello

Item from queue: Hello
Front: 3, Rear: 3, Size 0
Queue : Empty

Front: 3, Rear: 0, Size 1
Queue : Hello

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

Front: 0, Rear: 1, Size 1
Queue : Hello

Item from queue: Hello
Front: 1, Rear: 1, Size 0
Queue : Empty

Front: 1, Rear: 2, Size 1
Queue : Hello

Item from queue: Hello
Front: 2, Rear: 2, Size 0
Queue : Empty



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

맨 위로 이동하기

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

댓글 남기기

최근 글 10 개 :)