ממשק Java Queue והטמעות שלו

כאן אנו הולכים לדון בממשק Java Queue. תוכלו לגלות מהו מבנה הנתונים של Queue , כיצד הוא מיוצג ב-Java, אילו שיטות הן החשובות ביותר עבור כל התורים. כמו כן, אילו יישומים של Queue הם בשפת Java. לאחר מכן, אנו בוחנים מקרוב את היישומים החשובים ביותר ולומדים אותם בעזרת דוגמאות.

מבנה נתונים בתור

תור הוא מבנה נתונים מופשט ליניארי עם הסדר המסוים של ביצוע הפעולות - First In First Out (FIFO). זה אומר שאתה יכול להוסיף אלמנט (או תור, לשים בתור) רק בסוף המבנה, ולקחת אלמנט (לעקוב או להסיר מהתור) רק מההתחלה שלו. אתה עשוי לדמיין את מבנה הנתונים בתור בקלות רבה. זה נראה כמו תור או תור של לקוחות בחיים האמיתיים. הלקוח שהגיע ראשון, יקבל שירות ראשון. אם יש לך ארבעה אנשים בתור במקדונלד'ס או במקום אחר, הראשון שיעמוד בתור יהיה הראשון לקבל את החנות. אם הלקוח החדש יגיע, הוא/היא יהיו ה-5 בתור לקבל המבורגרים. לכן, תוך כדי עבודה עם תור, מוסיפים אלמנטים חדשים לסוף, ואם רוצים לקבל אלמנט, הוא יילקח מההתחלה. זהו העיקרון העיקרי של עבודת מבנה נתוני תורים קלאסית.

תור ב-Java

תור ב-Java הוא ממשק. לפי תיעוד של אורקל, לממשק Queue יש 2 ממשקי על, 4 ממשקים שונים שיורשים מהתור ורשימת מחלקות מרשימה ביותר. מה זה אומר? קודם כל, Java Queue הוא חלק מ-Collection Framework ומיישם ממשק Collection. אז זה תומך בכל השיטות של ממשק אוסף כגון הכנסה, מחיקה וכן הלאה. Queue מיישמת ממשק Iterable, המאפשר לאובייקט להיות היעד של הצהרת "לכל לולאה".

שיטות תור Java

התור מצהיר על מספר שיטות. כשיטות של ממשק הן צריכות להיות מיוצגות בכל המחלקות המיישמות Queue. שיטות התור החשובות ביותר, Java:

• Boolean offer() - מכניס אלמנט חדש לתור אם זה אפשרי
• Boolean add(E e) - מכניס אלמנט חדש לתור אם זה אפשרי. מחזירה true במקרה של הצלחה וזורקת IllegalStateException אם אין רווח.
• Object poll() - מאחזר ומסיר אלמנט מראש ה-. מחזירה null אם התור ריק.
• Object remove() - מאחזר ומסיר אלמנט מראש התור.
• Object peek() – מאחזר, אך לא מסיר אלמנט מראש התור. מחזירה null אם התור ריק.
• Object element() – מאחזר, אך לא מסיר אלמנט מראש התור.

ממשקי משנה של Java Queue

ממשק התור עובר בירושה על ידי 4 ממשקי משנה - BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . אתה יכול לחלק אותם ל-3 קבוצות: Deques, Blocking Queues ותורי העברה כאשר BlockingDeque שייך לשניים הראשונים. בואו נסתכל על הקבוצות הללו.

דקים

Deque פירושו תור כפול ותומך בהוספה או הסרה משני זנבות הנתונים כתור (ראשון-in-first-out/FIFO) או מהראש כמבנה נתונים פופולרי אחר הנקרא מחסנית ( אחרון - אין- יוצא ראשון/LIFO). מחלקות המטשמות ממשק Deque: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

חסימת תורים

תור חסימה הוא תור שחוסם שרשור בשני מקרים:

• thread מנסה להשיג אלמנטים מתור ריק
• thread מנסה להכניס אלמנטים לתור המלא

