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

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

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

konnacarmen

καλησπέρα σε όλους, μπορεί να είναι χαζή η ερώτηση μου αλλα εχω φάει μεγάλο σκάλωμα, Ξέρουμε οτι οταν χρησιμοποιούμε για την στοίβα την διαδικασία εξαγωγής όλων των στοιχείων χρησιμοποιούμε την Μέχρις_ότου.... η ερώτηση μου ειναι μπορούμε να χρησιμοποιήσουμε πχ και την ΓΙΑ ή πρέπει επειδή την διαδάσκουμε με την συγκεκριμένη δομή επανάληψης να χρησιμοποιήσουμε αυτη??


Ευχαριστω πολυυυυυυυυυ

petrosp13

Ίσα ίσα
Μια υλοποίηση με "Για" είναι πολύ πιο λογική!
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

konnacarmen

τελεια ευχαριστω παρα πολυ

P.Tsiotakis

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

ενώ το ΓΙΑ καλύπτει μόνο το β. Προφανώς οποιαδήποτε κωδικοποίηση υλοποιεί την επεξεργασία FIFO είναι ορθή

konnacarmen

Καλησπλέρα να κάνω μια ερώτηση ακόμα.

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

parsenopoulou

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

George Eco

#6
Παράθεση από: parsenopoulou στις 26 Μαρ 2021, 03:19:29 ΜΜ
Kαλησπέρα.
Σύμφωνα με το σχολικό βιβλίο, στο κεφάλαιο 3, οι πίνακες είναι δομές κύριας μνήμης . Αφού λοιπόν η στοίβα και η ουρά υλοποιούνται με πίνακες, είναι κ αυτές δομές κύριας μνήμης, οπότε μιλάμε για προσωρινή αποθήκευση και όχι για μόνιμη όπως στην περίπτωση του σκληρού δίσκου. Άρα κατά την προσωπική μου εκτίμηση  η πρόταση είναι λάθος.

Συμφωνώ. Πολύ απλά, για να γράψεις σε σκληρό δίσκο, χρειάζεστε εντολές διαχείρισης αρχείων. Η ΓΛΩΣΣΑ δε διαθέτει τέτοες εντολές. Στη RAM υλοποιούνται οι δομές αυτές.

konnacarmen

ωραια ευχαριστω παρα πολυυυυυυ

thaaanos

#8
Παράθεση από: petrosp13 στις 08 Μαρ 2021, 08:15:48 ΜΜ
Ίσα ίσα
Μια υλοποίηση με "Για" είναι πολύ πιο λογική!
Θα διαφωνήσω εδώ για "φιλοσοφικούς" λόγους, η χρήση της στοίβας πρέπει να γίνει μέσω της εξαγωγής, μέχρις ότου να αδειάσει. (ή όσο δεν είναι άδεια να εξάγεις)
  
ΓΙΑ TOP ΑΠΟ TOP ΜΕΧΡΙ 1 ΜΕ ΒΗΜΑ -1
    ΓΡΑΨΕ ΣΤΟΙΧΕΙΑ[TOP] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Το παραπάνω όσο λιτό και απέριττο και δελεαστικό και αν είναι μου φαίνεται "κάπως". Και σίγουρα στο μάθημα "Δομές Δεδομένων" θα έπαιρνα 0 αν έγραφα κάτι τέτοιο λολ

petrosp13

Δηλαδή, θέλω να αδειάσω πλήρως μια στοίβα από την θέση ΤΟΡ μέχρι την θέση 1 και δεν θα χρησιμοποιήσω δομή Για;
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

Πέτρος Κ.

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

Παράθεση από: petrosp13 στις 06 Απρ 2021, 02:57:25 ΜΜ
Δηλαδή, θέλω να αδειάσω πλήρως μια στοίβα από την θέση ΤΟΡ μέχρι την θέση 1 και δεν θα χρησιμοποιήσω δομή Για;

evry

