Ερώτηση σε στοίβα-ουρά

[Λαμπράκης Μανώλης]

καλησπέρα σε όλους

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

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

στέκει αυτό σαν εξήγηση ή μου ξεφεύγει κάτι

2) επίσης σε ουρά πχ 5 θέσεων, που οι δείκτες εμπρός αι πίσω είναι στην τελευταία θέση, δεν μπορούμε να κάνουμε εισαγωγή, ακόμη και αν έχουμε θέσεις άδειες σωστά   εξαγωγή μπορούμε να κάνουμε ? ο δείκτης εμπρός θα πάρει θέση 6, εκτός πίνακα... 


ευχαριστώ

[Laertis]

Η μνήμη μπορει να περιέχει τυχαία δεδομένα. Δε νομίζω ότι είναι υποχρεωτικο να μηδενίζεις (όπως κάνουμε στους πίνακες π.χ. για να αθροίζουμε στη συνέχεια όλες τις τιμές) όταν απωθείς, απλά το αγνοείς γιατί όταν γίνει ώθηση θα αντικατασταθεί όποια τιμή υπάρχει. Οπότε σωστά το κατάλαβες.

Στην ουρά όταν ο rear φτάσει στην τελευταία θέση θα πρέπει να ελέγχεται αν υπάρχουν κενές θέσεις μπροστά (rear-front+1<n) οπότε μετακινούμε το δείκτη  front στην 1η θέση και το rear στην rear-front+1 για να μπορεί να γίνει εξαγωγή.

[gpapargi]

Για το 2:
Τα στοιχεία της ουράς δεν είναι μονής χρήσεως, προφανώς τα βάζεις μπροστά. Ουσιαστικά μιλάμε για "κυκλική ουρά". Απλά δεν το αναφέρει το βιβλίο για να μη μπλέξει το μαθητή. Αν δεν έκανες αυτό, κάθε φορά που έβγαζες κάτι από την ουρά, θα έπρεπε να μετακινείς όλα τα στοιχεία μια θέση πιο μπροστά, πράγμα που θα αύξανε το πλήθος των βημάτων που κάνει ο αλγόριθμος. Κάτι τέτοιο γίνεται στην ουρά του ταμείου που μόλις εξυπηρετηθεί ένας κάνουν όλοι ένα βήμα μπροστά. Απλά εκεί κάνουν όλοι ένα βήμα μπροστά (= παράλληλη επεξεργασία) ενώ στην ουρά που υλοποιούμε εμείς η μετακίνηση των στοιχείων γίνεται μια προς μια (= σειριακή επεξεργασία). Για να μην αυξηθεί η πολυπλοκότητα λοιπόν τα αφήνουμε όπως είναι και παίζουμε με τους δείκτες... οι οποίοι κινούνται κυκλικά.
Για το 1:
Κάπως έτσι γίνεται και η διαγραφή αρχείων στον υπολογιστή. Δε φεύγουν τα data από τους αποθηκευτικούς χώρους, απλά μαρκάρονται ως availiable. Όταν θα ζητηθεί καινούργιος χώρος μπορεί να χρησιμοποιηθεί ο συγκεκριμένος και τότε φεύγουν τα δεδομένα από τις θέσεις αφού θα κάτσουν από πάνω τα νέα δεδομένα. Και στη στοίβα που περιγράφεις, εφόσον ο δείκτης έχει πάει σε άλλη θέση το στοιχείο χάθηκε... δεν έχεις καμία πρόσβαση σε αυτό. Αν πχ είναι στη θέση 10 του πίνακα και ο δείκτης κορυφή είναι στη θέση 9 το στοιχείο είναι εκτός. Δεν επιτρέπεται να πεις Εμφάνισε α[10] γιατί τότε δε θα είναι στοίβα αυτό που έχεις. Δεν είναι επιτρεπόμενη πράξη. Οι επιτρεπόμενες πράξεις είναι να βάζεις και να βγάζεις από το δείκτη.
Επίσης δεν πρέπει να μπλέκουμε την αφηρημένη δομή δεδομένων (ΑΔΔ) της στοίβας με την υλοποίηση. Το ότι υπάρχει ένα στοιχείο στον πίνακα πέρα από το δείκτη κορυφή αφορά τη υλοποίηση, όχι την ΑΔΔ της στοίβας

[Λαμπράκης Μανώλης]

ωραία ευχαριστώ, κάτι τέτοιο είχα στο μυαλό μου....

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

ευχαριστώ

[Laertis]

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

[Λαμπράκης Μανώλης]

Καλημέρα σε όλους

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

ευχαριστώ

[Laertis]

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

[Λαμπράκης Μανώλης]

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

[P.Tsiotakis]

στην πράξη σπάνια και οι 8 λειτουργίες εφαρμόζονται σε όλες τις δομές   

[Λαμπράκης Μανώλης]

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

[Laertis]

Είναι προσπέλαση. Καλό είναι να μη το ρωτήσεις στους μαθητές, θα μπερδευτούν με την εισαγωγή, εκτος αν θέλεις να τους κάψεις