ממשק Java Deque

Java Deque הוא מבנה נתונים המשלב תור ו-Stack רגילים. אתה יכול להוסיף ולהסיר אלמנטים הן לראש והן לזנב של ה-Deque. בתור ה"מסורתי" מוסיפים אלמנטים לזנב השורה (אחרי האלמנט האחרון) ומסירים אלמנטים מראש התור. עקרון זה נקרא First In First Out (FIFO) והוא פועל כמו כל קו לקוחות רגיל בחיים האמיתיים. ב-Java Queue הוא ממשק, חלק ממסגרת האוספים. יש גם מבנה נתונים חשוב בשם Stack, רשימה שעובדת עם אלמנטים בעקרון הפוך לחלוטין, LIFO - אחרון נכנס, ראשון יוצא. זה דומה לערימה של צלחות, הוספה או הסרה אפשרית רק בחלק העליון.

תור מול דקה

Deque הוא סוג די מוזר של תור: אתה יכול להוסיף אלמנטים חדשים גם לזנב וגם לראש הקו. אותו סיפור עם הסרה: אתה יכול להסיר את האלמנט האחרון או הראשון מהמבנה הזה. לפיכך, נראה שמדובר בתערובת של סטאק ותור. פירוש השם "Deque" הוא "תור כפול". "Deque" מבוטא כמו "חפיסת" קלפים ואתה יודע מה? זה קצת דומה לחפיסת קלפים אמיתית: אתה יכול לקחת קלף מהחלק התחתון או העליון של חפיסה כזו. רוצה להוסיף או להסיר אלמנטים משני הצדדים של מבנה ליניארי כלשהו? השתמש ב-Deque. Java 8 או כמעט כל גרסה אחרת תומכת בו. דמיינו לבנת לגו טיפוסית ו"מגדלים" חד עמודים העשויים מהלבנים. אתה יכול להוסיף לבנה חדשה לראש המגדל או לתחתית. אתה יכול גם להסיר לבנה משני הצדדים. הנה לנו דוגמה: אנחנו מוסיפים את כל הלבנים הצהובות למעלה ואת כל האדומים למטה. נדגים את הדוגמה הזו עם קוד Java בקרוב. אז אתה יכול לעמוד בתור ולעמוד בתור משני הקצוות של Java Deque, זה אומר שאתה יכול להשתמש ב-Deque כתור וגם כמחסנית. קרא על Stack ב-Java: Java Stack 101: התעמקות ב-Stack Class קרא על Queue ב-Java: Java Queue ממשק והטמעות שלו

התכונות של Deque

• Deque ב-Java הוא ממשק, אשר יישומים מספקים תמיכה במערך שניתן לשנות את גודלו. אז יש לך מערך של קיבולת ללא הגבלות ואתה יכול להוסיף אלמנטים חדשים בהתאם לצרכים שלך.
• גישה שוטפת על ידי שרשורים מרובים אינה נתמכת על ידי Deque
• Deque אינו בטוח בשרשור במקרה של היעדר סנכרון חיצוני.
• אסור להשתמש ברכיבי Null ב-deque של מערך.

הצהרת ממשק Java של Deque

public interface Deque<E> extends Queue<E>

שיטות Java Deque

java.util.Deque הוא ממשק שמרחיב את ממשק Java Queue ומייצג תור כפול. אז אתה יכול להשתמש בכל שיטות Java Queue תוך כדי עבודה עם Deque. למרות ש-Deque לא מרחיב את ממשק ה-Stack, ממשק ה-Deque מגדיר שיטות המאפשרות לך לבצע פעולות מחסנית טיפוסיות כגון push , peek ו- pop .

• boolean add(element) מוסיף אלמנט לזנב של Deque. מחזיר כ-true עם הצלחה, זורק חריגה של IllegalState אם אין מקום פנוי כרגע.
• addFirst(element) מוסיף אלמנט לראש ה-Deque.
• addLast(element) מוסיף אלמנט לזנב של Deque.
• offer(element) מוסיף אלמנט לזנב ומחזיר ערך בוליאני כדי להסביר אם ההכנסה הצליחה.
• offerFirst(element) מוסיף אלמנט לראש ומחזיר ערך בוליאני כדי להסביר אם ההכנסה הצליחה.
• offerLast(element) מוסיף אלמנט לזנב ומחזיר ערך בוליאני כדי להסביר אם ההכנסה הצליחה.
• iterator() מחזיר איטרטור עבור ה-deque.
• descendingIterator() מחזיר איטרטור שיש לו סדר הפוך עבור ה-deque הזה.
• push(אלמנט) מוסיף אלמנט לראש.
• pop(element) מסיר אלמנט מהראש ומחזיר אותו.
• removeFirst() מסיר את האלמנט בראש.
• removeLast() מסיר את האלמנט בזנב.
• poll() מאחזר ומסיר את ראש התור המיוצג על ידי ה-deque הזה (במילים אחרות, האלמנט הראשון של ה-deque הזה), או מחזיר null אם ה-deque הזה ריק.
• pollFirst() מאחזר ומסיר את הרכיב הראשון של ה-deque הזה, או מחזיר null אם ה-deque הזה ריק.
• pollLast() מאחזר ומסיר את הרכיב האחרון של ה-deque הזה, או מחזיר null אם ה-deque הזה ריק.
• peek() מאחזר, אך לא מסיר, את ראש התור המיוצג על ידי ה-deque הזה (במילים אחרות, האלמנט הראשון של ה-deque הזה), או מחזיר null אם ה-deque הזה ריק.
• peekFirst() מאחזר, אך אינו מסיר, את הרכיב הראשון של ה-deque הזה, או מחזיר null אם ה-deque הזה ריק.
• peekLast() מאחזר, אך לא מסיר, את הרכיב האחרון של ה-deque הזה, או מחזיר null אם ה-deque הזה ריק.

