לדף הראשי
תודות
x
נספח – ממשקים-Java
 
ממשק החוליה הגנרית Node<T>
המחלקה מגדירה חוליה גנרית שבה ערך מטיפוס T והפניה לחוליה העוקבת.
הפעולה בונה חוליה. הערך של החוליה הוא x, ואין לה חוליה עוקבת 
Node (T x)
הפעולה בונה חוליה. הערך של החוליה הוא x, והחוליה העוקבת לה היא next. ערכו של next יכול להיות null
Node (T x, Node<T> next)
הפעולה מחזירה את הערך של החוליה
T getInfo()
הפעולה מחזירה את החוליה העוקבת. אם אין חוליה עוקבת, הפעולה מחזירה null
Node<T> getNext()
הפעולה משנה את הערך השמור בחוליה ל-x.
void setInfo (T x)
הפעולה משנה את החוליה העוקבת ל-next. ערכו של next יכול להיות null
void setNext (Node<T> next)
הפעולה מחזירה מחרוזת המתארת את החוליה
String toString()
 
יעילות הפעולות
יעילות הפעולות נקבעת על פי המחלקה Node המופיעה בפרק 7 – ייצוג אוספים (ראו סעיף ב.5.).
כל הפעולות מתבצעות בסדר גודל קבוע, O(1).

ממשק המחלקה מחסנית  Stack<T>
המחלקה מגדירה טיפוס אוסף בעל פרוטוקול LIFO להכנסה והוצאה של ערכים.
הפעולה בונה מחסנית ריקה  
Stack()
הפעולה מחזירה `אמת` אם המחסנית הנוכחית ריקה, `שקר` אחרת
boolean isEmpty()
הפעולה מכניסה את הערך x לראש המחסנית הנוכחית (דחיפה)
void push (T x)
הפעולה מוציאה את הערך שבראש המחסנית הנוכחית ומחזירה אותו (שליפה).
הנחה: המחסנית הנוכחית אינה ריקה
T pop()
הפעולה מחזירה את הערך שבראש המחסנית הנוכחית מבלי להוציאו.
הנחה: המחסנית הנוכחית אינה ריקה
T top()
הפעולה מחזירה תיאור של המחסנית, כסדרה של ערכים, במבנה הזה (x1 הוא האיבר שבראש המחסנית):
[x1, x2, …, xn]
String toString()
 
 
יעילות הפעולות
יעילות הפעולות נקבעת על פי המחלקה Stack המופיעה בפרק 8 – מחסנית ותור. המחלקה מיוצגת בעזרת שרשרת חוליות (ראו סעיף ה.3.).
כל הפעולות מתבצעות בסדר גודל קבוע, O(1), למעט הפעולה toString() המתבצעת בסדר גודל לינארי.
 
 
ממשק המחלקה תור  Queue<T>
המחלקה מגדירה טיפוס אוסף עם פרוטוקול FIFO להכנסה והוצאה של ערכים.  
הפעולה בונה תור ריק  
Queue()
הפעולה מחזירה `אמת` אם התור הנוכחי ריק, ו`שקר` אחרת
boolean isEmpty()
הפעולה מכניסה את הערך x לסוף התור הנוכחי
void insert (Tx)
הפעולה מוציאה את הערך שבראש התור הנוכחי ומחזירה אותו.
הנחה: התור הנוכחי אינו ריק
T remove()
הפעולה מחזירה את ערכו של האיבר שבראש התור מבלי להוציאו.
הנחה: התור הנוכחי אינו ריק
T head()
הפעולה מחזירה מחרוזת המתארת את התור כסדרה של ערכים, במבנה הזה (x1 הוא האיבר שבראש התור):
 [x1, x2, …, xn]
String toString()
 
 
יעילות הפעולות
יעילות הפעולות נקבעת על פי המחלקה Queue המופיעה בפרק 8 – מחסנית ותור. המחלקה מיוצגת בעזרת שרשרת חוליות והפניה לזנב התור (ראו סעיף ט.2.).  
כל הפעולות מתבצעות בסדר גודל קבוע, O(1), למעט הפעולה toString() המתבצעת בסדר גודל לינארי.
 
 
 
 
ממשק המחלקה רשימה List<T>
המחלקה מגדירה אוסף סדרתי-לינארי, שהגישה אל ערכיו מתבצעת בכל מקום באוסף.
הפעולה בונה רשימה ריקה
List()
הפעולה מחזירה `אמת` אם הרשימה הנוכחית ריקה, ו`שקר` אחרת
boolean isEmpty()
הפעולה מחזירה את המקום של החוליה הראשונה ברשימה הנוכחית. אם הרשימה ריקה, הפעולה מחזירה null
Node<T> getFirst()
הפעולה מכניסה לרשימה הנוכחית את הערך x מקום אחד אחרי המקום pos.
אם pos הוא  x ,null יוכנס למקום הראשון ברשימה. הפעולה מחזירה את המקום של החוליה החדשה שהוכנסה.
הנחה: pos הוא מקום ברשימה הנוכחית או  null
Node<T> insert (Node<T> pos, T x)
 
