Queue ADT

Definition

• rear(back)에서 Enqueue, front에서 Dequeue가 일어나는 ordered list.

Properties

• FIFO scheme
• Typically implemented with array or LL

Methods

Main

• enqueue(Object) from rear
• Object dequeue() from front

Others

• Object peek()
• int size()
• boolean isEpmty()

Array based Queue

• Problem : 큐가 꽉찬 게 아닌데 insertion 불가.
  -> Circular array of size n.
• when f < r ... normal configuration.
• when f > r ... Wrapped-around configuration.
• size : return (N - f + r) mod N
• isEmpty() : return (size() == 0)

Performance

• Space complexity : O(n)
• Time complexity of all operations : O(1)

Limitations

• array로 구현했다 -> 사이즈 선제 선언 및 변경 불가.
• full queue에 새 원소 추가 -> 예외 발생.
• LL로 구현하는 게 더 바람직할 수도 있다.

Applications of Queue

Direct applications

• Waiting lists.
• Access to shared resources. (e.g., printer)
• Multiprogramming.
• Round Robin Schedulers

Indirect applications

• Auxiliary data structure for algorithms.
• Component of other data structures.

Recursion

Definition

• Divide a problem into a subproblem of the same type.
• Recursive function : a method (function) calling itself.

Properties

• loop is typically faster since it involves less system overhead.
• By tail recursion, we can reduce system overhead.

Binary Recursion

• linear recursion : 한 번에 한 개의 recursive call for each non-base case.
• binary recursion : 한 번에 두 개의 recursive calls for each non-base case.