رابط جاوا Deque

Java Deque یک ساختار داده است که یک صف معمولی و پشته را ترکیب می کند. شما می توانید عناصر را هم به سر و هم به دم Deque اضافه و حذف کنید. در صف "سنتی" عناصری را به دم خط اضافه می کنید (بعد از آخرین عنصر) و عناصر را از سر صف حذف می کنید. این اصل First In First Out (FIFO) نامیده می شود و مانند هر خط معمولی از مشتریان در زندگی واقعی کار می کند. در جاوا صف یک رابط است، بخشی از چارچوب مجموعه ها. همچنین یک ساختار داده مهم به نام Stack وجود دارد، لیستی که با عناصر در اصل کاملاً معکوس کار می کند، LIFO - آخرین ورودی، اول بیرون. این شبیه به یک پشته از صفحات است، اضافه کردن یا حذف کردن فقط در بالا امکان پذیر است.

صف مقابل دکه

Deque نوع عجیبی از Queue است: شما می توانید عناصر جدیدی را هم به دم و هم به سر خط اضافه کنید. همان داستان حذف: ممکن است آخرین یا اولین عنصر را از این ساختار حذف کنید. از این رو، به نظر می رسد مخلوطی از Stack و Queue باشد. نام "Deque" به معنای "صف دو انتها" است. "Deque" مانند یک "عرشه" از کارت تلفظ می شود و می دانید چیست؟ این تا حدودی شبیه به یک دسته کارت واقعی است: ممکن است یک کارت از پایین یا بالای چنین عرشه بردارید. آیا می خواهید عناصری را از دو طرف ساختار خطی اضافه یا حذف کنید؟ از Deque استفاده کنید. جاوا 8 یا تقریباً هر نسخه دیگری از آن پشتیبانی می کند. یک آجر لگو معمولی و «برج‌های» تک ستونی را تصور کنید که از آجر ساخته شده‌اند. می توانید یک آجر جدید به بالای برج یا به پایین اضافه کنید. همچنین می توانید یک آجر را از هر دو طرف جدا کنید. در اینجا یک مثال داریم: تمام آجرهای زرد را به بالا و همه قرمزها را به پایین اضافه می کنیم. به زودی این مثال را با کد جاوا نشان خواهیم داد. بنابراین می‌توانید از هر دو سر یک جاوا Deque صف‌بندی کنید و در صف قرار دهید، یعنی می‌توانید از Deque به عنوان صف و پشته استفاده کنید. درباره Stack در جاوا بخوانید: Java Stack 101: Deving into the Stack Class درباره صف در جاوا بخوانید: Java Queue Interface و پیاده سازی های آن

ویژگی های دکه

• Deque در جاوا یک رابط است که پیاده سازی آن از یک آرایه قابل تغییر اندازه پشتیبانی می کند. بنابراین شما مجموعه‌ای از ظرفیت‌های بدون محدودیت دارید و می‌توانید عناصر جدیدی را با توجه به نیاز خود اضافه کنید.
• دسترسی همزمان توسط چندین رشته توسط Deque پشتیبانی نمی شود
• در صورت عدم وجود همگام سازی خارجی، Deque از نظر نخ ایمن نیست.
• هیچ عنصر تهی در آرایه مجاز نیست.

اعلان رابط جاوا Deque

public interface Deque<E> extends Queue<E>

روش های جاوا دک

java.util.Deque یک رابط است که رابط صف جاوا را گسترش می دهد و یک صف دو انتها را نشان می دهد. بنابراین می توانید از تمام متدهای Java Queue در حین کار با Deque استفاده کنید. علی‌رغم اینکه Deque رابط Stack را گسترش نمی‌دهد، رابط Deque روش‌هایی را تعریف می‌کند که شما را قادر می‌سازد عملیات معمولی پشته مانند push ، peek و pop را انجام دهید .

• add(element) boolean یک عنصر را به دم Deque اضافه می کند. در صورت موفقیت، true را برمی‌گرداند، اگر در حال حاضر فضایی در دسترس نباشد، یک IllegalStateException ایجاد می‌کند.
• addFirst(element) یک عنصر را به سر Deque اضافه می کند.
• addLast(element) یک عنصر را به دم Deque اضافه می کند.
• offer(element) یک عنصر را به دم اضافه می کند و یک Boolean برمی گرداند تا توضیح دهد که آیا درج موفقیت آمیز بوده است.
• offerFirst(element) یک عنصر را به head اضافه می کند و یک Boolean برمی گرداند تا توضیح دهد که آیا درج موفقیت آمیز بوده است.
• offerLast(element) یک عنصر به دم اضافه می کند و یک Boolean برمی گرداند تا توضیح دهد آیا درج موفقیت آمیز بوده است.
• iterator() یک تکرار کننده برای deque برمی گرداند.
• descendingIterator() تکرار کننده ای را برمی گرداند که برای این deque ترتیب معکوس دارد.
• push(element) یک عنصر را به سر اضافه می کند.
• pop(element) یک عنصر را از هد حذف می کند و آن را برمی گرداند.
• removeFirst() عنصر موجود در سر را حذف می کند.
• removeLast() عنصر دم را حذف می کند.
• poll() سر صفی را که توسط این deque نشان داده شده است (به عبارت دیگر اولین عنصر این deque) بازیابی و حذف می کند، یا اگر این deque خالی باشد، null را برمی گرداند.
• pollFirst() اولین عنصر این deque را بازیابی و حذف می کند، یا اگر این deque خالی باشد، null را برمی گرداند.
• pollLast() آخرین عنصر این deque را بازیابی و حذف می کند، یا اگر این deque خالی باشد null را برمی گرداند.
• peek() سر صف را که توسط این deque نشان داده شده است (به عبارت دیگر اولین عنصر این deque) بازیابی می کند، اما حذف نمی کند، یا اگر این deque خالی باشد، null را برمی گرداند.
• peekFirst() اولین عنصر این deque را بازیابی می کند، اما حذف نمی کند، یا اگر این deque خالی باشد، null را برمی گرداند.
• peekLast() آخرین عنصر این deque را بازیابی می کند، اما حذف نمی کند، یا اگر این deque خالی باشد، null را برمی گرداند.

