Queue Interface

• OpenDSA version:

  public interface Queue<E> { // Queue class ADT
    // Reinitialize queue
    public void clear();
  
    // Put element on rear
    public boolean enqueue(E it);
  
    // Remove and return element from front
    public E dequeue();
  
    // Return front element
    public E frontValue();
  
    // Return queue size
    public int length();
  
    //Tell if the queue is empty or not
    public boolean isEmpty();
  }

Warm-up question

• What will be printed when this code executes:

  Queue<String> queue = new LQueue<>();
  
  queue.enqueue("A");
  queue.enqueue("B");
  queue.enqueue("C");
  queue.dequeue();
  queue.enqueue("D");
  
  while (queue.length() != 0) {
    System.out.println(queue.dequeue());
  }

Queue Applications

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

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;
    

Let’s take a Look at AQueue…

Dynamic-Array Based AQueue

• Big-\(\Theta\) cost?

  operation	cost
  enqueue()
  dequeue()
  frontValue()
  length()

Dynamic-Array Based AQueue

• Big-\(\Theta\) cost?

  operation	cost
  enqueue()	\(\Theta(1)\)*
  dequeue()	\(\Theta(1)\)
  frontValue()	\(\Theta(1)\)
  length()	\(\Theta(1)\)

  * Amortized

Linked Queue Socrative Question

Which of the following describes the most reasonable organization of a linked queue?

1. enequeue and dequeue are performed at the head. There is no need to maintain a tail reference.

2. enequeue is performed at the tail. dequeue is performed at the head.

3. enequeue is performed at the head. dequeue is performed at the tail.

4. Both a head and tail reference are required, but it doesn’t matter which is used for enequeue and which is used for dequeue.

Linked Queue

• Big-\(\Theta\) cost?

  operation	cost
  enqueue()
  dequeue()
  frontValue()
  length()

Linked Queue

• Big-\(\Theta\) cost?

  operation	cost
  enqueue()	\(\Theta(1)\)
  dequeue()	\(\Theta(1)\)
  frontValue()	\(\Theta(1)\)
  length()	\(\Theta(1)\)