개요

• 큐는 스택과 다르게 가장 처음에 들어간 데이터가 처음에 나오는 FIFO(First-In First-Out) 자료구조다.
• 삽입이 일어나는 쪽을 뒤(Rear), 삭제가 일어나는 쪽을 앞(Front)라고 한다.
• 프린트 큐, CPU 스케줄링, 데이터 버퍼, BFS 등에 사용된다.
  

추상 자료형

• 스택은 연산에 대해 아래와 같이 동작해야 한다.

1. 읽기(Peek) : 큐의 앞에 위치한 데이터에 접근
2. 삽입(Enqueue) : 큐의 뒤에 데이터를 삽입
3. 삭제(Dequeue) : 큐의 앞에서 데이터를 삭제

• 검색은 굳이 구현하지 않는다.

종류

• 앞과 뒤 모두에서 삽입과 삭제가 가능한 큐를 덱이라고 하고, 앞과 뒤가 연결된 형태를 원형 큐라고 한다.
  

사용법

• C#에서는 Queue로 구현되어 있다.
  

성능

• 각 연산에 대한 성능이다.

1. 읽기 : 앞에 바로 접근할 수 있기 때문에 O(1)
2. 삽입 : 뒤에 바로 삽입하기 때문에 O(1)
3. 삭제 : 앞에서 바로 삭제하기 때문에 O(1)