3-1. 큐란?

큐란?

영어 사전에 queue를 검색해보면 "대기열"이라는  뜻으로 나온다.

큐를 생각할 때는 놀이공원의 대기열이나 맛집의 대기 번호표를 생각하면 된다.

놀이공원에서는 먼저 줄을 선 사람이 먼저 놀이기구를 탈 것이다.

맛집에서 번호표를 받고 기다릴 때는 먼저 온 사람이 빠른 대기 번호를 받고, 먼저 불려질 것이다.

즉, 먼저 온 사람이 먼저 무언가를 하게 되는 구조인 것이다.

이것이 큐의 특징인 선입선출(FIFO, First-In First-Out)이다.

 

큐는 가장 먼저 입력된 데이터가 먼저 삭제되는 구조를 가지고 있다.

입출력이 항상 같은 위치(스택의 최상단)에서만 일어나는 스택과 달리, 큐는 입력과 출력의 위치가 다르다.

 

위 그림처럼 큐에서의 입력은 후단(rear)에서 일어나고 출력은 전단(front)에서 일어난다.

큐의 활용 예

• 컴퓨터 장치들 사이에서 데이터를 주고받을 때 사용되는 임시 기억 장치 버퍼(buffer)
• 프로세스 스케쥴링
• 이벤트 처리

등 많은 곳에서 큐가 사용된다.

---

큐의 ADT

• 데이터 : 선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모음
• 연산
  • enqueue(x) : 큐가 꽉 차지 않았다면 전달받은 x를 큐의 맨 뒤에 추가한다.
  • dequeue() : 큐가 비어있지 않으면 큐 맨 앞 요소를 삭제하고 반환한다.
  • peek() : 큐가 비어있지 않으면 큐 맨 앞 요소를 삭제하지 않고 반환만 한다.
  • isEmpty() : 큐가 비어있으면 true를 그렇지 않다면 false를 반환한다.
  • isFull() : 큐가 꽉 찼다면 true를 그렇지 않다면 false를 반환한다.
  • size() : 큐의 모든 요소들의 개수를 반환한다.
  • display() : 큐의 모든 요소들을 출력한다.