Απορία στην Στοιβα

Ξεκίνησε από konnacarmen, 08 Μαρ 2021, 08:05:28 ΜΜ

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

ΔΗΜΗΤΡΗΣ Χ

Παράθεση από: evry στις 23 Απρ 2021, 11:29:51 ΜΜ
Δηλαδή η στοίβα που υλοποιείται με δυναμική δομή δεδομένων δεν είναι στοίβα? Είναι άλλη δομή?
είχα γραψει  : στοιβα - ουρα = μονοδιάστατοι πίνακες συνοδευόμενοι με τις αναφερόμενες στο βιβλίο λειτουργίες και με ασκήσεις επικεντρωμένες μεν σε αυτές τις βασικές λειτουργίες χωρίς όμως τρελούς περιορισμούς που έχουν να κάνουν με τεχνικά θέματα.

Σαφώς και δεν εννοώ, οτι δεν υλοποιούνται και με δυναμικες δομες αλλά οτι εδώ, στο μάθημά μας, με βάση τα βιβλία, ειναι μονοδιάστατοι πίνακες,  στους οποίους χρησιμοποιούμε τις βασικές λειτουργίες που περιγράφονται στο βιβλίο για την προσθήκη η αφαιρεση στοιχείων.
Επίσης δεν εχω καταλάβει να είναι τοσο αυστηρη η υλοποιηση που να μην επιτρεπει πχ το για , για την αφαίρεση όλων των στοιχείων, η την προσπέλαση των στοιχείων που υπάρχουν στη δομη, αν και εδω θα ήθελα διευκρίνηση...
Τελος πάντων, ότι χρησιμεύουν ως πίνακες, για την προσομοίωση καθημερινών προβληματων ουράς - στοίβας με τη χρήση των βασικών τους λειτουργιών και πιθανόν μαζί με άλλα σχετικά ερωτήματα που μπορεί να θέσει το πρόβλημα.
ωστόσο επειδη
Παράθεση από: ΔΗΜΗΤΡΗΣ Χ στις 23 Απρ 2021, 12:12:10 ΜΜ
νομίζω, ότι το όλο θέμα κακώς διυλίζεται τόσο.
(Συμπεριλαμβανομένου και εμένα :D)
και επειδη τελικά οι μαθητές πρέπει να παίρνουν μια απάντηση που να τους ξεκουράζει (γιατι έχω μαθητές που παρακολουθούν το στέκι) και να τους κάνει να αισθάνονται ότι λύνουν σωστα,  και όχι να έχουν ανασφάλειες, (και ειδικα φετος εχουν εξαντληθει οι μαθητες πλεον ...)  σκοπευω να παρακολουθήσω τη συζητηση  και αναλογα θα τους συμβουλεψω για να μη χάσουν μοναδες.
Με καθε σεβασμο προς συμφωνούντες και διαφωνούντες,  καθώς ειλικρινά θεωρώ πως όλοι οσοι γράφουμε τη γνώμη μας εδω πέρα, το κάνουμε  γιατί πραγματικά προσπαθούμε για να βγει κατι σωστο, εχω γραψει και τη γνώμη τη δική μου και ελπίζω σε μια υπευθυνη τοποθετηση η ενα ασφαλες τελικο συμπερασμα (αν και τελικα ειναι απλά ένα θεματακι απο διαφορα που εχουν προκυψει μεσα στα χρόνια)
ΚΑΛΗΜΕΡΑ ΣΕ ΟΛΟΥΣ

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

πέρυσι αν δεν κάνω λάθος, μαζέψαμε κάποιοι συνάδελφοι από εδώ απορίες/διευκρινίσεις για τη νέα ύλη, και στείλαμε ένα αρχείο στο υπουργείο (το γενικό συντονισμό και δημιουργία του αρχείου είχε ο καλός συνάδελφος Γιάννης Αναγνωστόπουλος)

https://alkisg.mysch.gr/steki/index.php?topic=8158.msg89494#msg89494

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

Αν επιλογή = 'εξαγωγή' τότε
    αν πίσω=0 και εμπρός = 0 τότε
        γράψε 'άδεια'
    αλλιώς_αν εμπρός=πίσω τότε
        εμπρός<--0
        πίσω<--0
    Αλλιώς
          Για κ από εμπρός+1 μέχρι πίσω
             ουρά[κ-1]<--ουρά[κ]
         τέλος_επανάληψης
         εμπρός<--1
         πίσω<--πίσω-1
      Τέλος_αν
