Deque (ADT)

A double-ended queue or deque is simply a combination of a stack and a queue in that items can be inserted or removed from both ends.

Functions

• int size() — Returns how many items are in the deque.
• bool isEmpty() — Returns whether the deque is empty (i.e. size is 0).
• void insertFirst(Object o) — Puts an object $o$ at the front.
• void insertLast(Object o) — Puts an object $o$ at the back.
• Object removeFirst() — Removes the object from the front and returns it.
• Object removeLast() — Removes the object from the back and returns it.
• Object first() — Peeks at the front item without removing it.
• Object last() — Peeks at the back item without removing it.

Implementations

Identical to queue's implementations:

• Fixed/Circular Array
• Growable (Doubling) Array
• Singly-Linked-List. For analysis purposes, we'll assume that the front is the head of the list and the back is the tail of the list.

Analysis

See Amortized Time and Asymptotic Analysis for more information.

	Array (fixed)	Array (doubling)		List
insertFirst()	$O(1)$	worst:	$O(n)$	$O(1)$
		best:	$O(1)$
		avg:	$O(1)$
insertLast()	$O(1)$	worst:	$O(n)$	$O(1)$
		best:	$O(1)$
		avg:	$O(1)$
removeFirst()	$O(1)$	$O(1)$		$O(1)$
removeLast()	$O(1)$	$O(1)$		$O(n)$