[자료구조] Queue

✅ 큐 (Queue)

❕ 기본 개념 

- 데이터를 1열로 나열하는 데이터 구조

- 스택과 비슷하지만, 큐는 데이터를 추가하는 쪽과 삭제하는 쪽이 서로 반대쪽에 위치함

- "대기 행렬"이라고 생각하면 됨. 데이터가 줄 서 있는 행렬 ☜ 게임할 때 "큐가 왜이리 안 잡혀"할 때 쓰는 그 큐

- 먼저 넣은 것을 먼저 꺼내는 First In First Out (FIFO) 구조

- 스택과 마찬가지로 데이터를 조작할 수 있는 위치가 정해져 있음

- 중간에 있는 데이터에 indexing으로 접근할 수 없으며, 필요한 데이터가 나올 때까지 dequeue를 해야함

 

 

Stack vs. Queue

 

 

❕ 작동 방식 

- 큐에 데이터를 추가하는 작업을 enqueue, 데이터를 꺼내는 작업은 dequeue라고 함

- 큐의 가장 앞에서부터 차례대로 데이터가 추가됨 (push)

- 큐에서 데이터를 꺼낼 때는 가장 앞, 즉 가장 오래된 데이터부터 꺼냄

- front는 큐의 삭제가 발생하는 지점, rear는 큐의 삽입이 발생하는 지점

- 데이터 삽입 시 rear를 증가시키고, 삭제 시 front를 감소시킴

 

 

✔ 활용 예시 

오래된 데이터부터 순서대로 처리하는 방식은 쓰일 데가 많으므로, 큐는 폭넓게 활용되고 있다.

 

- 프린터 인쇄 대기열

- 컴퓨터 운영체제의 태스크 스케쥴링

- 너비 우선 탐색(BFS)에서는 탐색 후보 중에 항상 가장 오래된 것을 선택하므로 후보 관리에 큐 활용

 

 

 

참고자료

「알고리즘 도감」 中 1-5 큐

https://colab.research.google.com/drive/1ufsEvPZovKdUcW-_-4-VkbfBjAFRGzJv

https://www.faceprep.in/data-structures/types-of-queue-data-structure/

https://atoz-develop.tistory.com/entry/자료구조-큐-정리-및-연습문제