Очередь или Queue

Еще одним абстрактным простым типом данных есть Очередь/Queue.

Очередь реализует принцып первый вошел первый вышел (FIFO - first in first out). Каждый из вас уже видел очередь в своей жизни, когда стоял за билетами в кино или теарт. Очередь имеет голову(head) и хвост(tail), которые соответственно есть люди в начале очереди и в конце. Самый первый человек в очереди уйдет первым, последний - соответственно последним)).

Далее я покажу, как реализовать Очередь/Queue с помощью языка программирования Java, и с помощью массива размером n. Класс будет обладать аттрибутами head, который является индексом головного элемента, tail - индекс местоположения, куда будет вставлятся новый элемент. При выполнении условия queue.tail == queue.head - очередь пуста. При выполнении условия queue.head == queue.tail + 1, или же  если queue.head = 0 и queue.tail = queue.size, то очередь переполнена, что должно возвратить исключение или ошибку. queue.size - максимальное количество элементов очереди.

Так же Очередь содержит два метода, один для вставки, другой для удаления(enqueue и dequeue соответственно).

Пример на Java:

package adt;

public class Queue {
	private int[] elements;
	private int size;
	private int head;
	private int tail;
	
	public Queue(int size) {
		this.size = size;
		this.elements = new int[size];
		this.head = 0;
		this.tail = 0;
	}
	
	public void enqueue(int x) {
		if ((this.head == this.tail + 1) || (this.head == 0 && this.tail == this.size)) {
			throw new ArrayIndexOutOfBoundsException("Queue is full");
		}
		this.elements[this.tail] = x;
		if (this.tail == this.size) {
			this.tail = 0;
		} else {
			this.tail++;
		}
	}
	
	public int dequeue() {
		if (this.head == this.tail) {
			throw new IllegalArgumentException("Can't handle zero-length arrays.");
		}
		int x = this.elements[this.head];
		this.elements[this.head] = 0;
		if (this.head == this.size) {
			this.head = 0;
		} else {
			this.head++;
		}
		
		return x;
	}
}

Пример использования:

package adt;
import adt.Queue;;

public class QueueTest {
	public static void main (String args[]) {
		Queue q = new Queue(5);
		q.enqueue(1);
		q.enqueue(2);
		q.enqueue(3);
		q.dequeue();
		q.dequeue();
		q.dequeue();
		q.dequeue();
	}
}
LikeMe: