A queue is a collection of objects that are inserted and removed according to the first-in, first-out (FIFO) principle.

By convention, we assume that elements added to the queue can have arbitrary type and that a newly created queue is empty.

Queue Interface

public interface Queue<E> {
	int size(a); 
	boolean isEmpty(a); 
	// Inserts an element at the rear of the queue
	void enqueue(E e); 
	// Returns, but does not remove, the first element of the queue (null if empty)
	E first(a);  
	// Removes and returns the first element of the queue (null if empty)
	E dequeue(a); 
}
Copy the code

Array-based Queue Implementation

/* Implementation of the queue ADT using a fixed-length array. */
public class ArrayQueue<E> implements Queue<E> {
	private E[] data; 
	private int f = 0;      // index of the front element
	private int sz = 0;     // current number of elements (size) 

	// constructors 
	public ArrayQueue(a) { this(CAPACITY); } 
	public ArrayQueue(int capacity) {
		data = (E[]) new Object[capacity]; 
	} 

	// methods
	public int size(a) { return sz; } 
	public boolean isEmpty(a) { return (sz == 0); } 

	// insert an element at the rear of the queue 
	public void enqueue(E e) throws IllegalStateException {
		if(sz == data.length) throw new IllegalStateException("Queue is full"); 
		int avail = (f + sz) % data.length; 
		data[avail] = e; 
		sz++; 
	}

	// returns, but does not remove, the first element of the queue (null if empty) 
	public E first(a) {
		if(isEmpty()) return null; 
		return data[f]; 
	} 

	// removes and returns the first element of the queue (null if empty) 
	public E dequeue(a) {
		if(isEmpty()) return null; 
		E answer = data[f]; 
		data[f] = null;        // deference to help garbage collection
		f = (f + 1) % data.length; 
		sz--; 
		returnanswer; }}Copy the code

The enqueue (E, E) analysis

public void enqueue(E e) throws IllegalStateException {
        if(sz == data.length) throw new IllegalStateException("Queue is full"); 
        int avail = (f + sz) % data.length; 
        data[avail] = e; 
        sz++; 
}
Copy the code

New elements can be inserted only if the Queue is not full, that is, sz < data.length. Let’s say f = 11, sz = 10, data.length = 20 and now we’re going to insert a new element E, E, at the end of this Queue.

avail = (11 + 10) % 20    / / 1
data[1] = e;   
sz++;    / / 11
Copy the code

Dequeue () analysis

public E dequeue(a) {
        if(isEmpty()) return null; 
        E answer = data[f]; 
        data[f] = null;        // deference to help garbage collection
        f = (f + 1) % data.length; 
        sz--; 
        return answer; 
}
Copy the code

The range of f is [0, data.length-1]

The advantage of this implementation is that after removing the first element of the Queue, there is no need for a for loop to move all subsequent elements forward one bit, because using a for loop would make the dequeue less efficient.

Implementing A Queue with A Singly Linked List

public class LinkedQueue<E> implements Queue<E> {
	private SinglyLinkedList<E> list = new SinglyLinkedList<>();   // an empty list
	public LinkedQueue(a) {}   // new queue relies on the initially empty list 
	public int size(a) { return list.size(); } 
	public boolean isEmpty(a) { return list.isEmpty(); } 
	public void enqueue(E element) { list.addLast(element); } 
	public E first(a) { return list.first(); } 
	public E dequeue(a) {returnlist.removeFirst(); }}Copy the code

A Circular Queue

To be added