TechCodeview

Черга — це інший вид лінійної структури даних, яка використовується для зберігання елементів, як і будь-яка інша структура даних, але певним чином. Простими словами, ми можемо сказати, що черга - це тип структури даних на мові програмування Java, яка зберігає елементи одного виду. Компоненти в черзі зберігаються в режимі FIFO (першим прийшов, першим вийшов). У колекції черги є два кінці, тобто передній і задній. Черга має два кінці: передній і задній.

Наступний малюнок ідеально описує властивість FIFO (First In, First Out) черги Java.

Як пояснено на попередньому зображенні, ми бачимо, що черга — це лінійна структура даних із двома терміналами, тобто початковим (переднім) і кінцевим (заднім). Компоненти додаються всередину черги з заднього кінця черги, а компоненти витягуються з переднього кінця черги.

Черга — це інтерфейс у Java який належить пакету Java.util. Він також розширює інтерфейс колекції.

Загальне представлення інтерфейсу Java Queue показано нижче:

 public interface Queue extends Collection 

Як ми обговорювали вище, черга є інтерфейсом, тому ми також можемо сказати, що чергу не можна створити, оскільки інтерфейси не можуть бути створені. Якщо користувач хоче реалізувати функціональні можливості інтерфейсу черги в Java, то обов’язково мати кілька надійних класів, які реалізують інтерфейс черги.

У мові програмування Java існує два різних класи, які використовуються для реалізації інтерфейсу черги. Ці класи:

• LinkedList
• PriorityQueue

Характеристики Java Queue

Java Queue можна вважати однією з найважливіших структур даних у світі програмування. Java Queue приваблива своїми властивостями. Основні властивості структури даних Java Queue наведені наступним чином:

• Черга Java працює за принципом FIFO (першим прийшов, першим вийшов). Це вказує на те, що елементи вводяться в чергу в кінці та видаляються з початку.
• Інтерфейс Java Queue надає всі правила та процеси інтерфейсу Collection, як-от включення, видалення тощо.
• Існує два різних класи, які використовуються для реалізації інтерфейсу Queue. Ці класи LinkedList і PriorityQueue.
• Окрім цих двох, існує клас, тобто Черга блокування масиву, який використовується для реалізації інтерфейсу Черги.
• Існує два типи черг: необмежені черги та обмежені черги. Черги, які є частиною пакета java.util, відомі як необмежені черги, а обмежені черги – це черги, які присутні в пакеті java.util.concurrent.
• Deque або (двостороння черга) також є типом черги, яка забезпечує включення та видалення елементів з обох кінців.
• Deque також вважається потокобезпечним.
• Черги блокування також є одним із типів черг, які також є потокобезпечними. Черги блокування використовуються для реалізації запитів виробник-споживач.
• Черги блокування не підтримують нульові елементи. У чергах блокування, якщо виконується будь-яка робота, подібна до нульових значень, також виникає виняток NullPointerException.

Реалізація черги

Класи, які використовуються в реалізації Queue

Класи, які використовуються для реалізації функціональних можливостей черги, подано наступним чином:

• ArrayDeque
• LinkedList
• PriorityQueue

Інтерфейси, що використовуються в реалізації черги

Інтерфейси Java також використовуються в реалізації черги Java. Інтерфейси, які використовуються для реалізації функціональних можливостей черги, наведені нижче:

• Про що
• Черга блокування
• Блокування Deque

Методи класу черги Java

У черзі Java є багато методів, які використовуються дуже часто. Інтерфейс Queue підтримує різні методи, такі як вставка, видалення, peek тощо. Деякі операції черги Java викликають виключення, тоді як деякі з цих операцій повертають певне значення після завершення програми.

Примітка. У Java SE 8 у колекції черги Java не внесено жодних змін. Ці методи, визначені в розділі, надалі готуються в наступних версіях мови програмування Java. Наприклад, Java SE 9.

Різні методи черги Java визначено нижче:

алфавіт з цифрами

Реалізація масиву черги Java

Реалізація черги не така проста, як реалізація стека.

Щоб реалізувати чергу за допомогою масивів, ми спочатку оголошуємо масив, який містить n елементів.

Потім ми визначаємо наступні операції для виконання в цій черзі.

1) Поставте в чергу: Операція вставки елемента в чергу – Enqueue (функція queue Enqueue у програмі). Щоб вставити елемент у задній частині, нам потрібно спочатку перевірити, чи заповнена черга. Якщо він заповнений, ми не можемо вставити елемент. Якщо ззаду

2) Хвіст: Операція видалення елемента з черги — Dequeue (функція queue Dequeue у програмі). Спочатку перевіряємо, чи порожня черга. Щоб операція видалення з черги працювала, у черзі має бути принаймні один елемент.

3) Спереду: Цей метод повертає початок черги.

4) Дисплей: Цей метод обходить чергу та відображає елементи черги.

Програма Java Queue

Наступна програма Java демонструє реалізацію Queue.

