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

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

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

evry

Το συγκεκριμένο τμήμα κώδικα δουλεύει μια χαρά μόνο που δεν έχει καμία σχέση με τη δομή δεδομένων ΣΤΟΙΒΑ.
Παράθεση από: ripper στις 07 Απρ 2021, 01:19:23 ΜΜ
Μια χαρά δουλεύει η ΓΙΑ, αρκεί να είναι σε αυτήν τη μορφή:

ΓΙΑ Ι ΑΠΟ ΤΟΠ ΜΕΧΡΙ 1 ΜΕ_ΒΗΜΑ -1
    ΓΡΑΨΕ Α[Ι]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΟΠ <- 0
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

ripper

Παράθεση από: evry στις 07 Απρ 2021, 01:28:21 ΜΜ
Το συγκεκριμένο τμήμα κώδικα δουλεύει μια χαρά μόνο που δεν έχει καμία σχέση με τη δομή δεδομένων ΣΤΟΙΒΑ.

Συμφωνώ 100%, αλλά στα πλαίσια του μαθήματος μας, την αντιμετωπίζουμε στατικά, σαν πίνακα.

petrosp13

Στην πράξη, η στοίβα υλοποιείται με πίνακα λέει το βιβλίο που διδάσκουμε
Άρα, η σάρωση μιας στοίβας στα πλαίσια του μαθήματος θα γίνει με δομή Για, αυτό λέει η λογική
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

thaaanos

Σάρωση των στοιχείων μιας στοίβας δεν είναι στις λειτουργίες της στοίβας,
Το οτι μπορείς να το κάνεις ή οτι δουλεύει δεν είναι δικαιολογία για να το κάνεις.
Αν το κάνεις απλά μιλάς για άλλη δομή δεδομένων (δυναμικό πίνακα) και δεν είναι πια στοίβα.

petrosp13

Απώθηση όλων των στοιχείων μιας στοίβας;
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

taxata