Τέλος_αν

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

ΔΗΜΗΤΡΗΣ Χ

Παράθεση από: Λαμπράκης Μανώλης στις 24 Απρ 2021, 12:45:52 ΜΜ
εγώ πιστεύω 1) δεν θα πρέπει να ζητηθεί κάτι από το μαθητή πριν λυθούν όλα αυτά που συζητάμε  2) αν ζητηθεί και δώσει λύση "σωστή στα πλαίσια του μαθήματος", θα πρέπει να μην χάσει κάτι 
ΣΥΜΦΩΝΩ ΑΠΟΛΥΤΩΣ

Καρκαμάνης Γεώργιος

Διαβάζοντας τα παραπάνω καταλαβαίνει κανείς πως ο προβληματισμός είναι αν θα χρησιμοποιηθεί η εντολη ΓΙΑ ώστε να προσπελαστεί η στοίβα/ουρά με τη μορφή πίνακα ή αν θα εφαρμοστουν οι γνωστές λειτουργίες με χρήση των άλλων εντολων επανάληψης.
Επειδή είναι κάτι που δεν έχει ακόμα αντιμετωπιστεί σε θέματα πανελληνίων εξετάσεων εύλογες είναι οι απορίες όλων.
Παρόλα αυτά όμως μπορουμε να κατασταλάξουμε σε ορισμένα βασικά σημεία:
- Αν κάποιο θέμα πανελληνίων εξετάσεων απαιτεί τη χρήση στοίβας/ουράς προφανώς θα υπάρχει μια περιγραφή στην εκφώνηση με την οποια ο μαθητής θα καταλαβαίνει πως πρέπει να αντιμετωπίσει τη κάθε δομή.
- Πρέπει να γίνει ένας διαχωρισμός πρώτα από εμάς τους ίδιους τους καθηγητές μεταξύ πίνακα και δομών στοιβας/ουράς. Διαφορετικά πρέπει να αντιμετωπίζουμε τον πίνακα και διαφορετικά τις άλλες δύο δομές. Το τελευταίο βιβλιο του μαθήματος παρουσιάζει αλγοριθμους διαχείρισης των δομών στοίβας και ουράς χωρίς τη χρήση της εντολης ΓΙΑ.
Γιατί να μη υιοθετήσουμε και εμείς αυτή τη χρήση;
Ας παραδεχτούμε ότι στο πλαίσιο της διδασκαλιας αυτού του μαθήματος οι δυο δομές ναι μεν υλοποιούνται με πίνακες αλλά διαχειρίζονται με τη χρήση των εντολών ΜΕΧΡΙΣ_ΟΤΟΥ και ΟΣΟ στις αντίστοιχες λειτουργίες τους.
Γιατί πρέπει να πούμε στους μαθητές να χρησιμοποιούν την εντολη ΓΙΑ και να μην τους το απαγορεύσουμε;
Οι μαθητές μαθαίνουν αυτά που διαβάζουν και ακούν από τους καθηγητές τους Αν εμείς  ως εκπαιδευτικοί καθόμαστε και υποστηρίζουμε τη χρήση της ΓΙΑ στη διαχειρηση της στοίβας και της ουράς, τότε προφανώς θα γεννιουνται όλα αυτά τα ερωτήματα.




petrosp13

Εγώ ακόμα αδυνατώ να καταλάβω γιατί είναι λάθος το άδειασμα μιας στοίβας με την εξής λογική:
Για στοιχείο από τοπ μέχρι 1 με βήμα -1
Απώθηση()

Μπορεί κάποιος να μου το εξηγήσει;
Τι ακριβώς προσφέρει να το υλοποιήσω με Όσο;
Πού παραβιάζω την λογική της στοίβας;
Πού εκμεταλλεύομαι τον πίνακα και κλέβω;
Πού έχω άμεση πρόσβαση σε κάποιο στοιχείο εκτός της κορυφής;
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

oldBugman

