큐(Queue)

큐(Queue)란?

• 새로운 아이템의 추가와 기존의 아이템의 삭제가 다른 끝점에서 일어나는 linear한 자료구조
  • rear: insertion이 일어나는 끝 점
  • front: removal이 일어나는 다른 끝 점
• FIFO(First-In First-Out): 먼저 들어온 것이 먼저 나간다.

• 큐의 구현체는 주로 LinkedList 이다. ⇒ Array-based Queue vs Linked Queue

응용 예

• 그래프의 넓이 우선 탐색(BFS)에서 사용

• CPU threading or multi-tasking scheduling

• 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킴

• printing queue(pool)

• keystrokes

Queue에서의 연산

• queue(): 새로운 큐를 만든다.