Java Deque интерфейс

Java Deque е структура от данни, която комбинира обикновена опашка и стек. Можете да добавяте и премахвате елементи Howто към главата, така и към опашката на Deque. В „традиционната“ опашка добавяте елементи към опашката на реда (след последния елемент) и премахвате елементи от главата на опашката. Този принцип се нарича First In First Out (FIFO) и работи като всяка обичайна линия от клиенти в реалния живот. В Java Queue е интерфейс, част от рамката на колекциите. Има и важна структура от данни, наречена стек, списък, който работи с елементи на напълно обратен принцип, LIFO — последен влязъл, пръв излязъл. Подобно е на купчина чинии, добавянето or премахването е възможно само отгоре.

Опашка срещу Deque

Deque е доста странен тип опашка: можете да добавяте нови елементи Howто към опашката, така и към началото на линията. Същата история с премахването: можете да премахнете последния or първия елемент от тази структура. Следователно изглежда, че е смесица от стек и опашка. Името „Deque“ означава „Опашка с двоен край“. „Deque“ се произнася като „колоде“ карти и знаете ли Howво? Донякъде прorча на истинско тесте карти: можете да вземете карта от долната or горната част на такова тесте. Искате да добавите or премахнете елементи от двете страни на няHowва линейна структура? Използвайте Deque. Java 8 or почти всяка друга version го поддържа. Представете си типична лего тухла и едноколонни „кули“, напequalsи от тухлите. Можете да добавите нова тухла на върха or на дъното на кулата. Можете също да премахнете тухла от двете страни. Тук имаме пример: добавяме всички жълти тухли отгоре и всички червени отдолу. Скоро ще демонстрираме този пример с Java code. Така че можете да поставяте в опашка и да излизате от опашка от двата края на Java Deque, което означава, че можете да използвате Deque и като опашка, и като стек. Прочетете за Stack в Java: Java Stack 101: Задълбочаване в класа на стека Прочетете за Queue в Java: Java Queue Interface и неговите реализации

Характеристики на Deque

• Deque в Java е интерфейс, чиито реализации осигуряват поддръжка на масив с възможност за промяна на размера. Така че имате масив от капацитет без ограничения и можете да добавяте нови елементи според вашите нужди.
• Едновременният достъп от множество нишки не се поддържа от Deque
• Deque не е безопасен за нишки в случай на липса на външна синхронизация.
• Не са разрешени нулеви елементи в deque масив.

Deque Java интерфейс декларация

public interface Deque<E> extends Queue<E>

Java Deque методи

java.util.Deque е интерфейс, който разширява Java Queue Interface и представлява двустранна опашка. Така че можете да използвате всички методи на Java Queue, докато работите с Deque. Въпреки че Deque не разширява интерфейса на Stack, интерфейсът Deque дефинира методи, които ви позволяват да правите типични операции на стека като push , peek и pop .

• boolean add(element) добавя елемент към опашката на Deque. Връща true при успех, хвърля IllegalStateException, ако в момента няма свободно място.
• addFirst(element) добавя елемент към главата на Deque.
• addLast(element) добавя елемент към опашката на Deque.
• offer(element) добавя елемент към опашката и връща булево meaning, за да обясни дали вмъкването е било успешно.
• offerFirst(element) добавя елемент към главата и връща булево meaning, за да обясни дали вмъкването е било успешно.
• offerLast(element) добавя елемент към опашката и връща булево meaning, за да обясни дали вмъкването е било успешно.
• iterator() връща итератор за deque.
• descendingIterator() връща итератор, който има обратен ред за тази двойна последователност.
• push(element) добавя елемент към главата.
• pop(element) премахва елемент от главата и го връща.
• removeFirst() премахва елемента в началото.
• removeLast() премахва елемента в опашката.
• poll() извлича и премахва главата на опашката, представена от тази двойна последователност (с други думи, първият елемент от тази двойна последователност), or връща null, ако тази двойна последователност е празна.
• pollFirst() извлича и премахва първия елемент от тази последователност or връща null, ако тази последователност е празна.
• pollLast() извлича и премахва последния елемент от тази последователност or връща null, ако тази последователност е празна.
• peek() извлича, но не премахва, главата на опашката, представена от тази двойна последователност (с други думи, първият елемент от тази последователна последователност), or връща null, ако тази последователна редица е празна.
• peekFirst() извлича, но не премахва, първия елемент от тази последователност or връща null, ако тази последователност е празна.
• peekLast() извлича, но не премахва, последния елемент от тази последователност or връща null, ако тази последователност е празна.