Έχω αγανακτήσει με αυτά που διαβάζω! Οπότε ξαναγράφτηκα ως oldBugman...
Πραγματικά η σημασία σε αυτό που λέμε ουρά είναι το FIFO, ή First In First Out. ή το πρώτο που μπαίνει βγαίνει πρώτο. Δεν υπάρχει πουθενά ο έλεγχος μεγέθους της ουράς (δηλαδή ως προς το πόσα στοιχεία έχει). Αυτό που υπάρχει είναι αν η ουρά είναι άδεια (έλεγχος) και αν η ουρά είναι γεμάτη (και πάλι έλεγχος).
Υπάρχουν πολλοί τρόποι υλοποίησης ουρών. Οι ουρές δουλεύουν με δυο δείκτες εκτός αν έχουμε πίνακα με ολίσθηση, οπότε πρακτικά η ολίσθηση κάνει τον ένα δείκτη να είναι κολλημένος στην ίδια τιμή. Στους πίνακες οι δείκτες λέγονται Indexes, ενώ σε δυναμικές δομές λέγονται pointers. Οι pointers δεν έχουν διατεταγμένη σειρά, δηλαδή τα στοιχεία μπορεί να είναι ανακατεμένα. Στους πίνακες αν έχουμε κυκλική ουρά τότε επίσης μπορούν τα στοιχεία να βρίσκονται σε δυο χωριστές ομάδες (λόγω του ότι μετά το τελευταίο στοιχείο του πίνακα να συνεχίζουμε στο επόμενο στην πρώτη θέση του πίνακα).
Αν έχουμε ουρά με μηχανισμό ολίσθησης τότε ο rear είναι κολλημένος στην πρώτη θέση, άρα ο top έμμεσα δείχνει και τον αριθμό στοιχείων (ως top ή top-1 ανάλογα την υλοποίηση). Εκεί λοιπόν η χρήση της ΓΙΑ μπορεί να χρησιμοποιηθεί, εφόσον μόνο απόθηση υπάρχει στο σώμα της.

Το βασικότερο για μένα είναι να κατανοήσει κανείς για ποιο λόγο χρησιμοποιείται μια ουρά! Μια ουρά δέχεται στοιχεία. Το πώς προκύπτουν τα στοιχεία και πώς αυτά καταναλώνονται δηλώνουν την χρήση της ουράς. Κατά την χρήση της ουράς έχουμε πάντα δυο φάσεις που επαναλαμβάνονται μέχρι η ουρά να αδειάσει. Άρα λογικά ξεκινάμε με τουλάχιστον ένα στοιχείο. Στην πρώτη φάση εξάγουμε ένα στοιχείο, το επεξεργαζόμαστε και μπορεί να προκύψει η δεύτερη φάση μια ή περισσότερες φορές. Στη δεύτερη φάση βάζουμε στοιχεία στην ουρά. Ο αλγόριθμος πρέπει να τερματίζει όταν η ουρά αδειάσει. Άρα πρέπει να υπάρχει ένα στοιχείο ή ομάδα στοιχείων που δεν θα δίνουν νέα στοιχεία στην ουρά.

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

Γιώργος Καρράς
(ο παππούς, που απαιτεί και λίγο σεβασμό...)

P.Tsiotakis

#51
Το σχολικό βιβλίο χρησιμοποιεί τη δομή Μέχρις_ότου για τη διαχείριση των δομών στοίβα και ουρά γιατί ενσωματώνει το "Ναι/Όχι" στη συνέχεια/ολοκλήρωση της επεξεργασίας της. Το διατηρεί για ομοιογένεια και σε άλλες ασκήσεις. Η παραπάνω αιτιολόγηση δεν έρχεται σε σύγκρουση με το ότι ο/η συντάκτης του κώδικά μπορεί απλά να στερούταν φαντασίας.

Προφανώς κάθε βρόχος που σέβεται τη μέθοδο επεξεργασίας της στοίβας/ουράς (LIFO/FIFO) είναι σωστός και δόκιμος. Αυτό σημαίνει "κάθε επιστημονικά..." και όλα τα άλλα ωραία.

καλό Πάσχα

oldBugman

