Queue: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(24 intermediate revisions by the same user not shown)
Line 6: Line 6:


=Overview=
=Overview=
A '''queue''' is a [[Data_Structures#Dynamic_Set|dynamic set]] whose [[Data Structures#DELETE|DELETE]] operation, which does not have any argument, removes the oldest element in the queue. The queue implements the '''first-in-first-out''', or FIFO, policy. The queue has a head and a tail. The INSERT operation for a queue is called ENQUEUE and places the new element at the tail. The DELETE operation is called DEQUEUE, and has no argument. It simply returns the element at the head of the queue, if any. If we attempt to dequeue an element from an empty queue, it is said that the queue underflows. If we attempt to enqueue an element on a full queue, it is said that the queue overflows.


=Overview=
The queue is an essential component in implementing the [[Graph_Search#BFS_Algorithm_Pseudocode|Breadth-First Search (BFS)]] algorithm in graphs.
 
A '''queue''' is a [[Data_Structures#Dynamic_Set|dynamic set]] in which the the [[Data Structures#DELETE|DELETE]] operation, which does not have any argument, removes the oldest element in the queue. The queue implements the ''first-in-first-out'', or FIFO, policy. The queue has a '''head''' and a '''tail'''. The INSERT operation for a queue is called '''ENQUEUE''' and places the new element at the tail. The DELETE operation is called '''DEQUEUE''', and has no argument. It simply returns the element at the head of the queue, if any. If we attempt to dequeue an element from an empty queue, it is said that the queue '''underflows'''. If we attempt to enqueue an element on a full queue, it is said that the queue '''overflows'''.
 
[[File:QueueWithArray.png]]


=Implementation=
=Implementation=


The following implementation uses an array, which dictates the queue length. The queue grows circularly and wraps around the edge of the array as the data is enqueued and dequeued. We use to pointers, "head" and "tail", containing the indexes of the corresponding head and tail elements. The "head" pointer indicates the head element - the one that will be dequeued next, while "tail" points to the position where the next enqueued element will be placed.  
The implementation maintains the content into an n element array <code>a</code>, which establishes the queue capacity. We also maintain two variables: the current size of the queue as <code>s</code>, and the position where to insert a new element as <code>t</code> or "tail". Both are initialized to 0.


An empty queue is indicated by the fact that the "head" and the "tail" pointers have the same value.
<syntaxhighlight lang='java'>
 
public class Queue<T> {
We have two choices when it comes to model a full queue. If we want to use all the n elements in the array for queue element storage, then we model the "full" position with an external boolean, because otherwise there would be no way to distinguish the "empty queue" head and tail overlap and "full queue" head and tail overlap. Another possibility is to use only n - 1 elements of the array for queue element storage, and use one array element as a "marker" that always separates the head from the tail. This way, the "head" and "tail" pointers never overlap for a full queue, just for an empty queue.
  private final Object[] a;
 
  private int s; // size
The equivalent implementations are presented below:
  private int t; // tail, the index of the location where to insert next element
 
==n element Queue==
 
We model "full" and "empty" by allowing the "head" and "tail" markers to overlap, and we maintain an extra bit of data that tells those states apart. This way we can use all n array elements for queue element storage.


  public Queue(int capacity) {
    this.a = new Object[capacity];
    this.s = 0;
    this.t = 0;
  }
}
</syntaxhighlight>
Enqueueing verifies whether the queue still has capacity, and if it does, stores the element on position <code>t</code>, advances the tail with one position, wrapping around if necessary, and updates the size <code>s</code>.
<syntaxhighlight lang='java'>
<syntaxhighlight lang='java'>
/**
public void enqueue(T e) {
* A queue of ints that uses all n storage elements for queue element storage.
  if (s == a.length) {
* It needs an additional boolean variable to maintain whether the queue is
    // queue full
* full or not.
     throw new QueueOverflowException();
*/
  }
public class Queue {
  a[t] = e;
 
  t = (t + 1) % a.length;
    private int[] storage;
  s++;
 
    // this is the index of the queue head element
    private int head;
 
    // this is the index of the element where the tail *would* go
    private int tail;
 
    private boolean full;
 
    public Queue(int capacity) {
 
        this.storage = new int[capacity];
        this.head = 0;
        this.tail = 0;
        this.full = false;
    }
 
    public void enqueue(int i) throws QueueOverflowException {
 
        //
        // check if the queue is full
        //
 
        if (full) {
 
            throw new QueueOverflowException();
        }
 
        storage[tail] = i;
 
        tail = (tail + 1) % storage.length;
 
        //
        // this is the only time we can determine the queue is full
        //
 
        if (head == tail) {
 
            this.full = true;
        }
     }
 
    public int dequeue() throws QueueUnderflowException {
 
        if (head == tail && !full) {
 
            throw new QueueUnderflowException();
        }
 
        int result = storage[head];
 
        head = (head + 1) % storage.length;
 
        full = false;
 
        return result;
    }
 
    public boolean isEmpty() {
 
        return head == tail;
    }
 
    public boolean isFull() {
 
        return full;
    }
}
}
</syntaxhighlight>
</syntaxhighlight>
 
Dequeueing verifies whether the queue has elements, and if it does, computes the head of the queue from <code>t</code> and <code>s</code>, wrapping around if necessary, saves the element, updates the size and returns the element:
==n-1 element Queue==
 
We model by allowing the "head" and "tail" markers to overlap, and the full queue will always have a gap between head and tail. This way we can use only n-1 array elements for queue element storage.
 
<syntaxhighlight lang='java'>
<syntaxhighlight lang='java'>
/**
public T dequeue() {
* A queue of ints that uses just n-1 storage elements for queue element storage, and
  if (s == 0) {
* it can tell when it is full without maintaining an additional boolean variable.
     // queue empty
*/
     throw new QueueUndeflowException();
public class Queue {
  }
 
  // compute head
    private int[] storage;
  int h = (a.length + t - s) % a.length;
 
  T e = (T)a[h];
     // this is the index of the queue head element
  s--; // update size
     private int head;
  return e;
 
}
    // this is the index of the element where the tail *would* go
</syntaxhighlight>
    private int tail;
 
    public Queue(int capacity) {
 
        this.storage = new int[capacity];
        this.head = 0;
        this.tail = 0;
    }
 
    public void enqueue(int i) throws QueueOverflowException {
 
        //
        // verify whether by enqueueing this element the tail will overlap with the head
        // if they do, it means the queue is full
        //
 
        if ((tail + 1) % storage.length == head) {
 
            throw new QueueOverflowException();
        }
 
        storage[tail] = i;
 
        tail = (tail + 1) % storage.length;
    }
 
    public int dequeue() throws QueueUnderflowException {


        if (head == tail) {
==Playground Implementation==
{{External|https://github.com/ovidiuf/playground/blob/master/algorithms/graphs/adjacency-list/src/main/java/playground/graphs/adj/Q.java}}
==Alternative Implementations==
Alternative implementations that keep track of head and the tail explicitly, instead of size and tail, are provided below:
{{Internal|Queue Alternative Implementations#Overview|Queue Alternative Implementations}}


            throw new QueueUnderflowException();
=Miscellaneous=
        }


        int result = storage[head];
* Example of a queue implemented using two stacks: [https://github.com/NovaOrdis/playground/blob/master/data-structures-and-algorithms/data-structures/queue-using-two-stacks/src/main/java/playground/dsa/queueUsingTwoStacks/QueueUsingTwoStacks.java Playground - Queue implemented with Two Stacks]
 
* <font color=darkkhaki>TODO Example of a stack implemented using two queues. [[CLRS]] page 236.
        head = (head + 1) % storage.length;
* Process this: https://github.com/jwasham/coding-interview-university#queue</font>
 
        return result;
    }
 
    public boolean isEmpty() {
 
        return head == tail;
    }
 
    public boolean isFull() {
 
        return (tail + 1) % storage.length == head;
    }
}
</syntaxhighlight>

Latest revision as of 00:01, 10 November 2021

Internal

Overview

A queue is a dynamic set whose DELETE operation, which does not have any argument, removes the oldest element in the queue. The queue implements the first-in-first-out, or FIFO, policy. The queue has a head and a tail. The INSERT operation for a queue is called ENQUEUE and places the new element at the tail. The DELETE operation is called DEQUEUE, and has no argument. It simply returns the element at the head of the queue, if any. If we attempt to dequeue an element from an empty queue, it is said that the queue underflows. If we attempt to enqueue an element on a full queue, it is said that the queue overflows.

The queue is an essential component in implementing the Breadth-First Search (BFS) algorithm in graphs.

Implementation

The implementation maintains the content into an n element array a, which establishes the queue capacity. We also maintain two variables: the current size of the queue as s, and the position where to insert a new element as t or "tail". Both are initialized to 0. 

public class Queue<T> {
  private final Object[] a;
  private int s; // size
  private int t; // tail, the index of the location where to insert next element

  public Queue(int capacity) {
    this.a = new Object[capacity];
    this.s = 0;
    this.t = 0;
  }
}

Enqueueing verifies whether the queue still has capacity, and if it does, stores the element on position t, advances the tail with one position, wrapping around if necessary, and updates the size s. 

public void enqueue(T e) {
  if (s == a.length) {
    // queue full
    throw new QueueOverflowException();
  }
  a[t] = e;
  t = (t + 1) % a.length;
  s++;
}

Dequeueing verifies whether the queue has elements, and if it does, computes the head of the queue from t and s, wrapping around if necessary, saves the element, updates the size and returns the element: 

public T dequeue() {
  if (s == 0) {
    // queue empty
    throw new QueueUndeflowException();
  }
  // compute head
  int h = (a.length + t - s) % a.length;
  T e = (T)a[h];
  s--; // update size
  return e;
}

Playground Implementation

https://github.com/ovidiuf/playground/blob/master/algorithms/graphs/adjacency-list/src/main/java/playground/graphs/adj/Q.java

Alternative Implementations

Alternative implementations that keep track of head and the tail explicitly, instead of size and tail, are provided below:

Queue Alternative Implementations

Miscellaneous

Retrieved from "https://kb.novaordis.com/index.php?title=Queue&oldid=85726"