אהלן,

אני מנסה ליצור Deque בjava אבל יש לי בעיות עם popFront()

(אני לא יכול להשתמש בספריות המובנות)

זה מה שיש לי כרגע

  public E popFront() throws DequeException
  {
    if ( isEmpty() )
      throw new DequeException("Non-empty deque expected in call to popFront().");

    Node tmpNode = new Node();
    tmpNode.data = head.data;

    if ( size() == 1)
      head = rear = null;
    else
    {
    .
    .
    .
    }
     length--;
     return tmpNode.data;
 }

אשמח אם מישהו יוכל להשלים את החסר/לעזור כי אני כבר משתגע. (לא פרסמתי את הקוד שיש לי שם כי הוא פשוט לא נכון)

בעיקרון צריך לסדר שם את הרפרנטציות.

תודה!

head הוא איבר של המחלקה?

כל מה שאתה צריך לעשות זה head = head.next (אפילו לא צריך בשביל זה לבדוק אם הרשימה בגודל 1).

שים לב שזה לא queue, זהDeque

כלומר doubly-ended-queue

לכל איבר יש מצביע next ומצביע prev

במקרה הזה, הprev של הראשון ברשימה מצביע לאחרון והnext של האחרון הרשימה מצביע לראשון.

לכל הרשימה יש איבר ראשון ואחרון (head + rear) ומונה של הגודל שלה.

הבעיה שלי היא לנתק את האיבר הראשון לחלוטין ולקשר את האחרון לheadהבא בתור וגם להגדיר אותו כhead החדש כמובן

ובמקביל לנתק את הhead (הישן) ממה שהוא מצביע אליו.

אני מקווה שההסבר שלי ברור :-X

ותודה על העזרה

כל מה שאתה צריך הוא קצת יותר להתאמץ, משהו בסגנון:

head = head.next;
head.prev = rear;
rear.next = head;

חוץ מזה, ממתי ב-deque צריך לקשר בין האיבר הראשון והאחרון? אתה לא מתבלבל עם רשימה מעגלית?

למיטב זכרוני, deque זה פשוט תור שאפשר להוציא ולהכניס איברים משני קצותיו (בניגוד לתור רגיל שאפשר רק להכניס מצד אחד ולהוציא מהצד השני).

האמת היא שזה בדיוק הקוד שאני כתבתי..

להלן פלט לדוגמא:

How many numbers do you wish to enter in the deque? 
4
Enter 4 fixed-point values and then press the [Enter] key> 
1 2 3 4
1 has been inserted at the front of the deque.
1 has been inserted at the back of the deque.
The deque has 2 elements.
2 has been inserted at the front of the deque.
4 has been inserted at the back of the deque.
The deque has 4 elements.
3 has been inserted at the front of the deque.
9 has been inserted at the back of the deque.
The deque has 6 elements.
4 has been inserted at the front of the deque.
16 has been inserted at the back of the deque.
The deque has 8 elements.


4 has been deleted from the front of the deque.
16 has been deleted from the back of the deque.
The deque has 6 elements.
16 has been deleted from the front of the deque.
16 has been deleted from the back of the deque.
The deque has 4 elements.
16 has been deleted from the front of the deque.
16 has been deleted from the back of the deque.
The deque has 2 elements.
16 has been deleted from the front of the deque.
16 has been deleted from the back of the deque.
The deque has 0 elements.

אני אמור להסיר איבר מהסוף ומההתחלה עד שהרשימה ריקה.

חשבתי שהבעיה היא בהוספה של האיברים אבלכנראה שהבעיה היא בחלק אחר של הקוד.

לגבי רשימה מעגלית או לא, הנה ההוראות:

Your task in this project is to implement a generic

doubly-ended queue (deque). A queue is not always the appropriate for some

problems. You will implement a variant of the queue called doubly-ended-

queue (Deque). This implementation of a deque consists of doubly-linked

dynamically allocated nodes. In addition to the standard queue operations,

a dequeue has a popBack method, that removes the element from the back,

and a pushFront method that inserts an element at the front of the queue.

A good ADT design principle is to view data abstraction as an application

of the principle of least commitment. So the interface provided makes no

assumption about the type of data that the Deque will contain. That is, the

Deque class parameterized class.

עכשיו כשאני חושב על זה, למה בכלל pop יוצר node חדש? הרי אתה רק משתמש ב-data שיש בו.

יענו:

E data = head.data;
head = head.next;
rear.next = head;
head.prev = rear;
return data;

חוץ מזה, לפי מה שאני רואה אין שום דרישה ש-head ו-rear יצביעו זה על זה. אין שום בעיה לדעתי ש-head.prev ו-rear.next יהיו null.

בכל מקרה, קצת קשה לדעת איפה בדיוק הבעיה בלי שתעלה את הקוד המלא (נראה כאילו הבעיה היא דווקא ב-popBack, או שיש לך דריכה איפשהו בהכנסה).

בהתחלה באמת שמרתי רק את ה data ולא יצרתי node חדש אבל שיניתי את זה במסגרת הנסיונות שלי למצוא את הבאג.

אני אבדוק שוב לגבי ההצבעה של האלמנטיים הקיצוניים וההצבעה ההדדית שלהם.

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

תודה רבה על העזרה

דווקא ציפיתי שתעלה רק את הקוד הרלוונטי (פונקציות push ו-pop).

טוב, צדקת. באמת אין צורך לקשר את האיבר האחרון לראשון או להיפך.

שיניתי את הקוד והבעיה נפתרה בשעה טובה.