Αναφέρω στο προηγούμενο μήνυμα την ουρά. Επειδή γίνεται στο θέμα αναφορά στη Στοίβα σωστό είναι να περιγράψω με το ίδιο σκεπτικό την χρήση της. Οι ελληνικές λέξεις που αποδίδονται σε διάφορες δομές της πληροφορικής δεν είναι απόλυτες αλλά σχετικές με το περιεχόμενο (context) του θέματος (δομές δεδομένων). Όντως παλαιότερα η στοίβα αναφερόταν ως σωρός. Δεν έχει σημασία πώς λέγεται, αν και έχει σημασία να χρησιμοποιείται η τρέχουσα λέξη Στοίβα. Η λέξη δεν προσδιορίζει από μόνη της τη δομή! Η δομή χαρακτηρίζεται από το LIFO ή Last Ιn First Out, ή το τελευταίο που μπαίνει βγαίνει πρώτο. Και εδώ ισχύει ο κανόνας των δυο φάσεων καθώς και η αρχικοποίηση της δομής με ένα τουλάχιστον στοιχείο. Η επαναληπτική διαδικασία αφαιρεί στη πρώτη φάση ένα στοιχείο και βάσει του στοιχείου αυτού μπορεί να οδηγεί σε εισαγωγή ενός ή περισσότερων στοιχείων. Η επανάληψη τερματίζει όταν η στοίβα έχει αδειάσει.
Εδώ αξίζει να αναφερθεί ότι ένας επεξεργαστής CPU ή central processing unit, χρησιμοποιεί το Stack (Στοίβα) για να κρατάει την διεύθυνση επιστροφής μετά από κλήση υπορουτίνας, καθώς και χώρο για τοπικές μεταβλητές.  Αυτός ο τύπος στοίβας  έχει το κοινό με την δομή LIFO της χρήσης ενός δείκτη (Stack Pointer ή SP). Όμως έχει και διαφορές όπως τη χρήση του SP καταχωρητή για τη προσπέλαση του ν στοιχείου όπου ν είναι ο αριθμός που προστίθεται στη τιμή SP για να δώσει την διεύθυνση μιας τοπικής μεταβλητής. Έτσι στο κώδικα η μεταβλητή έστω Χ μπορεί να αντιστοιχεί στο SP+12.  Αυτό σημαίνει ότι σε αυτό τον τύπο Στοίβας γίνεται προσπέλαση στοιχείων πέρα από αυτό της κορυφής (top) που είναι στο SP (ή για την ακρίβεια αυτό που λέμε top είναι το SP - αυτό που δείχνει ο δείκτης SP).

Καλό Πάσχα!

gpapargi

Παράθεση από: alkisg στις 24 Απρ 2021, 10:18:57 ΠΜ
Τέλεια αφορμή για να πετάξω την απορία μου:
Γιατί στη λύση της άσκησης με το ταχυδρομείο προσπελαύνουμε άμεσα τα στοιχεία του πίνακα της ουράς, αντί να προσπελαύνουμε μόνο το Ουρά[δείκτης_αρχής] ή το Ουρά[δείκτης_τέλους];
Η λειτουργία ολίσθησης στις ουρές που "πρέπει να διδάξουμε", πώς υλοποιείται όταν εσωτερικά χρησιμοποιούμε δείκτες αντί για πίνακες;

Δεν υπάρχει αντίφαση εκεί; Η στοίβα είναι "αφηρημένη δομή" αλλά η ουρά "υλοποιείται με απευθείας πρόσβαση σε ενδιάμεσα στοιχεία ενός πίνακα";
Δεν μπορούμε να έχουμε ενιαία αντιμετώπιση και στις δύο δομές;

Κανονικά η ολίσθηση που κάνει στις λύσεις είναι κρυμμένη μέσα στην υλοποίηση της εισαγωγής. Δεν τη βλέπει το κυρίως πρόγραμμα. Δηλαδή το κυρίως πρόγραμμα βλέπει τις 2 λειτουργίες εισαγωγή και εξαγωγή (οι οποίες είναι υποπρογράμματα) και δεν ενδιαφέρεται για την εσωτερική υλοποίησή τους. Αν η υλοποίηση γίνει με πίνακα καλύτερα να γίνει με κυκλικά. Αν δε γίνεται καταφεύγουμε στην αργή λύση της ολίσθησης η οποία όμως είναι κρυμμένη μέσα στο υποπρόγραμα της εισαγωγής. Δεν την κάνει το κυρίως πρόγραμμα. Το πρόβλημα ξεκινάει από το ότι το βιβλίο έχει κάνει το implementation μέσα στο κυρίως πρόγραμμα και δεν είναι σαφές ποιο μέρος ανήκει στην υλοποίηση των πράξεων και ποιο στη χρήση από το κυρίως πρόγραμμα. Φυσικά αν κάνεις υλοποίηση με δείκτες δεν υπάρχει τέτοιο θέμα. Η υλοποίηση γίνεται με δείκτες και δεν έχεις ανάγκη να κάνεις καμία ολίσθηση. Όμως το βασικό είναι ότι το κυρίως πρόγραμμα δεν πρέπει να ξέρει πως γίνεται η υλοποίηση της εισαγωγής. Αυτή κρύβεται μέσα στο υποπρόγραμμα που υλοποιεί την πράξη της εισαγωγής.