QueueArrayImplementation.java

 class Queue { private static int front, rear, capacity; private static int queue[]; Queue(int size) { front = rear = 0; capacity = size; queue = new int[capacity]; } // insert an element into the queue static void queueEnqueue(int item) { // check if the queue is full if (capacity == rear) { System.out.printf('
Queue is full
'); return; } // insert element at the rear else { queue[rear] = item; rear++; } return; } //remove an element from the queue static void queueDequeue() { // check if queue is empty if (front == rear) { System.out.printf('
Queue is empty
&apos;); return; } // shift elements to the right by one place uptil rear else { for (int i = 0; i <rear 0 4 - 1; i++) { queue[i]="queue[i" + 1]; } set queue[rear] to if (rear < capacity) decrement rear rear--; return; print queue elements static void queuedisplay() int i; (front="=" rear) system.out.printf('queue is empty
'); traverse front and for (i="front;" i rear; system.out.printf(' %d , ', queue[i]); of queuefront() system.out.printf('
front element the queue: %d', queue[front]); public class queuearrayimplementation main(string[] args) create a capacity q="new" queue(4); system.out.println('initial queue:'); q.queuedisplay(); inserting in q.queueenqueue(10); q.queueenqueue(30); q.queueenqueue(50); q.queueenqueue(70); system.out.println('queue after enqueue operation:'); q.queuefront(); insert q.queueenqueue(90); q.queuedequeue(); system.out.printf('
queue two dequeue operations:'); pre> <p> <strong>Output:</strong> </p> <pre> Initial Queue: Queue is Empty Queue after Enqueue Operation: 10 , 30 , 50 , 70 , Front Element of the queue: 10 Queue is full 10 , 30 , 50 , 70 , Queue after two dequeue operations: 50 , 70 , Front Element of the queue: 50 </pre> <h2>Java Queue Linked List Implementation</h2> <p>As we have implemented the Queue data structure using Arrays in the above program, we can also implement the Queue using Linked List.</p> <p>We will implement the same methods enqueue, dequeue, front, and display in this program. The difference is that we will be using the Linked List data structure instead of Array.</p> <p>The below program demonstrates the Linked List implementation of Queue in Java.</p> <p> <strong>QueueLLImplementation.java</strong> </p> <pre> class LinkedListQueue { private Node front, rear; private int queueSize; // queue size //linked list node private class Node { int data; Node next; } //default constructor - initially front &amp; rear are null; size=0; queue is empty public LinkedListQueue() { front = null; rear = null; queueSize = 0; } //check if the queue is empty public boolean isEmpty() { return (queueSize == 0); } //Remove item from the front of the queue. public int dequeue() { int data = front.data; front = front.next; if (isEmpty()) { rear = null; } queueSize--; System.out.println(&apos;Element &apos; + data+ &apos; removed from the queue&apos;); return data; } //Add data at the rear of the queue. public void enqueue(int data) { Node oldRear = rear; rear = new Node(); rear.data = data; rear.next = null; if (isEmpty()) { front = rear; } else { oldRear.next = rear; } queueSize++; System.out.println(&apos;Element &apos; + data+ &apos; added to the queue&apos;); } //print front and rear of the queue public void print_frontRear() { System.out.println(&apos;Front of the queue:&apos; + front.data + &apos; Rear of the queue:&apos; + rear.data); } } class QueueLLImplementation{ public static void main(String a[]){ LinkedListQueue queue = new LinkedListQueue(); queue.enqueue(6); queue.enqueue(3); queue.print_frontRear(); queue.enqueue(12); queue.enqueue(24); queue.dequeue(); queue.dequeue(); queue.enqueue(9); queue.print_frontRear(); } } </pre> <p> <strong>Output:</strong> </p> <pre> Element 6 added to the queue Element 3 added to the queue Front of the queue:6 Rear of the queue:3 Element 12 added to the queue Element 24 added to the queue Element 6 removed from the queue Element 3 removed from the queue Element 9 added to the queue Front of the queue:12 Rear of the queue:9 </pre> <hr></rear>

Реалізація пов’язаного списку черги Java

Оскільки ми реалізували структуру даних Queue за допомогою масивів у наведеній вище програмі, ми також можемо реалізувати Queue за допомогою Linked List.

У цій програмі ми реалізуємо ті самі методи: enqueue, dequeue, front і display. Різниця полягає в тому, що ми будемо використовувати структуру даних Linked List замість Array.

Наведена нижче програма демонструє реалізацію зв’язаного списку черги в Java.

QueueLLImplementation.java

 class LinkedListQueue { private Node front, rear; private int queueSize; // queue size //linked list node private class Node { int data; Node next; } //default constructor - initially front & rear are null; size=0; queue is empty public LinkedListQueue() { front = null; rear = null; queueSize = 0; } //check if the queue is empty public boolean isEmpty() { return (queueSize == 0); } //Remove item from the front of the queue. public int dequeue() { int data = front.data; front = front.next; if (isEmpty()) { rear = null; } queueSize--; System.out.println('Element ' + data+ ' removed from the queue'); return data; } //Add data at the rear of the queue. public void enqueue(int data) { Node oldRear = rear; rear = new Node(); rear.data = data; rear.next = null; if (isEmpty()) { front = rear; } else { oldRear.next = rear; } queueSize++; System.out.println('Element ' + data+ ' added to the queue'); } //print front and rear of the queue public void print_frontRear() { System.out.println('Front of the queue:' + front.data + ' Rear of the queue:' + rear.data); } } class QueueLLImplementation{ public static void main(String a[]){ LinkedListQueue queue = new LinkedListQueue(); queue.enqueue(6); queue.enqueue(3); queue.print_frontRear(); queue.enqueue(12); queue.enqueue(24); queue.dequeue(); queue.dequeue(); queue.enqueue(9); queue.print_frontRear(); } } 

Вихід:

 Element 6 added to the queue Element 3 added to the queue Front of the queue:6 Rear of the queue:3 Element 12 added to the queue Element 24 added to the queue Element 6 removed from the queue Element 3 removed from the queue Element 9 added to the queue Front of the queue:12 Rear of the queue:9