כאן בטבלה למטה כל השיטות מחולקות לפי קבוצות. כפי שאתה יכול לראות ישנן שיטות רבות ושונות להוסיף ולהסיר אלמנט. לדוגמה, removeFirst() ו-pop() מסירים את האלמנט הראשון מ-deque. השני "בא" מהערימה. זה אומר שאם אתה משתמש ב-ArrayDeque שלך ​​כמחסנית בלבד, השתמש ב-pop() כדי להסיר, ב-push() כדי להוסיף ולהציץ() כדי לבדוק. זה הופך את הקוד שלך להגיוני יותר עבור מפתחים אחרים.

יישום דקה

Java Deque הוא ממשק ויש לו יישומים ב-Java Collections API:

• java.util.LinkedList //יישום רשימה ו-Deque
• java.util.ArrayDeque //יישום Deque, ספריית Java

המחלקה LinkedList משתמשת ברשימה מקושרת כפולה באופן פנימי כדי ליצור מודל של תור או דסק. מחלקה ArrayDeque מאחסנת את האלמנטים באופן פנימי במערך. אם מספר האלמנטים חורג מנפח המערך, מוקצה מערך חדש וכל הרכיבים עוברים. זה אומר ArrayDeque גדל לפי הצרכים.

מחלקה ArrayDeque

מחלקה ArrayDeque <E> היא תור כללי דו-כיווני, שיורש פונקציונליות מהמחלקה AbstractCollection ומשתמש בממשק Deque. ArrayDeque מספק את המתקן של שימוש ב-deque ומערך לשינוי גודל. בתחילה, המערך מאותחל בגודל 16. הוא מיושם כתור דו-כיווני, שבו הוא תומך בשני מצביעים, כלומר הראש והזנב. הוא יורש את מחלקה AbstractCollection ומיישם את ממשק Deque . הנקודות החשובות במחלקת ArrayDeque הן:

• אתה יכול להוסיף או להסיר אלמנטים מהזנב ומהראש של ArrayDeque
• רכיבי Null אינם מותרים
• ArrayDeque אינו בטוח בשרשור, בהיעדר סנכרון חיצוני.
• ל- ArrayDeque אין הגבלות קיבולת.

קונסטרוקטורים בכיתה ArrayDeque

• ArrayDeque() יוצר תור ריק.
• ArrayDeque (Collection <? Extends E> collection) יוצר תור מלא ברכיבי אוסף Collection.
• ArrayDeque (קיבולת int) יוצרת תור עם קיבולת קיבולת ראשונית . אם לא תציין את הקיבולת הראשונית, קיבולת ברירת המחדל היא 16.

דוגמה ל-Java Deque - ArrayDeque

זוכרים את דוגמה למגדל הלגו מתחילת המאמר? בואו ניצור כיתה לבניית מגדלים בעלי עמודה אחת העשויים מלבני לגו. לבנים יכול להיות אדום, צהוב או כחול. כלל בניית המגדל שלנו: אנו שמים את הלבנים האדומות למטה ולבנים צהובות למעלה. דוגמה גדולה ל-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 +
              '}';
   }
}

הנה כיתת המגדל שלנו. אנחנו יוזמים מגדל. המגדל היזום תלוי בכמות האדומים והצהובים. אנחנו יכולים להוסיף לבנים למגדל או להסיר אותו. אנו מוסיפים לבנים לחלק העליון אם הוא צהוב ומוסיפים אותו לתחתית אם הוא אדום.

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. זו משימה קלה מאוד!

רשימה מקושרת

ממשק ה- List שומר על רצף הוספת הפריטים ומאפשר גישה לפריט לפי אינדקס. Deque הוא תור דו-כיווני, והוא תומך בהוספה והסרה של אלמנטים משני הצדדים. LinkedList ידוע בעיקר כיישום List, אבל גם מחלקה זו מיישמת את Deque, והיא מאפשרת לנו ליצור תור דו-כיווני המורכב מכל אובייקט כולל null. LinkedList הוא אוסף של אלמנטים. אנחנו יכולים לראות את זה במקור הקוד של הכיתה, הפעם שימו לב לשדות: כאן אנחנו מוסיפים דוגמה אחת, אבל אם אתם רוצים ללמוד עוד על 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]