Άσκηση με στοίβες

[akalest0s]

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

[epsilonXi]

εμένα μ' αρέσει

σε κάποιον καλό μαθητή θα πρότεινα επιπλέον, στην περίπτωση που το back είναι γεμάτο και θελήσει ο χρήστης να επισκεφθεί νέα σελίδα, αντί για υπερχείλιση να έχουμε «λησμόνηση»

νέος όρος, μόλις επινοήθηκε

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

και την «λησμόνηση» να μην την κάνουν με κάποια μετακύλιση των δεδομένων στον «πίνακα», αφού δεν είναι πίνακας αλλά στοίβα, αλλά μέσω μίας τρίτης στοίβας...

[akalest0s]

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

[Σάκης Δημόπουλος]

https://www.youtube.com/watch?v=Ew5JHmpIQ20&t

[akalest0s]

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

[gthal]

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

@akalest0s ,
έχω την εντύπωση ότι η υλοποίηση της pop είναι που ξεφεύγει από αυτό που προσωπικά (και ίσως και όσοι σου είπαν για λάθος) θα ήθελα να καταλάβει ο μαθητής για την pop.
Τι εννοώ:
1) όπως η push έχει το έργο να "βάλει" κάτι μέσα στη στοίβα, έτσι και η pop έχει το έργο να "λάβει" κάτι από τη στοίβα και όχι απλά να το διαγράψει (πολύ δε περισσότερο, όχι να διαγράψει ένα πλήθος στοιχείων).
2) Επιπλέον, δες ας πούμε τι κάνεις με την εντολή ΚΑΛΕΣΕ push(ΣΤδ,τοπδ,ΣΤκ[τοπκ]) :
προσπελαύνεις άμεσα στο ΣΤκ[τοπκ] ως ένα οποιοδήποτε κελί του πίνακα, αντί να το "ζητήσεις" και να το "λάβεις" με μία pop.
Η pop θα σου έδινε πάντα το στοιχείο της κορυφής, ενώ με άμεση προσπέλαση θα μπορούσες ας πούμε να πάρεις και το ΣΤκ[τοπκ-2], πράγμα που καταστρατηγεί την ιδιότητά της ως στοίβας.
Ελπίζω να γίνεται κατανοητή η εξήγηση μου.

3) Τέλος όσον αφορά την ιδέα της άσκησης, δεν κατάλαβα γιατί ακριβώς πρέπει να υλοποιηθεί με 2 στοίβες όπου "πηγαινοφέρνουμε" στοιχεία από τη μία στην άλλη, ενώ μπορεί πολύ απλά να υλοποιηθεί με μία στοίβα;

[akalest0s]

1)  Τι εννοείς "να το λάβει, να το διαγράψει"; Η πράξη είναι η ίδια ακριβώς με του βιβλίου, η top <- top - 1. Το αν θα το πεις "διαγραψει" εννοιολογικά, ή "λάβει" ή οτιδήποτε, τι σημασία έχει; Σημασία νομίζω έχει ότι με top<-top-1, βγάζω κάτι από την στοίβα.
Όσο για το πλήθος στοιχείων, το μόνο που αλλάζω είναι να επαναλαμβάνω την ίδια, ολόκληρη την λειτουργία της απώθησης, όσες φορές θέλω κάθε φορά. Αν αυτό φαίνεται κακό για την γενικότητα του interface, τότε μπορείς πολύ απλά να το συμπεριλάβεις πάνω στην κλήση της pop, και όχι εντός της διαδικασίας. Νομίζω δεν είναι σημαντική αλλοίωση, αλλά το δέχομαι. Το άλλο που προανέφερα, δεν το καταλαβαίνω ως πρόβλημα, όπως το λες.

