Αποστολέας Θέμα: ΔΕΙΚΤΕΣ ΟΥΡΑΣ  (Αναγνώστηκε 2242 φορές)

anasta

  • Βετεράνος
  • ****
  • Μηνύματα: 59
  • Ok, yes... Ok, yes...
ΔΕΙΚΤΕΣ ΟΥΡΑΣ
« στις: 29 Μάι 2007, 07:49:50 μμ »
Για ποιες τιμές των δεικτών της ουράς (εμπρός-πίσω) η ουρά είναι άδεια;

όταν εμπρός=πίσω τότε έχει ένα στοιχείο;
όταν εμπρός>πίσω τότε είναι άδεια;

Laertis

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 1521
  • Sky's the limit
    • ΑΣΚΗΣΕΙΣ-ΘΕΜΑΤΑ ΑΕΠΠ
Απ: ΔΕΙΚΤΕΣ ΟΥΡΑΣ
« Απάντηση #1 στις: 29 Μάι 2007, 09:22:29 μμ »
Ακριβώς όπως το είπες  ;)

Όταν ο δείκτης εμπρός γίνει ίσος με τον πίσω , απαγορεύουμε την εξαγωγή για να μη συμβεί εμπρός > πίσω και αδειάσει η ουρά, οπότε δεν υπάρχει πλέον δομή .
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5666
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: ΔΕΙΚΤΕΣ ΟΥΡΑΣ
« Απάντηση #2 στις: 29 Μάι 2007, 10:36:38 μμ »
Γιώργο το τελευταίο δε νομίζω ότι είναι σωστό, μια άδεια ουρά εξακολουθεί να είναι ουρά.
Παρομοίωση με ουρά τράπεζας: είναι σαν να λέμε ότι ο ταμίας δεν θα εξυπηρετήσει τον τελευταίο πελάτη, για να ξέρουν οι επόμενοι που θα μπουν στην τράπεζα που είναι η ουρά αναμονής! :)
Ή, σαν να λέμε ότι μια βάση mysql δεν είναι βάση επειδή δεν έχει μέσα εγγραφές (ενώ έχουμε ορίσει πίνακες κτλ).

Τέλος, αν και δεν αναφέρεται στο βιβλίο, όλες οι ουρές είναι "κυκλικές", δηλαδή αφού τελειώσουν οι Ν θέσεις της οι δείκτες θα ξαναγυρίσουν από την αρχή. Έτσι δεν μπορούμε να βασιστούμε στον χαρακτηρισμό εμπρός = πίσω + 1, θα έπρεπε να βάλουμε mod N στην εξίσωση. Οπότε και για να μείνουμε εντός ύλης ας πούμε απλά ότι το εμπρός > πίσω δεν σημαίνει αναγκαστικά ότι η ουρά είναι άδεια.

Laertis

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 1521
  • Sky's the limit
    • ΑΣΚΗΣΕΙΣ-ΘΕΜΑΤΑ ΑΕΠΠ
Απ: ΔΕΙΚΤΕΣ ΟΥΡΑΣ
« Απάντηση #3 στις: 30 Μάι 2007, 03:04:49 μμ »
Αντιστρέφω το παράδειγμα Άλκη
Δηλαδή αντίστοιχα με το παράδειγμα προσομοίωσης , δε θα πρέπει να πλύνω το τελευταίο πιάτο απο τη στοίβα που μου άφησε η γυναίκα μου  γιατί θα πρέπει να στοιβάξω τα επόμενα άπλυτα πιάτα ; :) Αυτό μας λέει η στοίβα .

Επίσης όταν πας στην τράπεζα και δε δεις κανένα στο ταμείο (και φυσικά χαίρεσαι) λες ότι έχει ουρά ; Κι όταν κλείσει η τράπεζα η ουρά υπάρχει για τους αυριανούς ;  :)

Αυτό που νομίζω είναι ότι ,στην καθημερινή ζωή οι ουρές και στοίβες δημιουργούνται ή εξαφανίζονται χρονικά, δεν υπάρχουν ως "εν δυνάμει" δομές για μελλοντική χρήση.

Προφανώς οι ουρές είναι κυκλικές και πρέπει να επανέρχονται στην αρχή όταν γεμίσει η ουρά ή (για να γίνει αυτό που λες) όταν εμπρός < πίσω κάτι που δε λέει το βιβλίο. 
Το βιβλίο λέει σαφώς  σελ.61:

Σε κάθε περίπτωση όμως, πρέπει να ελέγχεται πριν απο οποιαδήποτε ενέργεια, αν υπάρχει ελεύθερος χώρος στον πίνακα για την εισαγωγή και αν υπάρχει τουλάχιστον ένα στοιχείο για την εξαγωγή

Αυτό που καταλαβαίνω εγώ είναι ότι όταν εξαχθεί και το τελευταίο στοιχείο απο την ουρά παύει να υφίσταται ουρά. Δες το και απο φιλοσοφικής άποψης ... :)
Ίσως και να κάνω λάθος ...
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

anasta

  • Βετεράνος
  • ****
  • Μηνύματα: 59
  • Ok, yes... Ok, yes...
Απ: ΔΕΙΚΤΕΣ ΟΥΡΑΣ
« Απάντηση #4 στις: 30 Μάι 2007, 07:22:20 μμ »
όταν λέμε οτι η ουρά είναι άδεια εννούμε οτι δεν έχει στοιχεία για εξαγωγή,
όχι οτι δεν μπορείς να την χρησιμοποιήσεις για εισαγωγή,
υπάρχει στην μνήμη του υπολογιστή.
όταν συμβεί εμπρός>πίσω τότε αρχικοποιείς πάλι τους δείκτες ώστε να μπορεί να χρησιμοποιηθεί η ουρά.

δεν έχει τύχει να χρησιμοποιήσω ποτέ κυκλική ουρά, αλλά κυκλική λίστα.

επίσης όταν ο πίσω δείκτης έχει τιμή ίση με το μέγεθος της ουράς, αλλά ο εμπρός δεν έχει την τιμή 1,
δηλαδή δεν έχει ελεύθερη θέση στο τέλος για εισαγωγή αλλά έχει κενές θέσεις που έχουν δημιουργηθεί από εξαγωγές στοιχείων, τότε κάνουμε αναδιοργάνωση στην ουρά, δηλαδή μεταφέρουμε τα στοιχεία στις πρώτες θέσεις διατηρώντας φυσικά την σειρά των στοιχείων και ενημερώνοντας κατάλληλα τους δείκτες.

ολα αυτά ομως ξεφεύγουν πολύ απο την ύλη του μαθήματος.
απλά μία επιβεβαίωση για ένα σωστό-λάθος ήθελα.

σας ευχαριστώ!!!!!!

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5666
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: ΔΕΙΚΤΕΣ ΟΥΡΑΣ
« Απάντηση #5 στις: 30 Μάι 2007, 10:16:38 μμ »
Ξεκίνησα να υλοποιήσω και να ανεβάσω την κλασσική (κυκλική) υλοποίηση ουράς με πίνακα.
Μετά σκέφτηκα να κοιτάξω το βιβλίο καθηγητή: στη σελίδα 87 δίνει τους αλγόριθμους εισαγωγής και εξαγωγής.

Δυστυχώς, οι αλγόριθμοι που προτείνει είναι υπεραπλουστευμένοι, τόσο που τελικά είναι λανθασμένοι. Αυξάνει διαρκώς τους δείκτες προς τα δεξιά χωρίς να κάνει κύκλο (mod N), και έτσι όταν το πίσω γίνει ίσο με το μέγεθος του πίνακα, θεωρεί ότι η ουρά γέμισε, ακόμα κι αν έχουν εξαχθεί αρκετά στοιχεία και η ουρά είναι άδεια.
Δεν ασχολείται καν να ξανααρχικοποιήσει τους δείκτες της ουράς . Αυτό βέβαια θα ήταν λάθος, θα έπρεπε πρώτα να μεταφέρει τα υπάρχοντα στοιχεία στην αρχή του πίνακα. Αλλά και η μεταφορά θα ήταν (λίγο?) λάθος, θα χάλαγε όλο το concept της ουράς (το Ο(1) που υποτίθεται ότι έχει η ουρά κατά την εισαγωγή - εξαγωγή).

Κατά την εξαγωγή επιτρέπει στην ουρά να μην έχει κανένα στοιχείο, οπότε  σ' αυτό το σημείο τουλάχιστον συμφωνώ με το βιβλίο (ότι επιτρέπεται να αδειάσει τελείως μια ουρά).

Εν τέλει, προσωπική μου γνώμη είναι ότι αν δεν διορθώσουν τουλάχιστον το βιβλίο καθηγητή, κάθε περαιτέρω συζήτηση (περί κύκλων, ορίων, πίσω <= μπροστά κτλ) είναι μάταιη...