כאשר שרשור מנסה לקבל פריטים מתור ריק, הוא ממתין עד שרשור אחר יכניס את הפריטים לתור. באופן דומה, כאשר שרשור מנסה להכניס אלמנטים לתור מלא, הוא ממתין עד שרשור אחר יוציא את האלמנטים מהתור כדי לקבל מקום פנוי עבור האלמנטים. בטח, המושג "תור מלא" מרמז שלתור יש גודל מוגבל, שבדרך כלל מצוין בקונסטרוקטור. תורי חסימה סטנדרטיים כוללים LinkedBlockingQueue, SynchronousQueue ו-ArrayBlockingQueue. יישום מחלקות של ממשק BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDeque הוא ממשק משנה עבור BlockingQueue. BlockingDeque כגון BlockingQueue הוא תור חסימה, אך דו-כיווני. אז זה יורש את המאפיינים של ממשק Deque. הוא מכוון לביצוע מרובה הליכי, אינו מאפשר אפס אלמנטים והיכולת להיות מוגבלת. הטמעות של ממשק BlockingDeque חוסמות את פעולת קבלת האלמנטים אם התור ריק, והוספת אלמנט לתור אם הוא מלא.

תורי העברה

ממשק TransferQueue מרחיב את ממשק BlockingQueue. אולם בניגוד ליישום של תורי ממשק BlockingQueue, שבהם ניתן לחסום שרשורים אם התור ריק (קריאה), או אם התור מלא (כתיבה), תורי ממשק TransferQueue חוסמים את זרם הכתיבה עד שזרם אחר יאחזר את האלמנט. השתמש בשיטת העברה לשם כך. במילים אחרות, הטמעת BlockingQueue מבטיחה שהאלמנט שנוצר על ידי המפיק חייב להיות בתור, בעוד שהטמעת TransferQueue מבטיחה שאלמנט המפיק "נקלט" על ידי הצרכן. יש רק יישום Java רשמי אחד של ממשק TransferQueue - LinkedTransferQueue.

יישום תור Java

ישנן מחלקות רבות המטשמות ממשק תור:

• AbstractQueue לפי Queue Java 8 docs, מחלקה אבסטרקטית זו מספקת יישומים בסיסיים של פעולות תור מסוימות. זה לא מאפשר רכיבים null. ישנן עוד 3 שיטות הוספה, הסרה ורכיב המבוססות על הצעה קלאסית בתור , סקר והצצה , בהתאמה. עם זאת, הם זורקים חריגים במקום לציין כישלון באמצעות החזרות כוזבות או ריק.
• ArrayBlockingQueue - תור חסימת FIFO בגודל קבוע מגובה על ידי מערך
• ArrayDeque - יישום מערך שניתן לשנות את גודלו של ממשק Deque
• ConcurrentLinkedDeque - תיאור מקביל ללא גבולות המבוסס על צמתים מקושרים.
• ConcurrentLinkedQueue - תור בטוח ללא גבולות המבוסס על צמתים מקושרים.
• DelayQueue - תור תזמון מבוסס זמן מגובה בערימה
• LinkedBlockingDeque - יישום במקביל של ממשק Deque.
• LinkedBlockingQueue - תור חסימת FIFO מוגבל באופן אופציונלי המגובה על ידי צמתים מקושרים
• LinkedList - יישום רשימה מקושרת כפולה של ממשקי List ו-Deque. מיישם את כל פעולות הרשימה האופציונליות ומתיר את כל האלמנטים (כולל null)
• LinkedTransferQueue - תור העברה בלתי מוגבל המבוסס על צמתים מקושרים
• PriorityBlockingQueue - תור עדיפות חסימה ללא גבולות מגובה בערימה
• PriorityQueue - תור עדיפות המבוסס על מבנה הנתונים הערימה
• SynchronousQueue - תור חסימה שבו כל פעולת הוספה חייבת לחכות לפעולת הסרה מתאימה על ידי שרשור אחר, ולהיפך.

ההטמעות הפופולריות ביותר הן LinkedList, ArrayBlockingQueue ו-PriorityQueue. בואו נסתכל עליהם ונעשה כמה דוגמאות להבנה טובה יותר.

רשימה מקושרת

Class LinkedList ב-Java מיישמת ממשקי List ו-Deque. אז זהו שילוב של List ו-Deque, תור דו-כיווני, התומך בהוספה והסרה של אלמנטים משני הצדדים. ב-Java LinkedList היא רשימה מקושרת כפולה: כל אלמנט של List קורא ל-Node ומכיל אובייקט והפניות לשני אובייקטים שכנים - הקודם והבא. אתה יכול לומר ש-LinkedList אינו יעיל במיוחד במונחים של שימוש בזיכרון. זה נכון, אבל מבנה הנתונים הזה יכול להיות שימושי במקרה של ביצועי פעולות הוספה ומחיקה. עם זאת זה קורה רק אם אתה משתמש באיטרטורים עבורם (במקרה זה זה מתרחש בזמן קבוע). פעולות גישה לפי אינדקס מבוצעות על ידי חיפוש מתחילת הסוף (מה שקרוב מביניהם) לאלמנט הרצוי. עם זאת, אל תשכח עלויות נוספות עבור אחסון הפניות בין אלמנטים. אז, LinkedList הוא יישום התור הפופולרי ביותר ב-Java. זה גם מימוש של List ו-Deque וזה מאפשר לנו ליצור תור דו-כיווני המורכב מכל אובייקט כולל null. LinkedList הוא אוסף של אלמנטים.

בוני LinkedList

LinkedList() ללא פרמטרים משמש לבניית רשימה ריקה. LinkedList(Collection<? extends E> c) מיועדת ליצירת רשימה המכילה את האלמנטים של האוסף שצוין, לפי הסדר שהם יוחזרו על ידי האיטרטור של האוסף.

שיטות עיקריות לרשימה מקושרת:

• add(E element) מוסיף את האלמנט שצוין לסוף רשימה זו;
• add(int index, E element) הוספת האלמנט באינדקס המיקום שצוין;
• get(int index) מחזירה את האלמנט במיקום שצוין ברשימה זו;
• remove(int index) מסיר את האלמנט שנמצא באינדקס המיקום;
• remove(Object o) מסיר את המופע הראשון של אלמנט ?o מהרשימה הזו אם הוא קיים.
• remove() מאחזר ומסיר את האלמנט הראשון ברשימה.
• addFirst(), addLast() מוסיפים אלמנט להתחלה/סוף של רשימה
• clear() מסיר את כל הרכיבים מהרשימה
• contains(Object o) מחזירה true אם הרשימה מכילה את האלמנט o.
• indexOf(Object o) מחזיר את האינדקס של ההופעה הראשונה של אלמנט o, או -1 אם הוא לא ברשימה.
• set(int index, E element) מחליף את האלמנט במיקום האינדקס באלמנט
• size()מחזיר את כמות האלמנטים ברשימה.
• toArray() מחזיר מערך המכיל את כל האלמנטים של הרשימה מהאלמנט הראשון ועד האחרון.
• pop() שמקפיץ אלמנט מהמחסנית (מיוצג על ידי הרשימה)
• push(E e) שדוחף אלמנט אל הערימה (מיוצג על ידי רשימה זו)

דוגמה לתור Java - LinkedList (הצבה והסרה של אלמנטים בדרכים שונות)

import java.util.*;

public class LinkedListTest {