Γι αυτό έγραψα και πιο πριν ότι πρέπει να θεωρούμε πως ότι κάνουμε γίνεται με τα υποπρογράμματα που υλοποιούν τις πράξεις και στη συνέχεια να "αντικαθιστούμε" το κομμάτι της κλήσης με το κομμάτι της υλοποίησης. Φυσικά αυτό μπερδεύει το μαθητή.

evry

#54
Πέτρο το πρόβλημα εδώ έχει να κάνει με τον τρόπο που χρησιμοποιούν τις δομές δεδομένων στοίβα και ουρά στο μάθημα.
Έτσι όπως τα έχουν ορίσει δεν μπορεί κανείς να σου απαγορεύσει να κάνεις αυτό που κάνεις παρακάτω. Δηλαδή αν το κάνει αυτό μαθητής δεν δικαιούται κανείς να του κόψει.
Όμως το θέμα είναι ότι όλο αυτό έρχεται σε αντίθεση με αυτό που λέμε αφηρημένος τύπος δεδομένων (ADT)
https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Η λογική είναι ότι εσύ πρέπει να χρησιμοποιείς μια στοίβα μέσα από το interface που σου δίνει και όχι έχοντας πρόσβαση στα στοιχεία ή ακόμα και στον top.
Ο κώδικάς σου θα πρέπει να λειτουργεί σωστά ακόμα και αν κάποιος πάει στην βιβλιοθήκη που έχει οριστεί η στοίβα και αλλάξει την υλοποίηση.
Κώδικας: ΓΛΩΣΣΑ
στοίβα <- Στοίβα()
στοίβα.ώθηση(5)
.........

ΟΣΟ  ΟΧΙ στοίβα.κενή() ΕΠΑΝΑΛΑΒΕ
    ΓΡΑΨΕ στοίβα.απώθηση()
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ


Στον παραπάνω κώδικα δεν ξέρω πως έχει υλοποιηθεί η στοίβα αλλά τη χρησιμοποιώ. Μπορεί να είναι με πίνακα ή με δυναμική δομή.
Αν η υλοποίηση αλλάξει δεν αλλάζει τίποτα στον κώδικα ενώ στο παράδειγμα που δίνεις εσύ δεν ισχύει το ίδιο.
Προσοχή! Αυτό δεν σημαίνει ότι στην στοίβα επιτρέπεται μόνο ώθηση/απώθηση. Μπορεί να χρειαστώ να δω το πρώτο στοιχείο χωρίς να το αφαιρέσω. Σε πολλές περιπτώσεις ανάλογα με την χρήση μπορεί να προστεθούν τέτοιες λειτουργίες. Όχι όμως να μπορείς να πειράξεις ή ακόμα και να δεις τον top.
Αυτό θα πει διαχωρισμός interface/implementation.

Παράθεση από: petrosp13 στις 26 Απρ 2021, 12:08:27 ΠΜ
Εγώ ακόμα αδυνατώ να καταλάβω γιατί είναι λάθος το άδειασμα μιας στοίβας με την εξής λογική:
Για στοιχείο από τοπ μέχρι 1 με βήμα -1
Απώθηση()

Πού εκμεταλλεύομαι τον πίνακα και κλέβω;

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

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

Δείτε και εδώ μια απλή υλοποίηση στοίβας που υλοποιεί το information hiding πολύ απλά
https://alkisg.mysch.gr/steki/index.php?topic=8628.msg94269#msg94269
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

gpapargi