Κανονικά δεν θα έπρεπε να μπορείς να χρησιμοποιήσεις δομή Για για να διατρέξεις μια στοίβα.
Αυτό που περιγράφεται στο σχολικό βιβλίο προφανώς και δεν είναι στοίβα! Είναι ένας πίνακας που τον ονομάζουν στοίβα.
Όταν λέμε στοίβα θα έπρεπε να εννοούμε τον αφηρημένο τύπο δεδομένων (ADT) Στοίβα αλλά στη ΓΛΩΣΣΑ δεν μπορούμε να κάνουμε κάτι τέτοιο διότι δεν επιτρέπει τον διαχωρισμό interface/implementation. Μετά σου λέει  κάνουμε Αλγοριθμική και μαθαίνουν και τα παιδιά απέξω ότι κάνουν και τμηματικό προγραμματισμό.
Ο ADT Στοίβα έχει τρεις λειτουργίες:
1) Pop
2) Push
3) isEmpty   (ίσως isFull)
https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Δεν έχει κάτι άλλο. Αν θέλουμε να ξέρουμε πόσα στοιχεία έχει σημαίνει ότι έχουμε δει πέρα από το πρώτο κάτι που παραβιάζει αυτές τις βασικές λειτουργίες της στοίβας.
Υπάρχουν κάποιες υλοποιήσεις που επιτρέπουν επιπλέον λειτουργίες όπως π.χ. ο υπολογισμός του μεγέθους της, όμως στην γενική μορφή δεν επιτρέπεται.
Ωστόσο αν θέλαμε να ξέρουμε πόσα είναι τα στοιχεία της και να έχουμε πρόσβαση σε όλα χωρίς να κάνουμε Pop τότε γιατί να χρησιμοποιούμε Στοίβα και όχι ένα απλό Array?
Κανονικά η σωστή χρήση Στοίβας προϋποθέτει ότι ο κώδικας που την χρησιμοποιεί δεν θα αλλάξει καθόλου είτε υλοποιείται με πίνακα είτε με δυναμική δομή.
Εμείς πάμε κατευθείαν στην υλοποίηση με πίνακα, μιλάμε για Στοίβα, προκαλούμε στους μαθητές σύγχυση αλλά ... κάνουμε Αλγοριθμική και τμηματικό προγραμματισμό.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

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

Παράθεση από: thaaanos στις 06 Απρ 2021, 12:43:54 ΜΜ
  
ΓΙΑ TOP ΑΠΟ TOP ΜΕΧΡΙ 1 ΜΕ ΒΗΜΑ -1
    ΓΡΑΨΕ ΣΤΟΙΧΕΙΑ[TOP] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ


Να προσθέσω απλά ότι υπάρχει κι άλλο πρόβλημα στο παραπάνω, καθώς μεταβάλλεται η αρχική τιμή της ΓΙΑ.

thaaanos

Παράθεση από: Νίκος Αδαμόπουλος στις 07 Απρ 2021, 10:20:01 ΠΜ
Να προσθέσω απλά ότι υπάρχει κι άλλο πρόβλημα στο παραπάνω, καθώς μεταβάλλεται η αρχική τιμή της ΓΙΑ.
Αφού δουλεύει ;)

ripper

Μια χαρά δουλεύει η ΓΙΑ, αρκεί να είναι σε αυτήν τη μορφή:

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

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

alkisg

> Πρόσφατα κάπου διάβασα ότι στοίβα και σωρός άρχισαν να τα διαφοροποιούν.

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

Στοίβα χρησιμοποιούμε όταν δηλώνουμε τοπικές μεταβλητές, π.χ.: char c = 'a';
Σωρό χρησιμοποιούμε όταν κάνουμε malloc (pointers), π.χ.: char *s = (char *) malloc(100);

ΔΗΜΗΤΡΗΣ Χ

#31
ΕΓΩ ΘΑ ΗΘΕΛΑ ΝΑ ΘΕΣΩ ΜΙΑ ΕΡΩΤΗΣΗ:
ΣΤΑ ΠΛΑΙΣΙΑ ΤΟΥ ΜΑΘΗΜΑΤΟΣ, ΕΝΑ ΘΕΜΑ ΣΑΝ ΤΑ ΠΑΡΑΚΑΤΩ ΕΥΣΤΑΘΕΙ?