       public static void main(String args[]){

           LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
           myLinkedList.add(1);
           myLinkedList.add(2);
           myLinkedList.add(4);
           System.out.println("three added elements: " + myLinkedList);
           //put one element into the head, not to the tail:
           myLinkedList.push(5);
           System.out.println("The new element last in will be the first: " + myLinkedList);
           //add new element at the specified position:
           myLinkedList.add(4,3);
           //put one element into the head, not to the tail (same as push):
           myLinkedList.addFirst(6);
           System.out.println(myLinkedList);
           //now remove element no 2 (it is 1):
           myLinkedList.remove(2);
           System.out.println(myLinkedList);
           //now remove the head of the list
           myLinkedList.pop();
           System.out.println(myLinkedList);
           //remove with the other method
           myLinkedList.remove();
           System.out.println(myLinkedList);
           //and with one more
           myLinkedList.poll();
           System.out.println(myLinkedList);
       }
       }

PriorityQueue

PriorityQueue הוא לא בדיוק התור במשמעות הכללית של FIFO. הרכיבים של תור העדיפות מסודרים לפי הסדר הטבעי שלהם, או על ידי Comparator המסופק בזמן בניית התור, תלוי באיזה קונסטרוקטור נעשה שימוש. עם זאת, זה לא סדר כמו שהוא יכול להיות במבנה ליניארי כגון רשימה (מהגדול לקטן ביותר או להיפך). תור עדיפות המבוסס על ערימה מינימלית של עדיפות. ערימה היא מבנה נתונים המבוסס על עץ בינארי . העדיפות של כל הורה גדולה יותר מסדר העדיפויות של ילדיו. עץ נקרא בינארי מוחלט אם לכל הורה אין יותר משני ילדים, ומילוי הרמות עובר מלמעלה למטה (מאותה רמה - משמאל לימין). ערימה בינארית מארגנת את עצמה מחדש בכל פעם שאלמנט חדש מתווסף או מוסר ממנה. במקרה של ערימה קטנה, האלמנט הקטן ביותר הולך לשורש ללא קשר לסדר ההחדרה שלו. תור עדיפות מבוסס על ערימה מינימלית זו, כך שאם יש לנו PriorityQueue של מספרים שלמים, האלמנט הראשון שלו יהיה הקטן מבין המספרים הללו. אם תמחק את השורש, הקטן הבא יהפוך לשורש.

שיטות תור עדיפות עיקריות:

• boolean add(object) מכניס את האלמנט שצוין לתור העדיפות. מחזיר נכון במקרה של הצלחה. אם התור מלא, השיטה זורקת חריגה.
• boolean offer(object) מכניס את האלמנט שצוין לתור העדיפות הזה. אם התור מלא, השיטה מחזירה false.
• boolean remove(object) מסיר מופע בודד של הרכיב שצוין מהתור הזה, אם הוא קיים.
• Object poll() מאחזר ומסיר את ראש התור הזה. מחזירה null אם התור ריק.
• void clear() מסיר את כל האלמנטים מתור העדיפות.
• Object element() מאחזר את ראש התור הזה מבלי להסיר אותו. זורק NoSuchElementException אם התור ריק.
• Object peek() מאחזר את ראש התור מבלי להסיר אותו. מחזירה null אם התור ריק.
• boolean contains(Object o) מחזירה true אם התור מכיל את האלמנט o.
• int size() מחזירה את מספר האלמנטים בתור זה.

דוגמה ל-PriorityQueue

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
   public static void main(String[] args) {

       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();

       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }

       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval):
1
2
3
4
5

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

ArrayBlockingQueue