Με βάση τη λογική της αφηρημένης δομής δεδομένων, νομίζω πως το καλύτερο στη ΓΛΩΣΣΑ θα ήταν να έχουμε υποπρογράμματα για ώθηση απώθηση ως εξής:
Κάλεσε Ωθηση(στοίβα,top,στοιχείο,done)
Η done θα είναι μια λογική μεταβλητή που θα θα γυρίζει αληθής αν πέτυχε η ώθηση ή ψευδής που θα σημαίνει ότι δεν πέτυχε, άρα θα καταλαβαίνουμε ότι έγινε υπερχείλιση.
Ομοίως
Κάλεσε Απώθηση(στοίβα, top, x, done)
H done θα γυρίζει αληθής αν πέτυχε η απώθηση ή ψευδής αν έγινε υποχείλιση.
Η top υπάρχει αλλά δεν τη χρησιμοποιούμε στο κυρίως πρόγραμμα.

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

oldBugman

#56
Η δική μου πρόταση είναι με χρήση κόμβων που φτιάχνονται σε πίνακα. Ο πίνακας είναι το ανάλογο της μνήμης, αλλά αντί να έχει bytes έχει ακέραιους. Υπάρχουν δυο πίνακες. Ο ένας λέγεται τιμ[] και περιέχει τις τιμές, ενώ ο άλλος λέγεται κομ[] και περιέχει δείκτες που συνδέουν τους κόμβους. Έτσι κάθε κόμβος έχει μια φυσική διεύθυνση που δείχνει δυο τιμές μια στο πίνακα κομ[] και μια στο πίνακα τιμ[]. Έτσι αν στην θέση 10 έχουμε έναν κόμβο με τιμ[10] = 1000 (η πληροφορία που καταχωρούμε στον κόμβο) τότε το κόμ[10] θα έχει είτε μια θέση Ν με τιμή μια από την περιοχή τιμών 1 έως 100 που θα δείχνει τον επόμενο κόμβο είτε το 0 που θα σηματοδοτεί τον τερματικό κόμβο (τον κόμβο που δεν οδηγεί σε άλλο). Η σύνδεση κόμβων με ένα δείκτη δημιουργεί αυτό που λέμε συνδεδεμένη λίστα. Επίσης στην αρχή όλοι οι κόμβοι ανήκουν σε μια συνδεδεμένη λίστα ελεύθερων κόμβων. Όταν χρειαζόμαστε ένα κόμβο τότε αφαιρούμε έναν από την λίστα ελεύθερων και τον προσθέτουμε εκεί που θέλουμε είτε σε μια ουρά είτε σε στοίβα.

Με λίγες γραμμές στη ΓΛΩΣΣΑ δημιουργούμε δυναμικές δομές!

Περισσότερα προγράμματα υπάρχουν εδώ: https://georgekarras.blogspot.com/p/3.html

Κώδικας: glossa
ΠΡΟΓΡΑΜΜΑ κομβοι
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: κομ[100], τιμ[100], ελεύθερο, μπροστά, πίσω, κορυφή
  ΑΚΕΡΑΙΕΣ: ι, βοηθητική
ΑΡΧΗ
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 99
    κομ[ι] <- ι + 1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  κομ[100] <- 0
!δείκτης ελεύθερων
  ελεύθερο <- 1
  ΓΡΑΨΕ "Δημιουργία στοίβας 20 στοιχείων"
  κορυφή <- 0
  ΓΙΑ ι ΑΠΟ 100 ΜΕΧΡΙ 119
    ΑΝ ελεύθερο <> 0 ΤΟΤΕ
      βοηθητική <- κορυφή
      ΚΑΛΕΣΕ Νεο(κορυφή, ελεύθερο, κομ) 
      κομ[κορυφή] <- βοηθητική
      ΓΡΑΨΕ "Ώθηση ", ι
      τιμ[κορυφή] <- ι
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
! Υπολογισμός Ελεύθερων Κόμβων
  ΚΑΛΕΣΕ Ελεύθερη_Μνήμη(ελεύθερο, κομ) 
  ΓΡΑΨΕ "Δημιουργία ουράς 20 στοιχείων"
  πίσω <- ελεύθερο
  μπροστά <- 0
  ΓΙΑ ι ΑΠΟ 120 ΜΕΧΡΙ 139
    ΑΝ ελεύθερο <> 0 ΤΟΤΕ
      βοηθητική <- μπροστά
      ΚΑΛΕΣΕ Νεο(μπροστά, ελεύθερο, κομ) 
      τιμ[μπροστά] <- ι
      ΓΡΑΨΕ "Εισαγωγή ", ι
      ΑΝ βοηθητική <> 0 ΤΟΤΕ
        κομ[βοηθητική] <- μπροστά
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
! Υπολογισμός Ελεύθερων Κόμβων
  ΚΑΛΕΣΕ Ελεύθερη_Μνήμη(ελεύθερο, κομ) 
  ΓΡΑΨΕ "Διάβασμα Στοιβας χωρίς να πετάξουμε τα στοιχεία"