2) Η υπόδειξή σου, μου γεννά το ερώτημα: στις στοίβες/ουρές, ΜΟΝΟ pop και push επιτρέπεται; Δεν επιτρέπεται η αναφορά/προσπέλαση στο πάνω πάνω στοιχείο; Γιατί; Με όσα ξέρω από προγραμματισμό, αλλά και με όσα λέει το βιβλίο ("push και pop οι βασικές λειτουργίες", ποιες είναι οι υπόλοιπες άραγε;), το να προσπελάσεις ΜΟΝΟ την κορυφή της στοίβας, είναι perfectly fine, έγκυρη λειτουργία. Δεν πήγα κάτω από την τοπ. Πουθενά. Οπότε που είναι το θέμα και εδώ; Θα συμφωνούσα αν έκανα προσπέλαση σε οποιοδήποτε άλλο στοιχείο, αυθαίρετα. Αλλά ακόμη και το τοπ στοιχείο, απαγορεύεται να το εμφανίσουμε/προσπελάσουμε;

ενώ με άμεση προσπέλαση θα μπορούσες ας πούμε να πάρεις και το ΣΤκ[τοπκ-2]

Αυτό λέω, ότι δεν έκανα κάτι τέτοιο. Αυτό θα ήταν όντως λάθος. Όμως η τοπκ που χρησιμοποιώ εκεί, επιτρέπω πιο πριν να αλλάξει μόνο μέσα από pop και push, όχι με άλλον τρόπο.

3) Αυτό που λες εδώ, ίσως έχει να κάνει με το "λάβει"/"διαγράψει" που λέγαμε πιο πάνω. Πως, χωρίς 2 στοίβες, θα πάρεις πάλι πίσω τα στοιχεία που έβγαλες (με pop) από την στοίβα, όταν έκανες πίσω στον browser? Αφού εκείνες οι σελίδες υποτίθεται χάθηκαν από την στοίβα, κάνοντας πίσω, δηλαδή pop.
Δεν χρειάζεσαι κάποια βοηθητική δομή εκεί;

Ευχαριστώ πολύ για το χρόνο σου και περιμένω τις απαντήσεις σου!

[evry]

2) Η υπόδειξή σου, μου γεννά το ερώτημα: στις στοίβες/ουρές, ΜΟΝΟ pop και push επιτρέπεται;

Ακριβώς μόνο αυτό και τίποτα άλλο.

Δεν επιτρέπεται η αναφορά/προσπέλαση στο πάνω πάνω στοιχείο; Γιατί;

Αν θες να δεις μέσα στη στοίβα πρέπει να κάνεις απώθηση, δεν μπορείς να δεις χωρίς απώθηση. Αυτό είναι το interface αυτού του Αφηρημένου Τύπου Δεδομένων

Ωστόσο σε κάποιες υλοποιήσεις/Interface αυτό που λες επιτρέπεται, π.χ. δες εδώ:
https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
που λέει:
Additionally, a peek operation may give access to the top without modifying the stack

[akalest0s]

Καταλαβαίνεις ότι γράφεις δύο αντίθετα πράγματα; "Ακριβώς μόνο αυτό και τίποτα άλλο"... αλλά τελικά, και κάτι άλλο, το peek!
Τόσο στον προγραμματισμό γενικότερα, όσο και στα πλαίσια του μαθήματος, το peek, είναι οκ, γιατί απλά βολεύει, χωρίς να χαλάει το interface μας.

Επίσης, τότε θέλω μια εξήγηση για εκείνο το σημείο που λέει "ΚΥΡΙΕΣ λειτουργίες".. γιατί δεν λέει ΜΟΝΑΔΙΚΕΣ να είμαστε ξεκάθαροι;
Προφανώς εγώ δεν έχω κανένα πρόβλημα να συμμορφωθώ με ΜΟΝΟ τις 2 αυτές λειτουργίες, πρόβλημα έχω με το ότι αυτά θα πρέπει να είναι ξεκάθαρα στο βιβλίο, να ξέρουμε και εμείς τελικά τι πρέπει να διδάσκουμε... Κάπου έχει καταντήσει αηδία το θέμα..

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

[evry]