הפעולה מוציאה מהרשימה הנוכחית את האיבר הנמצא במקום pos, ומחזירה את המקום העוקב ל-pos. אם הוצא האיבר האחרון – יוחזר null.
הנחה: pos הוא מקום ברשימה הנוכחית, ואינו null.  
Node<T> remove (Node<T> pos)
הפעולה מחזירה תיאור של הרשימה, כסדרה של ערכים, במבנה הזה (x1 הוא האיבר הראשון ברשימה):
[x1, x2, …, xn]
String toString()
 
 
יעילות הפעולות
יעילות הפעולות נקבעת על פי המחלקה List המופיעה בפרק 9 – רשימה. המחלקה מיוצגת בעזרת שרשרת חוליות (ראו סעיף ד).  
כל הפעולות מתבצעות בסדר גודל קבוע, O(1), למעט הפעולות toString() ו-remove(...) המתבצעות בסדר גודל O(n).
 
ממשק המחלקה חוליה בינריתBinTreeNode<T>
המחלקה מגדירה חוליה בינרית שבה ערך מטיפוס T ושתי הפניות לחוליות בינריות.
הפעולה בונה חוליה בינרית. ערך החוליה הוא x וערך שתי ההפניות שלה הוא null
BinTreeNode (T x)
הפעולה בונה חוליה בינרית שערכה יהיה x.
 left ו-right הן (הפניות אל) הילד השמאלי והימני שלה. ערכי ההפניות יכולים להיות null
BinTreeNode (BinTreeNode<T> left,
                   T x, BinTreeNode<T> right)
הפעולה מחזירה את הערך של החוליה
T getInfo()
הפעולה משנה את הערך השמור בחוליה ל-x
void setInfo (T x)
הפעולה מחזירה את הילד השמאלי של החוליה. אם אין ילד שמאלי הפעולה מחזירה null
BinTreeNode<T> getLeft()
הפעולה מחזירה את הילד הימני של החוליה. אם אין ילד ימני הפעולה מחזירה null
BinTreeNode<T> getRight()
הפעולה מחליפה את הילד השמאלי בחוליה left
void setLeft (BinTreeNode<T> left)
הפעולה מחליפה את הילד הימני בחוליה right
void setRight (BinTreeNode<T> right)
הפעולה מחזירה מחרוזת המתארת את הערך השמור בחוליה
String toString()
 
 
יעילות הפעולות
יעילות הפעולות נקבעת על פי המחלקה BinTreeNode המופיעה בפרק 10 – עץ בינרי (ראו סעיף ג.2.).
כל הפעולות מתבצעות בסדר גודל קבוע, O(1).

ממשק המחלקה מפה Map<V>
המחלקה מגדירה אוסף דינמי הממפה מפתחות וערכים. המפתחות במפה יהיו מטיפוס מחרוזת בעוד הערכים יהיו גנריים.
הפעולה בונה מפה ריקה
Map()
הפעולה מחזירה את הערך הקשור למפתח key. הפעולה מחזירה null אם המפתח אינו קיים במפה
V getValue (String key)
הפעולה מוסיפה למפה הנוכחית את המפתח key ואת הערך value הקשור אליו. אם המפתח key קיים במפה, הפעולה מעדכנת את הערך הקשור אליו בערך value שהתקבל
void insert (String key, V value)
הפעולה מוציאה מהמפה הנוכחית את המפתח key ואת הערך הקשור אליו. הפעולה מחזירה את הערך הקשור למפתח שהוצא מהמפה. אם המפתח אינו קיים במפה היא מחזירה null 
V remove (String key)
הפעולה מחזירה את אוסף המפתחות שקיימים במפה הנוכחית ממוין בסדר אלפביתי עולה. אם המפה ריקה, יוחזר מערך בגודל אפס
String[] getAllKeys()
הפעולה מחזירה מחרוזת המתארת את המפה כך:
[key1:value1, key2:value2, key3:value3,…]
String toString()
 
 
יעילות הפעולות
יעילות הפעולות נקבעת על פי המחלקה Map המופיעה בפרק 11 – מפה. המחלקה מיוצגת בעזרת עץ-חיפוש-בינרי (ראו סעיף ד.3.).  
O(1)
Map()
O(log n) במקרה הממוצע
O(n)   במקרה הגרוע
V getValue (String key)
O(log n) במקרה הממוצע
O(n)   במקרה הגרוע
void insert (String key, V value)
O(log n) במקרה הממוצע
O(n)   במקרה הגרוע
V remove (String key)
O(n)
String[] getAllKeys()
O(n)
String toString()