Ένας λογιστής συνεργάζεται με τον βοηθό του και τοποθετεί τους φακέλους των πελατών για τους οποίους  θέλει να καταγράψουν όνομα, έσοδα, και έξοδα του καθενός σε ένα αρχείο στον υπολογιστή του. Να φτιάξετε πρόγραμμα το οποίο περιγράφει την διαδικασία ως εξης
Α. χρησιμοποιει τρεις πινακες ον[200], ες[200] και εξ[200] για να πραγματοποιηθεί σε αυτούς η λειτουργία της στοίβας
Β. πραγματοποιείται επαναληπτικά η παρακάτω διαδικασία:
Ο χρήστης επιλέγει 'Ω' για τοποθέτηση φακέλου στη στοίβα, 'Α' για να πάρει φάκελο ο βοηθός από τη στοίβα ώστε να περαστούν τα στοιχεία όνομα, έσοδα και έξοδα στον υπολογιστή, και 'Τ' για τερματισμό και βέβαια πραγματοποιείται κάθε φορά η αντίστοιχη λειτουργία.( Στην περίπτωση της τοποθέτησης φακέλου, θα ελέγχει αν υπάρχει χώρος στην στοίβα, θα διαβάζει το όνομα τα έσοδα και τα έξοδα του πελάτη και θα τα τοποθετεί στην αντίστοιχη στοίβα, διαφορετικά θα εμφανίζει μήνυμα «η στοίβα είναι γεμάτη». Στην περίπτωση της απώθησης, θα ελέγχει αν υπάρχει κάποιο στοιχείο στις στοίβες, θα το εμφανίζει και θα το βγάζει από τη στοίβα, διαφορετικά θα εμφανίζει μήνυμα «η στοίβα είναι Άδεια» .

Γ. για τους φακέλους που τοποθετούνται στη στοίβα μετράει το πλήθος τους και εκτυπώνει πόσοι και ποιοι πελάτες εχουν έσοδα>εξοδα κατά περισσότερο από 10.000 ευρώ
Δ. για τους φακέλους που απωθούνται από τη στοίβα για να περαστούν τα στοιχεία, υπολογίζει και εκτυπώνει μεσο όρο εσόδων και εξόδων καθώς και ποιος είχε τα περισσότερα έσοδα
Ε. . Αν στο τέλος δεν έχει απομείνει κανένας  φάκελος στη στοίβα, εκτυπώνει ' η στοιβα άδειασε', διαφορετικα για τους φακέλους που μετά τον τερματισμό της διαδικασίας έχουν απομείνει στη στοίβα, υπολογίζει και εκτυπώνει πόσοι και ποιοι πελάτες έχουν εσοδα>=20.000 ευρώ, περισσότερα έξοδα και ποιος τα έχει.


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

ΕΓΩ ΘΑ ΗΘΕΛΑ ΜΙΑ ΥΠΕΥΘΥΝΗ ΑΠΑΝΤΗΣΗ ΓΙΑ ΤΟ ΑΝ ΤΕΛΙΚΑ ΚΑΤΙ ΤΕΤΟΙΟ ΕΙΝΑΙ ΣΤΑ ΠΛΑΙΣΙΑ ΤΟΥ ΜΑΘΗΜΑΤΟΣ ΜΑΣ.

ssimaiof

Παράθεση από: alkisg στις 21 Απρ 2021, 05:18:55 ΜΜ
> Πρόσφατα κάπου διάβασα ότι στοίβα και σωρός άρχισαν να τα διαφοροποιούν.

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

Στοίβα χρησιμοποιούμε όταν δηλώνουμε τοπικές μεταβλητές, π.χ.: char c = 'a';
Σωρό χρησιμοποιούμε όταν κάνουμε malloc (pointers), π.χ.: char *s = (char *) malloc(100);

Όχι δεν διδάχτηκαν και τα δύο. Όχι το heap. Προφανώς αποτελεί θέμα ελληνικής μετάφρασης των αντίστοιχων αγγλικών όρων. Το stack μεταφράστηκε σε σωρό. Δυστυχώς δεν βρήκα το δικό μου βιβλίο, αλλά βρήκα το Επεξεργασία Δεδομένων σελ. 115 της Γ' τάξης Ενιαίου Πολυκλαδικού Λυκείου (έκδοση 1993) όπου αναφέρει όσα γνωρίζουμε για τη στοίβα χωρίς να αναφέρει πουθενά τον όρο στοίβα αλλά στη θέση της τον όρο σωρό (stack).
Προφανώς από ότι κατάλαβα, όπως τα είπες, ΤΩΡΑ με τον όρο σωρό αναφερόμαστε στο heap.
Ευχαριστώ για τη διευκρίνηση.
Σταύρος Σημαιοφορίδης

ΔΗΜΗΤΡΗΣ Χ

#33
Συνάδελφοι, θα ήθελα τελικα να ξερω κάποια πράγματα για τη στοίβα και την ουρα, ως προς το τι τελικά επιτρέπεται και τι όχι, και το λεω πραγματικά ως ερώτηση και όχι προσπαθώντας να περάσω κάτι.
Επειδή ναι μεν η στοίβα ως δομή και λειτουργια ειναι κάτι πιο αυστηρο ... ωστόσο το βιβλίο γράφει ότι η στοίβα υλοποιείται με μονοδιάστατους πίνακες, ότι 2 είναι οι ΚΥΡΙΕΣ λειτουργιες σε μια στοίβα και οχι οι μοναδικες... και επειδή γενικότερα στο μάθημα θέλουμε οι μαθητές να σκέφτονται ποια εργαλεια θα χρησιμοποιουν και οχι να αποτυπωνουν απλα λυσεις ρωταω τα εξης:
1. μπορουμε να αδειασουμε τη στοιβα με δομη για; πχ τι διαφορα εχουν τα παρακατω (ιδια ερωτηση και για την ουρα)

ΔΙΑΔΙΚΑΣΙΑ αδειασμα( Χ,ΤΟΠ)
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Ι,Χ[100],ΤΟΠ
ΑΡΧΗ
ΑΝ ΤΟΠ<>0 ΤΟΤΕ
     ΓΙΑ Ι ΑΠΟ ΤΟΠ ΜΕΧΡΙ 1 ΜΕ ΒΗΜΑ -1
         ΓΡΑΨΕ 'ΑΠΩΘΕΙΤΑΙ ΤΟ ΣΤΟΙΧΕΙΟ',Χ[Ι]
     ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
     TOP<-0
ΑΛΛΙΩΣ
      ΓΡΑΨΕ ' ΑΔΕΙΑ ΣΤΟΙΒΑ'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

ΔΙΑΔΙΚΑΣΙΑ αδειασμα( Χ,ΤΟΠ)
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Ι,Χ[100],ΤΟΠ
ΑΡΧΗ
ΑΝ ΤΟΠ<>0 ΤΟΤΕ
     ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
         ΓΡΑΨΕ 'ΑΠΩΘΕΙΤΑΙ ΤΟ ΣΤΟΙΧΕΙΟ',Χ[ΤΟΠ]
         ΤΟΠ<-ΤΟΠ-1
     ΜΕΧΡΙΣ_ΟΤΟΥ ΤΟΠ=0
ΑΛΛΙΩΣ
      ΓΡΑΨΕ ' ΑΔΕΙΑ ΣΤΟΙΒΑ'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

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

Θα ήθελα μια υπευθυνη τοποθετηση απο κάποιον αν ξερει.
ευχαριστω πολυ.




thaaanos

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

alkisg

#35
Δηλαδή η διαδικασία "εισαγωγή" στην ουρά επιτρέπεται να κάνει ολίσθηση χρησιμοποιώντας την ουρά σαν πίνακα, με πρόσβαση στα ενδιάμεσα στοιχεία της πέρα από την αρχή και το τέλος της,
αλλά δεν επιτρέπεται να κάνουμε το ίδιο στη στοίβα;

Γιατί την στοίβα την θέλουμε "αφηρημένη δομή" με τις ελάχιστες δυνατές λειτουργίες ακόμα και στο εσωτερικό της υλοποίησής της, και την ουρά όχι; Ο ρατσισμός στις δομές έχει εκπαιδευτικά οφέλη;

Με άλλα λόγια, επιμένω ότι η απευθείας πρόσβαση σε στοιχεία των δομών θα έπρεπε να μην είναι ταμπού, χρησιμοποιείται συχνά σε αυτές τις δομές μέχρι και με υποστήριξη εντολών του hardware. Γιατί να επιτρέπονται οι παραλλαγές της ταξινόμησης φυσαλίδας, π.χ. με "σημαία" ή κάνοντας μόνο 10 επαναλήψεις για να βρούμε τους 10 μεγαλύτερους αριθμούς, και να μην επιτρέπονται οι παραλλαγές στη στοίβα π.χ. με εντολές τύπου peek(top-2);
ΟΚ, οι δομές αυτές είναι ακόμα φρέσκες στην ύλη και να μην βάλουμε ακόμα δύσκολες ασκήσεις, αλλά μην φτάνουμε στο σημείο να αναφέρουμε τις παραλλαγές τους σαν αντι-επιστημονικές...

thaaanos

Νομιζω οτι υπάρχει μια παρανόηση σχετικά με το Χρήστη σε σχέση με τον Προγραμματιστή της Δομής.
Ο Χρήστης δεν μπορεί να χρησιμοποιήσει την δομή παρα μόνο μέσω των λειτουργιών που προσφέρει ο Προγραμματιστής της.
Ακόμα και αν αυτός είναι το ίδιο πρόσωπο.

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

Μπορεί μια υλοποίηση πχ της Ουράς να χρησιμοποιεί μεν πίνακα αλλα τα στοιχεία να είναι κύκλικά τοποθετημένα πχ, τοτέ το
Για Ι από Front μέχρι Rear να μήν σκαναρει τίποτα γιατί μπορέι κάλλιστα το Front > Rear

ΔΗΜΗΤΡΗΣ Χ

#37
Παράθεση από: thaaanos στις 23 Απρ 2021, 10:05:25 ΠΜ
Πιο σωστό είναι για εμενα το δεύτερο γιατι σε κάθε απώθηση ενημερώνεται το TOP. και όχι μια και καλη στο τέλος. Το πρόβλημα θα ήταν πιο προφανές ισως αν είχες παραλληλισμό και πολλές διεργασίες χρησιμοποιούσαν την στοιβα, δεν θες τότε μετά από κάθε απώθηση να μεινει η στοιβα σε ασυνεπή κατάσταση.

Θάνο Σε ευχαριστώ για τη τοποθέτησή σου η οποία έχει λογική και συμφωνώ εν μερει. Ωστόσο όταν πάμε για κάποιο άδειασμα όπως για παράδειγμα στην λυμένη άσκηση του βιβλίου με το πλοίο, δεν μας ενδιαφέρον οι ενδιάμεσες καταστάσεις. Αλλα Αν ακόμα γίνει και αυτό και θες να ελέγχεις ενδιάμεσα τη στοιβα, μπορείς μέσα στη για να βάλεις τις κατάλληλες εντολές. γενικά πιστεύω ότι πρέπει να μελετάται ως μία δομή πίνακα και απλά με τις λειτουργίες ώθηση και απώθηση, να προσομοιώνονται τα διάφορα προβλήματα και αυτό έχω καταλάβει από τις αναφορές των βιβλίων του μαθήματος.
Θα συμφωνήσω πλήρως με τις παρατηρήσεις του Άλκη και γενικά νομίζω ότι κακώς τίθενται αυτοί οι περιορισμοί.
Δηλαδή στοιβα - ουρα = μονοδιάστατοι πίνακες συνοδευόμενοι με τις αναφερόμενες στο βιβλίο λειτουργίες και με ασκήσεις επικεντρωμένες μεν σε αυτές τις βασικές λειτουργίες χωρίς όμως τρελούς περιορισμούς που έχουν να κάνουν με τεχνικά θέματα. Και βέβαια ως πρώτη χρονιά ουσιαστικά για αυτές τις δομές, θα συμφωνήσω με τον Άλκη πάλι ότι καλό είναι να είμαστε λίγο συγκρατημένοι.
Τελευταιο πάλι όμως θα γράψω ότι θα ήθελα να γινόταν μία υπεύθυνη τοποθέτηση, παρότι νομίζω, και το τονίζω ότι νομίζω, ότι το όλο θέμα κακώς διυλίζεται τόσο.
(Συμπεριλαμβανομένου και εμένα :D)

thaaanos

Να σήμειώσω εδώ οτι ο αλγόριθμος εισαγωγής/ εξαγωγής σε στοίβα και ουρά ειναι **ανεξάρτητος** από την υλοποιηση και γιαυτό επιμένω να ακολουθείτε η λογική του ακόμα και αν δεν δινεται ως υποπρόγραμμα.
και εξηγώ

υποθέστε 1 γραμμική αποθήκη Q, 2 δείκτες που δειχνουν την αρχή και το τέλος, f,r

εισαγωγή Δ:
προχώρα το f κατα μία θέση
τοποθέτησε το Δ στην θέση f

Εξαγωγή Δ
Πάρε το Δ από την θέση r
προχώρα το r κατα μια θέση

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


evry

Δηλαδή η στοίβα που υλοποιείται με δυναμική δομή δεδομένων δεν είναι στοίβα? Είναι άλλη δομή?
Επίσης αν αυτά είναι πίνακες τι κουραζόμαστε με ορισμούς στοίβας και ουράς? Γιατί να μην μιλάμε κατευθείαν για πίνακες? Τι παραπάνω κερδίζουμε;
Για ποιον λόγο να χρησιμοποιούμε ώθηση/απώθηση αφού μπορούμε να έχουμε πρόσβαση σε οποιοδήποτε στοιχείο του πίνακα-στοίβα;

Παράθεση από: ΔΗΜΗΤΡΗΣ Χ στις 23 Απρ 2021, 12:12:10 ΜΜ
Δηλαδή στοιβα - ουρα = μονοδιάστατοι πίνακες συνοδευόμενοι με τις αναφερόμενες στο βιβλίο λειτουργίες και με ασκήσεις επικεντρωμένες μεν σε αυτές τις βασικές λειτουργίες χωρίς όμως τρελούς περιορισμούς που έχουν να κάνουν με τεχνικά θέματα.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

dpa2006

Computer science (abbreviated CS or CompSci) is the scientific and practical approach to computation and its applications. It is the systematic study of the feasibility, structure, expression, and mechanization of the methodical processes (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information, whether such information is encoded in bits and bytes in a computer memory or transcribed engines and protein structures in a human cell.source:http://en.wikipedia.org/wiki/Computer_science

petrosp13

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

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

Φυσικά και θα κουραζόμαστε με τους ορισμούς της στοίβας και ουράς, γιατί αλλιώς ο μαθητής δεν μπορεί να κατανοήσει ότι μιλάμε για κάτι πολύ συγκεκριμένο και όχι απλά για μια (ακόμη) άσκηση με πίνακες
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

alkisg

Παράθεση από: petrosp13 στις 24 Απρ 2021, 01:20:37 ΠΜ
...τον αναγκάζεις να προσπελαύνει μόνο τον κόμβο της κορυφής, αλλιώς η λύση του είναι λανθασμένη, αφού δεν υλοποιεί στοίβα με χρήση πίνακα...

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

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

petrosp13

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

alkisg

Πέτρο λέω για τις ενδεικτικές λύσεις ασκήσεων:
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), και την υλοποιήσω, πάλι στοίβα είναι, ελαφρώς προσαρμοσμένη χωρίς να χάνονται οι χαρακτηριστικές της ιδιότητες.

ΔΗΜΗΤΡΗΣ Χ

Παράθεση από: 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), και την υλοποιήσω, πάλι στοίβα είναι, ελαφρώς προσαρμοσμένη χωρίς να χάνονται οι χαρακτηριστικές της ιδιότητες.

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