[자료구조] 큐 (Queue)

이번에 알아 볼 자료구조는 큐(Queue)다.

큐 역시 개념은 대충알지만 제대로 알지 못하기 때문에 한번 공부해 보겠다.

 

현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.

---

📌 개념

큐(Queue)도 지금까지 공부했던 데이터 구조처럼 데이터를 한 열로 저장한다.

스택과 비슷하지만, 큐는 추가하는 쪽과 삭제하는 쪽이 반대다.

큐를 대기 행렬이라고도 하는데, 이름이 의미하듯 줄을 서는 행렬과 비슷하다. 새로운 사람은 마지막에 서고, 먼저 온 사람 순서대로 처리된다.

큐의 개념도

큐의 개념도 이다. 현재 Red라는 데이터만 큐에 저장되어 있다.

 

데이터 추가

큐에 데이터를 추가하는 작업을 인큐(enqueue)라고 한다.

인큐

왼쪽부터 Blue를 추가하고 Yellow가 추가되었다.

 

데이터 제거

큐에서 데이터를 꺼내는 것을 디큐(dequeue)라고 한다.

디큐

큐에서 데이터를 꺼낼 때는 가장 먼저 추가된 데이터부터 꺼낸다.

그래서 왼쪽부터 살펴보면 가장 먼저 들어가있던 Red를 꺼내고 다음 Blue가 빠져나왔다.

 

데이터 접근

큐는 선입선출 구조로 First In First Out, 줄여서 FIFO라고 부른다

스택과 마찬가지로 중간에 있는 데이터에는 접근할 수 없고, 필요한 데이터가 나올 때까지 디큐해야 한다.

---

📌 추가 내용

오래된 데이터부터 차례로 처리하는 것은 자연스러운 방식이므로, 큐는 폭넓게 활용된다.

이후에 공부할 너비 우선 탐색에서 탐색 후보 중에 항상 가장 오래된 것을 선택해야 하기 때문에 큐를 사용한다.

 

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠

 

---

📝 큐(Queue) 관련 문제

[C#][프로그래머스] 카드 뭉치