در جدول زیر همه روش ها بر اساس گروه ها تقسیم شده اند. همانطور که می بینید روش های مختلفی برای افزودن و حذف یک عنصر وجود دارد. برای مثال، هم removeFirst() و هم pop() اولین عنصر را از deque حذف می کنند. دومی از پشته "آمد". این بدان معناست که اگر از ArrayDeque خود فقط به عنوان پشته استفاده می کنید، از pop() برای حذف، از push() برای افزودن و از peek() برای بررسی استفاده کنید. این باعث می شود کد شما برای توسعه دهندگان دیگر معقول تر شود.

پیاده سازی Deque

Java Deque یک رابط است و در Java Collections API پیاده سازی شده است:

• java.util.LinkedList //List and Deque پیاده سازی
• java.util.ArrayDeque // پیاده سازی Deque، کتابخانه جاوا

کلاس LinkedList از یک لیست دوگانه به صورت داخلی برای مدل سازی یک صف یا یک deque استفاده می کند. کلاس ArrayDeque عناصر را به صورت داخلی در یک آرایه ذخیره می کند. اگر تعداد عناصر از حجم آرایه بیشتر شود، یک آرایه جدید تخصیص داده می شود و همه عناصر به سمت بالا حرکت می کنند. این بدان معناست که ArrayDeque بر اساس نیازها رشد می کند.

کلاس ArrayDeque

کلاس ArrayDeque <E> یک صف عمومی دو جهته است که عملکرد را از کلاس AbstractCollection به ارث می برد و از رابط Deque استفاده می کند. ArrayDeque امکان استفاده از deque و resizable-array را فراهم می کند. در ابتدا، آرایه با اندازه 16 مقداردهی اولیه می شود. به عنوان یک صف دو طرفه پیاده سازی می شود، جایی که از دو اشاره گر، یعنی head و tail پشتیبانی می کند. کلاس AbstractCollection را به ارث برده و رابط Deque را پیاده سازی می کند . نکات مهم در مورد کلاس ArrayDeque عبارتند از:

• شما می توانید عناصر را از دم و سر ArrayDeque اضافه یا حذف کنید
• عناصر پوچ مجاز نیستند
• در غیاب همگام سازی خارجی، ArrayDeque ایمن نیست.
• ArrayDeque هیچ محدودیتی در ظرفیت ندارد.

سازندگان کلاس ArrayDeque

• () ArrayDeque یک صف خالی ایجاد می کند.
• ArrayDeque (Collection <? Extends E> collection) یک صف پر از عناصر مجموعه Collection ایجاد می کند.
• ArrayDeque (ظرفیت int) یک صف با ظرفیت اولیه ایجاد می کند . اگر ظرفیت اولیه را مشخص نکنید، ظرفیت پیش فرض 16 است.

مثال Java Deque - ArrayDeque

مثال برج لگو را از ابتدای مقاله به یاد دارید؟ بیایید یک کلاس برای ساخت برج های تک ستونی از آجر لگو ایجاد کنیم. آجرها می توانند قرمز، زرد یا آبی باشند. قانون ساخت برج ما: آجرهای قرمز را در پایین و آجرهای زرد را در بالا قرار می دهیم. مثال بزرگ جاوا 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 +
              '}';
   }
}

اینجا کلاس برج ماست. ما یک برج را راه اندازی می کنیم. برج آغاز شده به مقدار قرمز و زرد بستگی دارد. می توانیم آجر را به برج اضافه کنیم یا آن را حذف کنیم. اگر زرد بود به بالا آجر اضافه می کنیم و اگر قرمز بود به پایین اضافه می کنیم.

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

صبر کن چی؟؟ چرا قرمزها در بالا هستند؟ نه، این کار را نمی کنند. آنها فقط از اول (پایین) تا آخر (بالا) روی کنسول چاپ کردند. بنابراین اگر می خواهید چیزی شبیه به تصویر با آجرهای بالا ببینید، می توانید متد drawTower کلاس LegoTower را تغییر دهید. این یک کار بسیار آسان است!

LinkedList

رابط List توالی افزودن آیتم ها را حفظ می کند و امکان دسترسی به آیتم بر اساس فهرست را فراهم می کند. Deque یک صف دو طرفه است و از افزودن و حذف عناصر از هر دو طرف پشتیبانی می کند. LinkedList عمدتاً به عنوان پیاده‌سازی List شناخته می‌شود، اما این کلاس Deque را نیز پیاده‌سازی می‌کند و به ما اجازه می‌دهد یک صف دوطرفه متشکل از هر شیء از جمله null ایجاد کنیم. LinkedList مجموعه ای از عناصر است. می‌توانیم آن را در منبع کد کلاس ببینیم، این بار به فیلدها توجه کنید: در اینجا یک مثال اضافه می‌کنیم، اما اگر می‌خواهید درباره LinkedList بیشتر بدانید، به این مقاله CodeGym خوش آمدید .

پیاده سازی لیست پیوندی در جاوا، افزودن و حذف عناصر. مثال

بیایید این عملیات را در عمل امتحان کنیم. اول، اجرای 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]