DS Lec.7 - Queue

Queue

• FIFO scheme
• array나 linked list로 구현한다.
• front에서 deque(좌측), back(rear)에서 enque(우측)

Operations

• Main
  • enqueue(Object) : rear(우측)에 추가
  • Object dequeue() : front에서 원소 삭제 및 리턴
• Others
  • Object peek() : 마치 스택의 top()과 같다. 삭제없이 front 원소를 리턴한다.
  • int size()
  • boolean isEmpty()

Array-based Queue

• front (f) : index of the front element
• rear (r) : index immediatly past the rear element

problem : 꽉 찬게 아닌데 insertion 불가

why? 계속 enqueue할 때마다 r은 우측으로 이동하기 때문. 그러다가 중간 중간 deque가 발생한다면 f 역시 우측으로 이동한다. 결국 r이 배열의 끝에 도착했을 때, f index의 좌측에 공간이 있음에도 r index가 끝에 도달해서 FullQueueException을 던지게 되는 것이다.

따라서, 이를 해결하기 위해 circular array of size n을 사용한다.

• Normal configuration : f < r
• Wrapped-around cofiguration : r < f

Queue Interface in JAVA

• Restrictions
  • dequeue() and peek() on an empty queue throws an EmptyQueueException().
  • The execution of enqueue() on a full queue throws an FullQueueException().

Queue operations

Circular array with modulo(%) operator

Algorithm size()
	if r >= f:
    	return r - f
   	else:
    	return N - (f - r)

위 두 경우를 모두 포함한 식이 아래이다.

return (N - f + r) % N

Algorithm isEmpty()
	return f == r -> 	
    or
    return size() == 0

Array-based Queue

• Performance : n - 원소 갯수
• 공간복잡도 : O(n)
• 시간복잡도 of all operations : O(1)

Limitations

• 배열이니까 사이즈가 사전에 정의되어야 하며, 바꿀 수 없다.
• full queue에 enqueue하려고 하면 예외 발생
• LL로 구현하는 게 더 바람직하다.