! εμφανίζει από 119 έως 100 δηλαδή το τελευταίο που μπήκε βγαίνει πρώτο
  ΚΑΛΕΣΕ Δείξε(κορυφή, κομ, τιμ) 
  ΓΡΑΨΕ "Διαβασμα Ουράς χωρίς να πετάξουμε τα στοιχεία"
! εμφανίζει από 120 έως 139 δηλαδή το πρώτο που μπήκε βγαίνει πρώτο
  ΚΑΛΕΣΕ Δείξε(πίσω, κομ, τιμ) 
! Θα χρησιμοποιήσουμε τα 5 πρώτα από την στοίβα (θα τα πετάξουμε)
  ΓΡΑΨΕ "Απώθηση 5 πρώτων από την στοίβα"
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 5
    ΑΝ κορυφή <> 0 ΤΟΤΕ
      ΚΑΛΕΣΕ Χρήση(βοηθητική, κορυφή, ελεύθερο, κομ, τιμ) 
      ΓΡΑΨΕ βοηθητική
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
! θα χρησιμοποιήσουμε τα 5 πρώτα από την ουρά (θα τα πετάξουμε)
  ΓΡΑΨΕ "Εξαγωγή 5 πρώτων από την Ουρά"
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 5
    ΑΝ πίσω <> 0 ΤΟΤΕ
      ΚΑΛΕΣΕ Χρήση(βοηθητική, πίσω, ελεύθερο, κομ, τιμ) 
      ΓΡΑΨΕ βοηθητική
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
! Υπολογισμός Ελεύθερων Κόμβων
  ΚΑΛΕΣΕ Ελεύθερη_Μνήμη(ελεύθερο, κομ) 
! Άδειασμα Στοίβας
  ΟΣΟ κορυφή <> 0 ΕΠΑΝΑΛΑΒΕ
    ΚΑΛΕΣΕ Χρήση(βοηθητική, κορυφή, ελεύθερο, κομ, τιμ) 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
! Υπολογισμός Ελεύθερων Κόμβων
  ΚΑΛΕΣΕ Ελεύθερη_Μνήμη(ελεύθερο, κομ) 
! Άδειασμα Ουράς
  ΟΣΟ πίσω <> 0 ΕΠΑΝΑΛΑΒΕ
    ΚΑΛΕΣΕ Χρήση(βοηθητική, πίσω, ελεύθερο, κομ, τιμ) 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
! Υπολογισμός Ελεύθερων Κόμβων
  ΚΑΛΕΣΕ Ελεύθερη_Μνήμη(ελεύθερο, κομ) 

ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
ΔΙΑΔΙΚΑΣΙΑ Δείξε(πρώτο, μνημη, περιεχόμενο) 
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: πρώτο, βοηθητική, μνημη[100], περιεχόμενο[100] 
ΑΡΧΗ
  βοηθητική <- πρώτο
  ΟΣΟ βοηθητική <> 0 ΕΠΑΝΑΛΑΒΕ
    ΓΡΑΨΕ περιεχόμενο[βοηθητική] 
    βοηθητική <- μνημη[βοηθητική] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ Χρήση(επιστροφή, πρώτο, ελεύθ, μνημη, περιεχόμενο) 
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: επιστροφή, πρώτο, μνημη[100], περιεχόμενο[100] 
  ΑΚΕΡΑΙΕΣ: βοηθητική, ελεύθ
