Deques in Java

Συζητήσεις για την Java

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
Άβαταρ μέλους
Paralias
Δημοσιεύσεις: 82
Εγγραφή: 29 Ιαν 2005 20:00

Deques in Java

Δημοσίευση από Paralias » 05 Δεκ 2007 14:36

Απ'τη σχολή μας έχουν βάλει αυτή την εργασία...
Μπορεί να βοηθήσει κάποιος;

Η εκφώνηση είναι η εξής:
Δημιουργήστε έναν αφηρημένο τύπο δεδομένων (ΑΔΤ) για διπλές ουρές (deques),
δηλαδή ουρές με «διπλά άκρα» με δύο διαφορετικές υλοποιήσεις. Ο σκοπός της
εργασίας αυτής είναι να υλοποιήσετε βασικές δομές δεδομένων χρησιμοποιώντας
πίνακες και συνδεδεμένες λίστες και να ασκηθείτε στον προγραμματισμό με Java.
Double-ended queue ή deque -- Ουρά με διπλά άκρα: Είναι μια γενίκευση της
συνηθισμένης ουράς που επιτρέπει εισαγωγή και αφαίρεση στοιχείων και από τα δύο
άκρα της δομής. Δημιουργήστε δύο υλοποιήσεις του ΑΔΤ deque με τις εξής πράξεις

Κώδικας: Επιλογή όλων

public interface Deque<Item> &#123;
public Deque&#40;&#41; // construct an empty deque
public boolean isEmpty&#40;&#41; // return true if the queue is empty,
// false otherwise
public void addFirst&#40;Item item&#41; // insert the item at the front of the
// queue
public void addLast&#40;Item item&#41; // insert the item at the end of the queue
public Item removeFirst&#40;&#41; // delete and return the first item in the
// queue
public Item removeLast&#40;&#41; // delete and return the last item in the
// queue
public Item getFirst&#40;&#41; // return the first item in the
// queue
public Item getLast&#40;&#41; //return the last item in the
// queue
&#125;
Κάθε πράξη θα ολοκληρώνεται το πολύ σε χρόνο Ο(1) (στην χειρότερη περίπτωση,
εκτός από τον διπλασιασμό πίνακα). Δημιουργήστε exceptions για κάθε περίπτωση που
χρειάζεται, π.χ. αν η ουρά είναι άδεια και επιχειρείτε να επιστρέψετε κάποιο στοιχείο.
Κάνετε 2 διαφορετικές υλοποιήσεις του ΑΔΤ Deque: μία χρησιμοποιώντας
συνδεδεμένες λίστες και μία χρησιμοποιώντας πίνακες. Χρησιμοποιήσετε generics για
να δημιουργήσετε δομές γενικής χρήσης.
Η πρώτη υλοποίηση θα βασίζεται σε διπλά συνδεδεμένες λίστες. Χρησιμοποιήστε:
public class DequeLinkedList<Item> implements Deque<Item> { ... }
Η δεύτερη υλοποίηση θα χρησιμοποιεί πίνακες. Αν ποτέ ο πίνακας γεμίσει
χρησιμοποιήστε την στρατηγική του διπλασιασμού για να διπλασιάσετε το μέγεθος του
πίνακα. Χρησιμοποιήστε:
public class DequeArray<Item> implements Deque<Item> { ... }

Άβαταρ μέλους
Paralias
Δημοσιεύσεις: 82
Εγγραφή: 29 Ιαν 2005 20:00

Deques in Java

Δημοσίευση από Paralias » 06 Δεκ 2007 21:23

Παιδιά την πρώτη υλοποίηση με τις συνδεδεμένες λίστες την έκανα.Μπορεί κανείς να βοηθήσει στην υλοποίηση με πίνακα;

Απάντηση

Επιστροφή στο “Java”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες