1. What is Queue?

• front 랑 rear를 통해 구성 됨.

• FIFO → First In, First Out

  → Stack이 후입선출인 것과 다르게 Queue는 선입선출!!

2. Operations

• dequeue()
• clear() (or flush()) | $O(1)$ | | Observer (Observe data) | - isFull()
• isEmpty() | $O(1)$ |

3. Queue Design Considerations

3-1. Option 1

Problem : Dequeue의 시간 복잡도 → O(n)

3-2. Option 2 - Circular queue

• 뒤에 공간 다 차면 앞 공간부터 다시 채움
• enque() → rear == maxQueue-1 ? rear +=1 : rear =0;

Problem: Full과 Empty를 검사하는 조건이 모두 front == rear +1로 같음

2-3. Option 3 - Reserved Space

• reserved space를 만들고 front가 항상 이를 가리키도록 함!

  → reserved space를 위한 하나의 메모리가 낭비됨.