Δεν το διατύπωσα καλά ίσως.
Είπα ότι σε κάποιες περιπτώσεις επιτρέπεται ένα Peek για να δεις τι έχει πάνω ίσως γιατί αυτό είναι βολικό (αλλιώς θα έπρεπε να κάνεις pop+push) για συγκεκριμένες εφαρμογές.
Ωστόσο στις περισσότερες περιπτώσεις οι λειτουργίες σε μια στοίβα είναι τρεις:
1) push
2) pop
3) isEmpty
Αυτό είναι το πιο συνηθισμένο και πιο κοντά στον ορισμό της στοίβας.
Αν θέλεις μια δομή στην οποία χρειάζεται να κοιτάς το πάνω-πάνω ή άλλα στοιχεία τότε μάλλον δεν ήθελες στοίβα εξαρχής.
Ωστόσο όλα αυτά λύνονται αφού μια άσκηση μπορεί κάλλιστα να δώσει συγκεκριμένο Interface και να ζητήσει συγκεκριμένη υλοποίηση.
Το  πρόβλημα είναι ότι η χρήση στοίβας/ουράς στη ΓΛΩΣΣΑ είναι αντιπαιδαγωγική και αντιεπιστημονική διότι
1) Δεν υπάρχει διαχωρισμός interface / υλοποίησης, δηλαδή δεν έχουμε information hiding
2) Έτσι όπως παρουσιάζεται δεν μπορεί να κατανοήσει ο μαθητής τι χρειαζόμαστε τη στοίβα και όλη αυτή την πολυπλοκότητα αφού μπορεί να κάνει τα ίδια και με λιγότερο κώδικα με ένα array.

Έτσι όπως είναι το μάθημα θα έλεγα ότι μπορείς να έχεις peek σε μια στοίβα μόνο αν στο επιτρέπει η εκφώνηση, αλλιώς πρέπει να μείνεις σε push/pop.

Πάντως δεν καταλαβαίνω γιατί πρέπει να χρησιμοποιήσουμε το peek και να αναρωτιόμαστε αν θα το πάρουν σωστό και να μην χρησιμοποιήσουμε αλληλουχία pop+push = peek που είναι το ίδιο.

ΥΓ. Αυτή τη στιγμή το μάθημα έχει ξεπεράσει τις δυνατότητες της ΓΛΩΣΣΑΣ, για αυτό δημιουργούνται όλα αυτά τα προβλήματα. Να δω πότε θα το καταλάβουμε επιτέλους.

[akalest0s]

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

Πάντως δεν καταλαβαίνω γιατί πρέπει να χρησιμοποιήσουμε το peek και να αναρωτιόμαστε αν θα το πάρουν σωστό και να μην χρησιμοποιήσουμε αλληλουχία pop+push = peek που είναι το ίδιο.

Όπως πολύ σωστά είπες, τα παιδιά δεν καταλαβαίνουν την όλη τη λογική μιας adt, ειδικά με τον ανεπαρκή τρόπο που παρουσιάζεται στο βιβλίο/Γλωσσα.
Πόσο μάλλον να κάνουν κάτι τέτοιο που λες, αντί για την απλούστατη και ήδη γνωστή αναφορά ΣΤ[τοπ], έξω από pop και push.
Όμως ίσως αξίζει τον κόπο να τους το δείξω.. ομολογώ πως μέχρι τώρα θεωρούσα τελείως φυσικό ένα απλό peek και τέλος.

[gthal]

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

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

[akalest0s]

Σας ευχαριστώ πολύ και τους δύο για το χρόνο σας, όπως και να έχει. Κέρδος είχα.

[Νίκος Αδαμόπουλος]

Πάντως και στο Stl υπάρχει το top() που σου επιστρέφει το στοιχείο της κορυφής χωρίς να το αφαιρέσει από τη στοίβα.

[ApoAntonis]

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


