Υπερχείλιση / Υποχείλιση Στοίβας - Ουράς

Ξεκίνησε από Επισκέπτης, 15 Μαρ 2006, 10:09:33 ΜΜ

« προηγούμενο - επόμενο »

Επισκέπτης

Το λάθος της Υπερ/υπο-χείλισης αναφέρεται στο βιβλίο μόνο για τη στοίβα.

Το ίδιο δε μπορεί να συμβεί και σε ουρά; (εισαγωγή σε γεμάτη / εξαγωγή από άδεια);;  Γιατί να το περιορίσουμε στη στοίβα;


Λάμπρος Μπουκουβάλας

η υπερχείλιση αναφέρεται στο βιβλίο σε συνδυασμό με την λειτουργία της μνήμης του υπολογιστή ως στοίβας. έχεις δει σε υπολογιστή το μήνυμα λάθους stack overflow, αλλά δεν έχεις δει το μήνυμα out of queue. Μήπως κάτι σημαίνει αυτό?
Λάμπρος Μπουκουβάλας
MSc - MRes

http://blogs.sch.gr/lambrosbouk

Ο Θουκυδίδης  (που τον διαβάζουν οι ξένοι, αλλά όχι εμείς)  έγραφε: «Αταλαίπωρος τοις πολλοίς η ζήτησις της αληθείας, και επί τα ετοίμα μάλλον τρέπονται» (Ι, 20, 3). Οι περισσότεροι δηλαδή αναζητούν αβασάνιστα την αλήθεια και στρέφονται σε ό,τι βρίσκουν έτοιμο. Δεν προβληματίζονται...

filippos

Η εισαγωγή σε γεμάτη ουρά είναι εξίσου λάθος με την ώθηση σε γεμάτη στοίβα.

Όμοια, η εξαγωγή από κενή ουρά είναι εξίσου λάθος με την απώθηση από κενή στοίβα.

Γι' αυτό το λόγο γενικά οι αλγόριθμοι που υλοποιούν αυτές τις 4 λειτουργίες οφείλουν να ελέγχουν γι' αυτές τις καταστάσεις.

Έχω όμως την αίσθηση ότι οι όροι υπερχείλιση (overflow) και υποχείλιση (underflow) χρησιμοποιούνται μόνο σε στοίβα και όχι σε ουρά.  Δεν είμαι όμως και απόλυτα σίγουρος.

Οι υπόλοιποι τι λέτε;

Θα μπορούσε να τεθεί ερώτηση Σωστό/Λάθος με τη μορφή:
1. η εξαγωγή από κενή ουρά προκαλεί υποχείλιση
ή / και
2. η εισαγωγή σε γεμάτη ουρά προκαλεί υπερχείλιση

Τι πρέπει να απαντήσουν οι μαθητές

andreas_p

Δε νομίζω να πέσει τέτοια ερώτηση. Αν πέσει  θα πρέπει να λάβουμε κάθε απάντηση ως Σωστή.

Λάμπρος Μπουκουβάλας

o filippos έχει δίκιο. οι έννοιες υπερχείλιση και υποχείλιση ισχύουν μόνο για στοίβα. κατά τη γνώμη μου η απάντηση στην ερώτησή σου είναι ΛΑΘΟΣ. δεν αναφέρει το βιβλίο τις αντίστοιχες λειτουργίες της ουράς.
Λάμπρος Μπουκουβάλας
MSc - MRes

http://blogs.sch.gr/lambrosbouk

Ο Θουκυδίδης  (που τον διαβάζουν οι ξένοι, αλλά όχι εμείς)  έγραφε: «Αταλαίπωρος τοις πολλοίς η ζήτησις της αληθείας, και επί τα ετοίμα μάλλον τρέπονται» (Ι, 20, 3). Οι περισσότεροι δηλαδή αναζητούν αβασάνιστα την αλήθεια και στρέφονται σε ό,τι βρίσκουν έτοιμο. Δεν προβληματίζονται...

evry


   Το ότι δεν αναφέρει το βιβλίο τo underflow/overflow ουράς δε σημαίνει ότι δεν υπάρχει. Αφού μιλάμε για έναν πίνακα με περιορισμένο αριθμό θέσεων είναι προφανές ότι στις οριακές περιπτώσεις συμβαίνει ότι και στη στοίβα.
    Ο λόγος που το βιβλίο αναφέρει μόνο τη στοίβα είναι ότι η δομή αυτή χρησιμοποιείται αρκετά από τα λειτουργικα συστήματα και από τις γλώσσες προγραμματισμού όπως για παράδειγμα στη μεταβίβαση παραμέτρων όπου το σχολικό βιβλίο αφιερώνει μια σελίδα στη στοίβα.
     Μπορείτε να ρίξετε μια ματιά σε οποιοδήποτε σοβαρό βιβλίο για δομές δεδομένων ή ακόμα και στη σχετική σελίδα της wikipedia
http://en.wikipedia.org/wiki/Queue
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Επισκέπτης

@Evry: Το θέμα δεν είναι κατά πόσον είναι λάθος η εισαγωγή σε γεμάτη ουρά ή η εξαγωγή από άδεια.  Σε αυτό νομίζω συμφωνούμε όλοι. 

Το θέμα είναι κατά πόσον είναι δόκιμος ο όρος υπερ/υπο-χείλιση (οver/under-flow) στις ουρές.  Το βιβλίο αναφέρει τους όρους μόνο στη στοίβα, και η δική μου αίσθηση είναι επίσης ότι το πρόβλημα περιγράφεται μεν ως stack overflow error στις στοίβες αλλά ως queue full error στις ουρές. 

Αν λοιπόν θυμάμαι καλά, ο υπο συζήτηση όρος αφορά μόνο τη στοίβα

evry

Πάντως για να λέει το παρακάτω στο wikipedia (όχι ότι το θεωρώ και ευαγγέλιο) κάτι θα ξέρει

A practical implementation of a queue of course does have some capacity limit, that depends on the concrete situation it is used in. For a data structure the executing computer will eventually run out of memory, thus limiting the queue size. Queue overflow results from trying to add an element onto a full queue and queue underflow happens when trying to remove an element from an empty queue

Επίσης αν βάλεις "queue overflow in data structures" στο google θα βγουν αρκετές σελίδες του μαθήματος δομών δεδομένων σε πολλά πανεπιστήμια. Οπότε ο όρος χρησιμοποιείται από αρκετούς. Ίσως κάποιοι να προτιμουν κάποιον άλλο όρο για την ουρά για να μην γίνεται σύγχυση με τη στοίβα αλλά το queue overflow δε νομίζω ότι είναι λάθος.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

P.Tsiotakis


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

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

Με εκτίμηση,