큐(Queue) - "큐피포"

---

선형 자료 구조에서 종종 비교되는 것이 스택(Stack)과 큐(Queue)입니다.

 

스택은 지난번 포스팅했던 것처럼 LIFO의 특징을 갖고 있는데,

큐는 FIFO의 특징을 갖고 있습니다.

 

또한, 스택은 삽입/삭제가 한곳에서 이루어지는 것에 반해 (Top)

큐는 삽입/삭제하는 곳이 분리되어 있습니다.(Rear, Front)

 

스택은 깊이 우선 탐색(DFS) 구현에 활용될 수 있고,

큐는 너비 우선 탐색(BFS) 구현에 활용 될 수 있습니다.

---

큐(Queue)

 

선형 자료 구조의 하나로, 스택과 달리 삽입되는 곳과 삭제되는 곳이 다른 자료 구조
큐는 뒤에서(Rear) 삽입되고 앞(Front)에서 삭제할 수 있는 구조
FIFO(First Input, First Output) 특징 보유

 

큐의 개념도

 

출처 : 탑싯 에센스

 

스택 또는 큐 문제로 1교시형이 혹 나온다면 

3 단락에 두 개의 자료구조를 비교 정리하면 좋을 듯합니다.

(LIFO vs FIFO, Top vs Rear/Front, DFS / BFS ...)

 

스택과 큐의 연산 비교

 

출처 : 탑싯 에센스

 

기출 문제

 

선형 큐가 갖고 있는 문제점을 해결하는 방안으로 환형 큐가 사용됩니다.

(관리 125-3-1)
배열을 이용하여 큐(Queue)를 구성할 때의 단점과 해결 방법을 설명하시오.

 

(관리 114-1-7)
우선순위 큐(Priority Queue)

 

참고 자료

 

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

[C++] STL Queue 사용법 & 예제 총정리 (tistory.com)

[C++] STL Queue 사용법 & 예제 총정리

 

[알고리즘]C++ BFS 구현하기 (tistory.com)

[알고리즘]C++ BFS 구현하기