Тук в tableта по-долу всички методи са разделени по групи. Както можете да видите, има много различни методи за добавяне и премахване на елемент. Например, и removeFirst() и pop() премахват първия елемент от deque. Вторият „дойде“ от стека. Това означава, че ако използвате своя ArrayDeque само като стек, използвайте pop() за премахване, push() за добавяне и peek() за проверка. Това прави вашия code по-разумен за други разработчици.

Реализации на Deque

Java Deque е интерфейс и има реализации в Java Collections API:

• java.util.LinkedList // Реализация на списък и Deque
• java.util.ArrayDeque // Реализация на Deque, Java библиотека

Класът LinkedList използва двойно свързан списък вътрешно за моделиране на опашка or deque. Класът ArrayDeque съхранява елементите вътрешно в масив. Ако броят на елементите надвишава обема на масива, се разпределя нов масив и всички елементи се преместват. Това означава, че ArrayDeque расте според нуждите.

Клас ArrayDeque

Класът ArrayDeque <E> е обща двупосочна опашка, наследяваща функционалност от класа AbstractCollection и използваща интерфейса Deque. ArrayDeque предоставя възможност за използване на deque и resizable-array. Първоначално масивът се инициализира с размер 16. Реализира се като двупосочна опашка, където поддържа два указателя, а именно главата и опашката. Той наследява класа AbstractCollection и имплементира интерфейса Deque . Важните точки за класа ArrayDeque са:

• Можете да добавяте or премахвате елементи от опашката и главата на ArrayDeque
• Нулеви елементи не са разрешени
• ArrayDeque не е безопасен за нишки при липса на външна синхронизация.
• ArrayDeque няма ограничения за капацитет.

Конструктори на клас ArrayDeque

• ArrayDeque() създава празна опашка.
• ArrayDeque (колекция Collection <? Extends E>) създава опашка, пълна с елементи на колекция Collection.
• ArrayDeque (int капацитет) създава опашка с първоначален капацитет капацитет. Ако не посочите първоначалния капацитет, капацитетът по подразбиране е 16.

Пример за Java Deque — ArrayDeque

Помните ли примера с Лего кулата от началото на статията? Нека създадем клас за изграждане на кули с една колона, напequalsи от Lego Bricks. Тухлите могат да бъдат червени, жълти or сини. Нашето правило за изграждане на кула: поставяме червените тухли на дъното и жълтите тухли на върха. Пример за голям Java Deque

//enum with colors
public enum Color {
   RED, YELLOW, BLUE;
}

//class for the standard Lego Brick. You can connect or disconnect the Brick, it has color
public class LegoBrick {
   Color color;
   boolean isConnected;

   public void connect() {
       System.out.println("This brick is connected");
       this.isConnected = true;
   }

   public void disconnect() {
       System.out.println("Disconnected");
       isConnected = false;
   }

   public LegoBrick(Color color, boolean isConnected) {
       this.color = color;
       this.isConnected = isConnected;
   }

   public Color getColor() {
       return color;
   }

   public boolean isConnected() {
       return isConnected;
   }

   @Override
   public String toString() {
       return "LegoBrick{" +
              "color=" + color +
              ", isConnected=" + isConnected +
              '}';
   }
}

Ето го нашия клас Tower. Инициираме кула. Инициираната кула зависи от количеството червени и жълти. Можем да добавим тухла към кулата or да я премахнем. Добавяме тухла отгоре, ако е жълта, и я добавяме отдолу, ако е червена.

import java.util.ArrayDeque;
public class LegoTower {
   ArrayDeque<LegoBrick> myTower;
   int quantityOfReds;
   int quantityOfYellows;

   public void addBrickToTower(LegoBrick newLegoBrick) {
       if (newLegoBrick.getColor() == Color.YELLOW) {
           this.myTower.offerLast(newLegoBrick);
           quantityOfYellows++;
       }
	//we can use addFirst(e)/push(e) instead of offerFirst here
       if (newLegoBrick.getColor() == Color.RED) {
           myTower.offerFirst(newLegoBrick);
           quantityOfReds++;
       }
   }

