#05. 큐(Queue)

큐(Queue)

• FIFO(First In First Out) 구조 : 먼저 넣은 데이터가 먼저 나오는 구조
• 선형 리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조
• 데이터가 삽입(push)되는 곳을 front, 제거(pop)되는 곳을 back이라고 한다.

 

• front 포인터 : 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터 (삭제 작업에 사용)
• rear 포인터 : 가장 마지막에 삽입된 자료가 위치한 기억 공간을 가리키는 포인터 (삽입 작업에 사용)

 

장점

• 데이터의 삽입과 삭제가 빠르다.

단점

• 큐(Queue)의 중간에 위치한 데이터로의 접근이 어렵다.

 

사용

• 데이터를 입력된 순서대로 처리해야 할 때
• BFS(너비 우선 탐색), Flood Fill
• ex) BFS 문제, 콜센터 대기 순서, 프로세스 관리

---

대표적인 큐의 기능

• push (enqueue) : 큐에 자료를 넣는다.

void enqueue(int value) {
	if (IsFull())
		printf("Queue is Full.\n");
	else {
		rear = (rear + 1) % MAX;
		queue[rear] = value;
	}
}

 

• pop (dequeue) : 큐의 자료를 뺀다.

int dequeue() {
	if (IsEmpty())
		printf("Queue is Empty.\n");
	else {
		front = (front + 1) % MAX;
		return queue[front];
	}
}

 

• front : 큐의 가장 처음 자료를 가리킨다.

int queue_getfront() {

	return queue[front + 1];

}

 

• back : 큐의 가장 마지막 자료를 가리킨다.

int back() {

	return queue[end - 1];
    
}

 

• empty (IsEmpty) : 큐가 비어있는지 여부를 알려준다.

bool IsEmpty(void) {
	if (front == rear)  //front와 rear가 같으면 큐는 비어있는 상태 
		return true;
	else 
		return false;
}

 

• IsFull : 큐가 꽉 차 있는지 여부를 알려준다.

bool IsFull(void) {
	int tmp = (rear + 1) % MAX;   //원형 큐에서 rear+1을 MAX로 나눈 나머지값이
	if (tmp == front)  //front와 같으면 큐는 가득차 있는 상태 
		return true;
	else
		return false;
}

 

• size : 큐의 크기를 알려준다.

int size() {

	return end - begin;
    
}

---

원형 큐(Circle Queue)

메모리 공간은 잘 활용하나 배열롤 구현되어 있기 때문에 큐의 크기가 제한된다.

 

 

Linked list queue

큐의 크기가 제한이 없고, 삽입/삭제가 편리하다.

---

References

 

velog.io/@kongsub/%ED%81%90Queue-%EB%8D%B1Deque

큐(Queue) / 덱(Deque)

chanhuiseok.github.io/posts/algo-26/

알고리즘 - 큐(Queue) : 선형 큐와 원형 큐

m.blog.naver.com/justkukaro/220510730704

05-자료구조: 큐(Queue)

minimin2.tistory.com/9

[자료구조] C언어로 큐(Queue) , 원형 큐(Circular Queue) 구현, 소스코드

m.blog.naver.com/nabilera1/222062019192

C언어 알고리즘 입문:: Queue 큐 (환형큐, STL 라이브러리 활용 등)

reakwon.tistory.com/30

[자료구조] 큐(Queue)와 원형큐(Circular Queue) 개념과 구현