큐(Queue)

C언어를 기반으로 자료구조에서의 큐에 대해 정리해보려한다.

Queue란?

큐는 데이터의 삽입과 삭제를 특정 규칙에 따라 처리하는 자료구조이고, 데이터가 먼저 들어온 순서대로 처리되는 FIFO (First-In-First-Out) 방식으로 동작한다.

---

Queue의 용어

• Front : Queue에서 Item이 삭제되는 위치를 가리키는 포인터
• Rear : Queue에서 Item이 삽입되는 위치를 가리키는 포인터
• EnQueue : Queue의 Rear부분에 Item을 삽입함
• DeQueue : Queue의 Front부분에 Item을 삭제함

---

Queue의 기능 구현

• InitQueue: Queue를 초기화 시킴
• IsFull: Queue가 가득차 있는지 확인함
• IsEmpty: Queue가 비어있는지 확인함
• Peek: Front의 Item을 반환함
• EnQueue: Queue의 Rear부분에 Item을 삽입함
• DeQueue: Queue의 Front부분에 Item을 삭제함

---

Queue의 기능 구현 코드

Queue 구현 코드

#define max_queue 100

typedef struct {
	int front, rear;
	int items[max_queue];
}queue;

InitQueue 함수 구현 코드

void InitQueue(queue* pqueue){
	pqueue->front = pqueue-> rear = 0;
}

IsFull 함수 구현 코드

bool IsFull(queue* pqueue){
	return pqueue->front == (pqueue->rear+1)%max_queue;
}

IsEmpty 함수 구현 코드

bool IsEmpty(queue* pqueue){
	return pqueue->front == pqueue->rear;
}

Peek 함수 구현 코드

int Peek(queue* pqueue){
	if(IsEmpty(pqueue)) exit(1);
	return pqueue->items[pqueue->front];
}

EnQueue 함수 구현 코드

void EnQueue(queue* pqueue, int item){
	if(IsFull(pqueue)) exit(1);
	pqueue->items[pqueue->rear]= item;
	pqueue->rear = (pqueue->rear+1) % max_queue;
}

DeQueue 함수 구현 코드

void DeQueue(queue* pqueue){
	if(IsEmpty(pqueue)) exit(1);
	pqueue->front = (pqueue->front+1)% max_queue;
}

---

Queue의 시간 복잡도

Queue	탐색	삽입	삭제
Big-O	O(n)	O(1)	O(1)

---

느낀점

Queue를 배워보면서 Stack과 달리 Queue는 FIFO 방식으로 동작한다는 것을 새롭게 알게 되었다. Queue는 Linear Queue, Circular Queue을 구현 할 수 있는데, Circular Queue로 구현을 하면 공간의 효율성 측면에서 이점을 가진다는 것을 알게 되었다. Queue는 Stack과 마찬가지로 자료구조에서 중요한 개념이므로 잘 기억해 둬야겠다.