• FIFO : First in, First Out

  • front, rear

  • enqueue()

    • rear = rear + 1
    • rear = 0; if rear == maxQueue - 1

    → rear = (rear + 1) % maxQueue

  • dequeue()

    • front = front + 1
    • front = 0; if front == maxQueue - 1

    → front = (front + 1) % maxQueue

  • Problem

    • Full : front == rear + 1
    • Empty : front == rear + 1

  • Solution

    • reserved space를 두고, front가 항상 reserved space를 가리키게 함
    • Full : rear + 1 = front → (rear+1) % maxQueue == front
    • Empty : rear == front (둘 다 reserved space 가리킴)

  • Initialization

    • reserved space를 queue의 맨 마지막에 두고 시작
    • 어디에나 reserved space를 두어도 됨