מבנה הנתונים הפנימי של ArrayBlockingQueue מבוסס על מערך מעגלי לאחסון אלמנטים. זהו תור טיפוסי (FIFO) במקרה שבו אלמנטים חדשים יוכנסו בזנב התור, ופעולות חילוץ מחזירות אלמנט מראש התור. לאחר שנוצרה לא ניתן לשנות את קיבולת התור. ניסיונות להכניס (להכניס) אלמנט לתור מלא מובילים לחסימת הזרימה; ניסיון לקחת אלמנט מתור ריק גם חוסם את השרשור. כפי שאמרנו קודם, מערך זה הוא מעגלי. כלומר, האלמנט הראשון והאחרון של המערך מטופלים באופן לוגי סמוך. התור מקדם את המדדים של רכיבי הראש והזנב בכל פעם שאתה מכניס את האלמנטו לתור או מסיר אותו מהתור. אם אינדקס כלשהו מקדם את האלמנט האחרון של המערך, הוא מתחיל מחדש מ-0. לפיכך, התור לא צריך להזיז את כל האלמנטים במקרה של הסרת הראש (כמו במערך הרגיל). עם זאת, במקרה של הסרת אלמנט מהאמצע (באמצעות Iterator.remove), האלמנטים מוזזים. ArrayBlockingQueue תומך במדיניות הוגנות נוספת עם פרמטר הוגן בקונסטרוקטור להזמנת עבודת זרימות המתנה של יצרנים (הכנסת אלמנטים) וצרכנים (חילוץ אלמנטים). כברירת מחדל, ההזמנה אינה מובטחת. עם זאת, אם התור נוצר עם "fair == true", היישום של המחלקה ArrayBlockingQueue מספק גישה לשרשור בסדר FIFO. הון עצמי מפחית בדרך כלל את רוחב הפס, אך גם מפחית את התנודתיות ומונע אוזל של משאבים.

בוני כיתות ArrayBlockingQueue

• ArrayBlockingQueue (קיבולת אינט) יוצרת תור של קיבולת קבועה ועם מדיניות גישה כברירת מחדל.
• ArrayBlockingQueue (קיבולת אינט, בוליאני הוגן) יוצר תור עם קיבולת קבועה ומדיניות גישה מוגדרת.
• ArrayBlockingQueue (int capacity, Boolean fair, Collection <? extends E> c) יוצר תור עם קיבולת קבועה שצוינה במדיניות הגישה וכולל אלמנטים בתור.

כאן יש לנו את הדוגמה של BlockingQueueExample. אנו יוצרים תור של ArrayBlockingQueue עם קיבולת של אלמנט אחד ודגל הוגן. נפתחים שני שרשורים. הראשון שבהם, Producer thread, מעמיד בתורים הודעות ממערך ההודעות בשיטת put. השרשור השני, Consumer, קורא אלמנטים מהתור באמצעות שיטת take ומציג אותם במסוף. סדר האלמנטים הוא זה הטבעי לתור.

import java.util.concurrent.*;

public class ArrayBlockingQueueExample {

   private BlockingQueue<Integer> blockingQueue;
   private final Integer[]  myArray = {1,2,3,4,5};

       public ArrayBlockingQueueExample ()
       { blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
           (new Thread(new Producer())).start();
           (new Thread(new Consumer())).start();
       }

       class Producer implements Runnable
       {
           public void run() {
               try {
                   int counter = 0;
                   for (int i=0; i < myArray.length; i++) {
                       blockingQueue.put(myArray[i]);
                       if (counter++ < 2)
                           Thread.sleep(3000);
                   } blockingQueue.put(-1);
               }
               catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }

       class Consumer implements Runnable
       {
           public void run() {
               try {
                   Integer message = 0;
                   while (!((message = blockingQueue.take()).equals(-1)))
                       System.out.println(message);
               } catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }

       public static void main(String[] args) {
           new ArrayBlockingQueueExample();
       }
   }

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

התור משמש להכנסת אלמנטים בסוף התור ומסירים מתחילת התור. זה עוקב אחר תפיסת ה-FIFO.

Java Queue הוא חלק מ-Collection Framework ומיישם ממשק Collection. אז זה תומך בכל השיטות של ממשק אוסף כגון הכנסה, מחיקה וכן הלאה.

ההטמעות הנפוצות ביותר של Queue הן LinkedList, ArrayBlockingQueue ו-PriorityQueue.

הרכיבים של תור העדיפות מסודרים לפי הסדר הטבעי שלהם, או על ידי Comparator המסופק בזמן בניית התור, תלוי באיזה קונסטרוקטור נעשה שימוש.

אם מתבצעת פעולת null כלשהי על BlockingQueues, NullPointerException נזרק.