Το συμπληρωματικό υλικό αναφέρει στα πλεονεκτήματα, μειονεκτήματα λιστών και πινάκων, ότι η τυχαία πρόσβαση στις λίστες δεν επιτρέπεται. Πρώτο σημείο: Τι να υποθέσουμε για τις στοίβες και τις ουρές;
Δεύτερο σημείο: Ποιά είναι - και που ειπώθηκε- η συνθήκη κατά την οποία ότι η τυχαία προσπέλαση σε πίνακα δεν επιτρέπεται.

2) Η υπόδειξή σου, μου γεννά το ερώτημα: στις στοίβες/ουρές, ΜΟΝΟ pop και push επιτρέπεται; Δεν επιτρέπεται η αναφορά/προσπέλαση στο πάνω πάνω στοιχείο; Γιατί; Με όσα ξέρω από προγραμματισμό, αλλά και με όσα λέει το βιβλίο ("push και pop οι βασικές λειτουργίες", ποιες είναι οι υπόλοιπες άραγε;), το να προσπελάσεις ΜΟΝΟ την κορυφή της στοίβας, είναι perfectly fine, έγκυρη λειτουργία. Δεν πήγα κάτω από την τοπ. Πουθενά. Οπότε που είναι το θέμα και εδώ; Θα συμφωνούσα αν έκανα προσπέλαση σε οποιοδήποτε άλλο στοιχείο, αυθαίρετα. Αλλά ακόμη και το τοπ στοιχείο, απαγορεύεται να το εμφανίσουμε/προσπελάσουμε;Αυτό λέω, ότι δεν έκανα κάτι τέτοιο. Αυτό θα ήταν όντως λάθος. Όμως η τοπκ που χρησιμοποιώ εκεί, επιτρέπω πιο πριν να αλλάξει μόνο μέσα από pop και push, όχι με άλλον τρόπο.

Ακριβώς μόνο αυτό και τίποτα άλλο.

Τα παραδείγματα που υπάρχουν στο βιβλίο 2, δεν ακολουθούν αυτόν τον περιορισμό. Δεν αναφέρομαι καν στις λύσεις οι οποίες δεν έχουν διανεμηθεί.

"κατά την εξαγωγή ... χωρίς να γίνεται καμία παρέμβαση στα περιεχόμενα του πίνακα" (σελίδα 24) και αμέσως μετά στο παράδειγμα 1
ενώ σαφώς δείχνει υλοποίηση ουράς με πίνακα, στην εξαγωγή διαγράφει τα στοιχεία.
Μάλιστα στο δεύτερο ερώτημα "ώστε η έξοδος να εμφανίζει τα στοιχεία Τ,Ε,Λ,Ο,Σ"
Που γίνεται έξοδος; Είναι λειτουργία, είναι εντολή, είναι από το διάστημα;

Αντίστοιχα, προβλήματα για τις στοίβες φυσικά.
"η βοηθητική μεταβλητή top δείχνει το στοιχείο που τοποθετήθηκε τελευταίο στην κορυφή της στοίβας"
στην ίδια σελίδα (!)
"η μεταβλητή top είναι η μεταβλητή που δείχνει τη θέση που τοποθετήθηκε ... δηλαδή δείχνει την κορυφή της στοίβας"

Απελπισία με πιάνει. Δεν μπορούμε να πάρουμε μια απόφαση αν η μεταβλητή δείχνει το στοιχείο ή την θέση του.

Ο αποκλεισμός άλλος λειτουργιών είναι αυθαίρετος. Ακόμα και η προσπέλαση τυχαίου στοιχείου.
Με ποιά λογική θα γίνει διόρθωση (στο απευκταίο σενάριο όπου θα ζητηθεί κάτι τέτοιο) όταν θα εμφανιστεί σε γραπτό. Επομένως με ποιές προϋποθέσεις θα παρθεί απόφαση αν αυτό που έχει δοθεί ως απάντηση, είναι σκέψη του εξεταζόμενου ή προέρχεται από την διδασκαλία;

Ελπίζω να μην περιέλθουμε σε κατάσταση κλαυσίγελου μεθαύριο.