#20
Όσον αφορά στον κώδικα με το Για και το Γράψε εφόσον μιλάμε για στοίβα ακόμα και ένα απλό Γράψε Α[τοπ] δεν μπορεί να γίνει εάν δεν γίνει πρώτα pop. Ας φανταστούμε τη στοίβα ως ένα αδιαφανή σωλήνα ο οποίος έχει μόνο ένα άνοιγμα από το πάνω μέρος του (pringles) για να εμφανίσουμε (να φάμε ένα πατατάκι) πρέπει πρώτα να το βγάλουμε με την κίνηση (μέθοδο) pop.
Ο τρόπος που παρουσιάζεται η στοίβα στο βιβλίο (και η ουρά αλλά δεν μιλάμε γι' αυτή τώρα) έχει τα θέματά του και μπερδεύει.
Κάπως θα μπορούσε να βελτιωθεί η κατάσταση εάν αλλάξει η προτεινόμενη σειρά διδασκαλίας και διδάσκεται πρώτα το κεφάλαιο των υποπρογραμμάτων και η ώθηση και η απώθηση να υλοποιούνται και να χρησιμοποιούνται ΜΟΝΟ ως Διαδικασίες (το κοντινότερο στις μεθόδους) και ως οι ΜΟΝΕΣ επιτρεπόμενες λειτουργίες σε αυτήν.


Παρακάτω παραθέτω υλοποίηση στοίβας με στατικά διαχειριζόμενη  (για συμβατότητα με τη λογική του ΓΕΛ) λίστα σε Python.
Το interface είναι λίγο  πλούσιο για λόγους ευκολίας στις δοκιμές οπτικοποίησης (πχ η peek κάνει pop & push)
http://users.sch.gr/chatzipap/stack_with_array/
....

Τάσος_Χατζηπαπαδόπουλος
Κύριε δεν έχω internet
http://users.sch.gr/chatzipap/

alkisg

Η hardware υποστήριξη στοίβας στους συνηθισμένους επεξεργαστές χρησιμοποιεί εντολές assembly της μορφής:

ΣτοίβαΕκτέλεσης[bp-3] <- 10

Όπου bp είναι ο καταχωρητής που δείχνει την κορυφή της στοίβας και -3 είναι η θέση μιας τοπικής μεταβλητής σε σχέση με την κορυφή. Έτσι υλοποιούνται οι τοπικές μεταβλητές των υποπρογραμμάτων και δίνεται η δυνατότητα αναδρομής που περιγράφεται στη σελίδα 187 του βιβλίου μαθητή.

Δηλαδή η υλοποίηση της στοίβας με πίνακα και η απευθείας πρόσβαση σε κάποια από τα στοιχεία της είναι συχνό φαινόμενο στην πράξη. Αν θέλουμε να το θεωρήσουμε εκτός ύλης, ΟΚ, αλλά είναι valid use case της δομής στοίβα.

http://www.c-jump.com/CIS77/ASM/Stack/S77_0060_direct_stack.htm

Να το πω με άλλα λόγια, μπορούμε να ορίσουμε την ελάχιστη αφηρημένη δομή Stack όπως λέει η Wikipedia, αλλά αν μετά θέλουμε να υλοποιήσουμε και μια κλάση ArrayStack που να έχει και δυο λειτουργίες παραπάνω, δεν σημαίνει ότι δεν είναι απόγονος της κλάσης Stack· η μέθοδος isStack() θα επιστρέφει true.

George Eco

#22
Παράθεση από: petrosp13 στις 07 Απρ 2021, 01:55:59 ΜΜ
Στην πράξη, η στοίβα υλοποιείται με πίνακα λέει το βιβλίο που διδάσκουμε
Άρα, η σάρωση μιας στοίβας στα πλαίσια του μαθήματος θα γίνει με δομή Για, αυτό λέει η λογική

Παράθεση από: petrosp13 στις 08 Απρ 2021, 01:12:44 ΠΜ
Απώθηση όλων των στοιχείων μιας στοίβας;

Έμμμ, ο Πέτρος έχει δίκιο συνάδελφοι. Είτε μας αρέσει είτε όχι.
Στα πλαίσια του μαθήματος, αν κάποιος είναι αρκετά τρελός, να ζητήσει να εμφανίσουμε τα περιεχόμενα μιας στοίβας, θα πρέπει...

  • Να φτιάξουμε ένα πίνακα ίσο με αυτόν της στοίβας
  • Να αρχικοποιήσουμε το πίνακα με μη αποδεκτή τιμή (ώστε να ξέρουμε ποια είναι κενά αν δε γεμίσει)
  • Να απωθήσουμε τα στοιχεία ένα προς ένα, χώνοντάς τα στο πίνακα.
  • Να τα εμφανίσουμε ΑΠΟ ΤΟΝ ΠΙΝΑΚΑ με ΓΙΑ (κι αντίστοιχη εμφωλευμένη ΑΝ για τα κενά στοιχεία).
  • Να ωθήσουμε ορθά τα στοιχεία στη στοίβα, ώστε να αναδομηθεί όπως ήταν.

Είναι ο μόνος τρόπος που μπορώ να σκεφτώ στα πλαίσια του μαθήματος.


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

Κατά τη γνώμη μου, η στοίβα στα πλαίσια του μαθήματος ως έχει, αποτελείται από τον πίνακα, τη μεταβλητή ΚΑΙ ΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ ΩΘΗΣΗΣ - ΑΠΩΘΗΣΗΣ. Αλλιώς ας μη διδάσκουμε στοίβα κι ουρά, τι νόμηα έχει; Μόνο πίνακες. Γι' αυτό δε μου αρέσει ως έχει το μάθημα. Καταλήγουμε να θέτουμε θέματα τέτοιου τύπου.

thaaanos

Η μπορείς να τα βγάζεις από την στοιβα Α, να τα ελέγχεις και να τα βάζεις σε μια άλλη στοιβα Β, και μόλις αδειάσει η Α να τα ξαναβάλεις πίσω βγάζοντας τα από την στόιβα Β και βάζοντας τα στην στοίβα Α
:D

George Eco

Παράθεση από: thaaanos στις 20 Απρ 2021, 01:44:51 ΜΜ
Η μπορείς να τα βγάζεις από την στοιβα Α, να τα ελέγχεις και να τα βάζεις σε μια άλλη στοιβα Β, και μόλις αδειάσει η Α να τα ξαναβάλεις πίσω βγάζοντας τα από την στόιβα Β και βάζοντας τα στην στοίβα Α
:D
Σωστό κι αυτό!

ΔΗΜΗΤΡΗΣ Χ

ΠΑΙΔΙΑ ΓΙΑΤΙ ΤΟ ΜΠΛΕΚΟΥΜΕ ΤΟΣΟ,
ΚΑΙ ΜΠΕΡΔΕΥΟΥΜΕ ΚΑΙ ΕΜΑΣ ΚΑΙ ΤΟΥΣ ΜΑΘΗΤΕΣ.
ΜΙΑ ΣΤΟΙΒΑ ΥΛΟΠΟΙΕΙΤΑΙ ΜΕ ΕΝΑΝ ΠΙΝΑΚΑ. ΑΝ ΘΕΣ ΝΑ ΔΕΙΣ ΑΠΛΑ ΤΑ ΠΕΡΙΕΧΟΜΕΝΑ ΤΗΣ ΤΗΝ ΧΡΗΣΙΜΟΠΟΙΕΙΣ ΣΑΝ ΠΙΝΑΚΑ. ΓΙΑΤΙ ΔΥΣΚΟΛΕΥΟΥΜΕ ΤΟΣΟ ΤΟ ΜΑΘΗΜΑ ΜΟΝΟΙ ΜΑΣ?
ΣΥΜΦΩΝΩ ΜΕ ΤΑ ΤΕΧΝΙΚΑ ΣΗΜΕΙΑ ΑΛΛΑ ΕΣΤΩ ΟΤΙ ΣΕ ΜΙΑ ΑΣΚΗΣΗ ΘΕΛΟΥΜΕ ΜΕΤΑ ΤΟ ΤΕΛΟΣ ΜΙΑΣ ΕΠΑΝΑΛΗΠΤΙΚΗΣ ΔΙΑΔΙΚΑΣΙΑΣ ΒΑΛΕ - ΒΓΑΛΕ, ΝΑ ΔΟΥΜΕ ΤΙ ΕΧΕΙ ΑΠΟΜΕΙΝΕΙ ΣΤΗ ΣΤΟΙΒΑ - ΠΧ ΦΟΡΤΩΣΗ ΕΜΠΟΡΕΥΜΑΤΩΝ. ΝΑ ΔΟΥΜΕ ΠΧ ΤΟ ΑΘΡΟΙΣΜΑ ΤΩΝ ΔΕΜΑΤΩΝ ΠΟΥ ΔΕΝ ΦΟΡΤΩΘΗΚΑΝ ΑΛΛΑ ΕΜΕΙΝΑΝ ΣΤΗ ΣΤΟΙΒΑ. ΠΟΥ ΧΑΛΑΕΙ ΤΟ ΜΑΘΗΜΑ? Η ΧΡΗΣΗ ΤΗΣ ΩΣ ΣΤΟΙΒΑ ΕΧΕΙ ΓΙΝΕΙ ΜΕΣΩ ΤΩΝ ΩΘΗΣΕΩΝ - ΑΠΩΘΗΣΕΩΝ ΣΕ ΜΙΑ ΛΟΓΙΚΗ ΣΕΙΡΑ ΤΗΣ ΔΙΑΔΙΚΑΣΙΑΣ ΦΟΡΤΩΣΗΣ ΑΣ ΠΟΥΜΕ (ΤΑ ΤΟΠΟΘΕΤΕΙ ΚΑΠΟΙΟΣ ΣΤΗ ΣΤΟΙΒΑ ΚΑΙ ΚΑΠΟΙΟΣ ΑΛΛΟΣ ΤΑ ΒΑΖΕΙ ΣΤΟ ΦΟΡΤΗΓΟ.)... ΓΙΑΤΙ ΝΑ ΤΟ ΜΠΛΕΞΟΥΜΕ? ΘΕΩΡΩ ΠΩΣ ΜΠΟΡΕΙ ΝΑ ΓΙΝΕΙ ΣΤΑ ΠΛΑΙΣΙΑ ΤΟΥ ΜΑΘΗΜΑΤΟΣ Η ΧΡΗΣΗ ΤΗΣ ΓΙΑ ΚΑΝΟΝΙΚΑ...
ΑΝ ΚΑΝΩ ΛΑΘΟΣ ΣΥΓΝΩΜΗ. ΝΟΜΙΖΩ ΟΤΙ ΤΕΤΟΙΟΥς ΠΕΡΙΟΡΙΣΜΟΥΣ ΘΑ ΕΠΡΕΠΕ ΝΑ ΤΟΥΣ ΘΕΤΕΙ ΤΟ ΒΙΒΛΙΟ ΚΑΙ ΟΧΙ ΕΜΕΙΣ.

ApoAntonis

Θα το βελτιώσω!  :D

Παράθεση από: ripper στις 07 Απρ 2021, 01:19:23 ΜΜ

ΓΙΑ Α[top] ΑΠΟ top ΜΕΧΡΙ 1 ΜΕ_ΒΗΜΑ -1
    ΓΡΑΨΕ Α[Α[top]]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
top <- 0

gpapargi

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

ssimaiof

Θα συμφωνήσω με τον gpapargi. Σε κάθε δομή δεδομένων ορίζονται οι λειτουργίες που μπορεί να γίνουν.
Στη στοίβα έχουμε μόνο ώθηση και απώθηση.
Δεν έχει νόημα (για τη στοίβα) π.χ. ο υπολογισμός αθροίσματος των στοιχείων της στοίβας.
Η Πληροφορική βέβαια εξελίσσεται με αυτό να σημαίνει ότι μπορούν να βγουν νέες δομές πολλές φορές βασισμένες σε κάποιες προϋπάρχουσες. Θα μπορούσαμε ίσως για κάποιο άγνωστο σε μένα λόγο να θέλαμε μια δομή που θα συνδυάζει στοίβα και ταξινόμηση (!! λέμε τώρα και καμιά χαζομάρα). Αυτή όμως θα ήταν κάτι άλλο. Θα μπορούσαμε να την ονομάσουμε Στοίβα++ (κατά το C++). Θα είχε στοιχεία της στοίβας όμως θα ήταν κάτι άλλο.
Πρόσφατα κάπου διάβασα ότι στοίβα και σωρός άρχισαν να τα διαφοροποιούν. Εγώ τα διδάχτηκα (πριν πολλά πολλά χρόνια) σαν το ίδιο πράγμα. Όμως στοίβα λένε αφορά την υλοποίηση με πίνακα και σωρός η υλοποίηση με συνδεσμικές λίστες. Αλήθεια αν υπήρχε η υλοποίηση με συνδεσμικές λίστες και όχι με πίνακα θα κάναμε τέτοιες ερωτήσεις ;
Στα παιδιά αυτό που κατά την άποψή μου πρέπει να περάσει είναι η γενική αφηρημένη έννοια της στοίβας και η υλοποίηση με πίνακα μόνο ώθησης απώθησης. Καμιάς άλλης λειτουργίας.
Μη στην προσπάθειά μας να βγάλουμε (έξυπνα έως διεστραμμένα έξυπνα) θέματα και ερωτήσεις που θα ελέγχουν κατά πόσο κατανόησαν την ύλη άθελά μας δημιουργούμε περισσότερο μπέρδεμα.
Σταύρος Σημαιοφορίδης

George Eco

Παράθεση από: gpapargi στις 21 Απρ 2021, 10:23:26 ΠΜ
Δεν είναι όμως μόνο οι πανελλήνιες. Είναι και η επιστημονικότητα του μαθήματος. Μιλάμε για την αφηρημένη δομή δεδομένων Στοίβα. Θα πρέπει ότι κάνεις να το κάνεις μέσω των επιτρεπόμενων πράξεων δηλαδή μέσω υποπρογραμμάτων που υλοποιούν τις πράξεις. Δεν είναι σωστό να βλέπεις τον πίνακα. Για μένα το πιο σωστό, δεδομένης της ΓΛΩΣΣΑΣ είναι να δούμε τι υποπρογράμματα πρέπει να έχουμε για να κρύβουμε όσο γίνεται την υλοποίηση και μετά ας κάνουμε ακριβώς το ίδιο χωρίς υποπρόγραμμα. Αλλά μέχρι εκεί.
Πολύ μου αρέσει αυτό.