Queue Interface

public interface Queue<E> {

  void enqueue(E item);

  E dequeue();

  E peek();

  boolean isEmpty();

  int size();
  
}

Queue Applications

• Queues are ubuiquitous in applications that must connect producers to consumers of data.

Circular Arrays

Some Options for Circular Increment:

    
    // Option A
    index++;
    if (index == array.length) {
      index = 0;
    }
    
    // Option B
    if (index == array.length - 1) {
      index = 0;
    } else {
      index++;
    }
    
    // Option C
    index = (index + 1) % array.length;
    

Dynamic-Array Based AQueue

• Big-$\mathrm{\Theta }$ cost?

  operation	cost
  enqueue()	$\mathrm{\Theta }(1)$*
  dequeue()	$\mathrm{\Theta }(1)$
  frontValue()	$\mathrm{\Theta }(1)$
  length()	$\mathrm{\Theta }(1)$

  * Amortized

Linked Queue

• Issue for you to consider:
  • Should the front of the queue be at the head of the list?
  • Should it be at the tail of the list? Does it matter?

Linked Queue

• Big-$\mathrm{\Theta }$ cost?

  operation	cost
  enqueue()	$\mathrm{\Theta }(1)$
  dequeue()	$\mathrm{\Theta }(1)$
  frontValue()	$\mathrm{\Theta }(1)$
  length()	$\mathrm{\Theta }(1)$