   public void removeBrickFromTower (LegoBrick legoBrick) {
       if (legoBrick.getColor() == Color.YELLOW) {
           this.myTower.removeLast();
           quantityOfYellows--;
       }
       if (legoBrick.getColor() == Color.RED) {
           myTower.removeFirst();
           quantityOfReds--;
       }
       legoBrick.isConnected = false;

   }

   public LegoTower(int quantityOfReds, int quantityOfYellows) {

       myTower = new ArrayDeque<>();
       this.quantityOfReds = quantityOfReds;
       this.quantityOfYellows = quantityOfYellows;
       for (int i = 0; i < quantityOfReds; i++) {
           LegoBrick redLegoBrick = new LegoBrick(Color.RED, false);
           myTower.addFirst(redLegoBrick);
           redLegoBrick.isConnected = true;
       }
       for (int i = 0; i < quantityOfYellows; i++) {
           LegoBrick yellowLegoBrick = new LegoBrick(Color.YELLOW, false);
           myTower.addLast(yellowLegoBrick);
           yellowLegoBrick.isConnected = true;
       }
   }

   public void setMyTower(ArrayDeque<legobrick> myTower) {
       this.myTower = myTower;
   }

   public void setQuantityOfReds(int quantityOfReds) {
       this.quantityOfReds = quantityOfReds;
   }

   public void setQuantityOfYellows(int quantityOfYellows) {
       this.quantityOfYellows = quantityOfYellows;
   }

   @Override
   public String toString() {
       return "LegoTower{" +
              "myTower=" + myTower +
              ", quantityOfReds=" + quantityOfReds +
              ", quantityOfYellows=" + quantityOfYellows +
              '}';
   }

   public void drawTower() {
       for (LegoBrick i : myTower) {
           System.out.println(i.color);
       }
   }
}


public class Main {
   public static void main(String[] args) {
       LegoBrick legoBrick1 = new LegoBrick(Color.YELLOW, false);
       legoBrick1.connect();
       System.out.println(legoBrick1.toString());
       legoBrick1.disconnect();
       System.out.println(legoBrick1.toString());
       LegoBrick legoBrick2 = new LegoBrick(Color.YELLOW, false);
       LegoBrick legoBrick3 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick4 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick5 = new LegoBrick(Color.YELLOW, false);

       LegoTower legoTower = new LegoTower(2, 5);
       System.out.println("my Initiated Lego Tower: ");
       legoTower.drawTower();
       legoTower.addBrickToTower(legoBrick1);
       legoTower.addBrickToTower(legoBrick2);
       legoTower.addBrickToTower(legoBrick3);
       legoTower.addBrickToTower(legoBrick4);
       legoTower.addBrickToTower(legoBrick5);
       System.out.println("My LegoTower after adding some elements: ");
       legoTower.drawTower();
       legoTower.removeBrickFromTower(legoBrick1);
       legoTower.removeBrickFromTower(legoBrick3);
       System.out.println("We removed one red and one yellow brick:");
       legoTower.drawTower();

   }

}

Резултатът от стартирането на тази програма:

my Initiated LegoTower:

RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
My LegoTower after adding some elements:
RED
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
We removed one red and one yellow brick:
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW

Process finished with exit code 0

Чакаме Howво?? Защо червените са отгоре? Не, не го правят. Те просто се отпечатаха на конзолата, започвайки от първия (отдолу) до последния (отгоре). Така че, ако искате да видите нещо като на снимката с тухлите по-горе, можете да промените метода drawTower на класа LegoTower. Това е много лесна задача!

LinkedList

Интерфейсът List запазва последователността на добавяне на елементи и позволява достъп до елемента по индекс. Deque е двупосочна опашка и поддържа добавяне и премахване на елементи от двете страни. LinkedList е известен главно като реализация на List, но също така този клас имплементира Deque и ни позволява да създадем двупосочна опашка, състояща се от всяHowви обекти, включително null. LinkedList е колекция от елементи. Можем да го видим в изходния code на класа, този път обърнете внимание на полетата: Тук добавяме един пример, но ако искате да научите повече за LinkedList, добре дошли в тази статия на CodeGym .

Реализация на свързан списък в Java, добавяне и премахване на елементи. Пример

Нека изпробваме тези операции на практика. Първо, изпълнение на Java LinkedList: създаване на LinkedList от низове, добавяне на 3 елемента. След това премахнете един, след това добавете един в средата.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<string> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Резултатът от стартирането на тази програма:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]