Queue: Difference between revisions

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


* [[Data Structures#Queue|Data Structures]]
* [[Data Structures#Queue|Data Structures]]
* [[Stack#Overview|Stack]]
* [[Deque#Overview|Deque]]


=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.
 
=Implementation=
 
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.
 
<syntaxhighlight lang='java'>
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;
  }
}
</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'>
public void enqueue(T e) {
  if (s == a.length) {
    // queue full
    throw new QueueOverflowException();
  }
  a[t] = e;
  t = (t + 1) % a.length;
  s++;
}
</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:
<syntaxhighlight lang='java'>
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;
}
</syntaxhighlight>
 
==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}}


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. Also see [[Stack#Overview|Stack]].
=Miscellaneous=


<font color=darkgray>Difference between list and queue.</font>
* 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.
* Process this: https://github.com/jwasham/coding-interview-university#queue</font>

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