Queues

Queue란?

• first - in first - out(FIFO) 구조를 가진 자료구조 (선입선출, 먼저 들어온 것이 먼저 나감)
  

주요 operations:

• enqueue(o): 마지막 요소인 rear에 새로운 요소를 추가함
• dequeue(): 큐의 시작 요소인 front 삭제

  삭제는 시작 셀에서만, 삽입은 마지막 셀에서만 수행된다.

보조 operations:

front() 시작 요소인 front를 제거 없이 리턴
int size() - 원소 개수(큐의 크기)를 리턴, return = n
bool Empty - 큐가 비었는지를 리턴, return (n=0)

Exceptions

-> 큐가 비었을 때 dequeue(), front()는 QueueEmpty를 리턴

큐의 적용

선형 큐의 단점

선형 큐에서 삽입 및 삭제를 반복하다 보면, rear가 맨 마지막 인덱스를 가리키고, 이를 꽉 찼다고 인식한다.
이를 보완한 것이 환형 배열(circular array, 원형큐)

Array-based Queue
크기가 N인 1차원 배열을 사용
마지막 idx를 넘어가면, 처음 인덱스로 올 수 있도록 % (modular) 연산을 사용한다.
ex. rear = ((rear + 1) % N)