ΑΡΧΗ
  ΑΝ πρώτο <> 0 ΤΟΤΕ
    επιστροφή <- περιεχόμενο[πρώτο] 
    βοηθητική <- πρώτο
    πρώτο <- μνημη[πρώτο] 
    μνημη[βοηθητική] <- ελεύθ
                      ! επιστροφή του ελεύθερου κόμβου στη στοίβα των ελεύθερων.
    ελεύθ <- βοηθητική
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ Νεο(επιστροφή, ελ, μνήμη) 
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: επιστροφή, ελ, μνήμη[100] 
ΑΡΧΗ
  επιστροφή <- ελ
  ελ <- μνήμη[ελ] 
  μνήμη[επιστροφή] <- 0
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ Ελεύθερη_Μνήμη(ελ, μνήμη) 
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: βοηθητική, ελ, μνήμη[100], ι
ΑΡΧΗ
  βοηθητική <- ελ
  ι <- 0
  ΟΣΟ βοηθητική <> 0 ΕΠΑΝΑΛΑΒΕ
    ι <- ι + 1
    βοηθητική <- μνήμη[βοηθητική] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ "Ελεύθερη Μνήμη ", ι, " κόμβων"
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

thaaanos

Παράθεση από: petrosp13 στις 26 Απρ 2021, 12:08:27 ΠΜ
Εγώ ακόμα αδυνατώ να καταλάβω γιατί είναι λάθος το άδειασμα μιας στοίβας με την εξής λογική:
Για στοιχείο από τοπ μέχρι 1 με βήμα -1
Απώθηση()

Μπορεί κάποιος να μου το εξηγήσει;
Τι ακριβώς προσφέρει να το υλοποιήσω με Όσο;
Πού παραβιάζω την λογική της στοίβας;
Πού εκμεταλλεύομαι τον πίνακα και κλέβω;
Πού έχω άμεση πρόσβαση σε κάποιο στοιχείο εκτός της κορυφής;

Υποθέτεις οτι ο δείκτης top ισοδυναμει με το πληθος των στοιχείων στην στοιβα.
(το οποίο εξαρτάται από την υλοποιηση την οποία ο χρήστης της δομής αγνοεί)

thaaanos

Παράθεση από: alkisg στις 24 Απρ 2021, 11:19:39 ΠΜ
Πέτρο λέω για τις ενδεικτικές λύσεις ασκήσεων:
http://ebooks.edu.gr/ebooks/d/8547/5296/22-0263-01_Pliroforiki-G-Lykeiou-SpOikPlir_Lyseis-Askiseon.pdf

Σελίδα 19, γραμμή 40:

Κώδικας: ΓΛΩΣΣΑ
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ αθρ
    πινακας_επιθετων[i] <- πινακας_επιθετων[αρχ - 1 + i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ


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

Για να μην παρεξηγηθώ, εγώ εννοώ ότι:

  • Είμαι κατά της ολίσθησης, αφού εκτός από τη λάθος πολυπλοκότητα Ο(Ν), δεν υφίσταται καν σαν έννοια αν υλοποιήσουμε ουρά με δείκτες.
  • Όπως είπε ο Θάνος παραπάνω, είμαι υπέρ του: ο "χρήστης" της "βιβλιοθήκης στοίβα/ουρά" δεν πρέπει να ξέρει την εσωτερική αναπαράσταση. Για μένα αυτό σημαίνει αφηρημένη δομή, ο ορισμός του API μιας βιβλιοθήκης.
  • Όμως θεωρώ ότι εμείς διδάσκουμε και "προγραμματιστές" της "βιβλιοθήκης στοίβα/ουρά", άρα υπό εκείνο το πρίσμα, επιτρέπεται να μιλήσουμε για εσωτερική αναπαράσταση.
  • Τέλος, το να κάνουμε μικροαλλαγές στο API της στοίβας/ουράς δεν σημαίνει ότι κάναμε ιεροσυλία, ούτε ότι ξαφνικά σταμάτησαν να είναι ουρές και στοίβες. Ακόμα και το API εξαρτάται από το δοθέν πρόβλημα. Αν το πρόβλημα που θέλω να λύσω απαιτεί συνάρτηση Peek(top - 1), και την υλοποιήσω, πάλι στοίβα είναι, ελαφρώς προσαρμοσμένη χωρίς να χάνονται οι χαρακτηριστικές της ιδιότητες.

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