Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Γ΄ Λυκείου => Μήνυμα ξεκίνησε από: P.Tsiotakis στις 02 Νοέ 2015, 12:11:53 πμ

Τίτλος: Στοίβα και Ουρά (new)
Αποστολή από: P.Tsiotakis στις 02 Νοέ 2015, 12:11:53 πμ
Ετοίμασα ένα φυλλάδιο (https://drive.google.com/file/d/0B4550y5SvJsIejFWM0lfektHczA/edit) για τις Δομές Δεδομένων Στοίβα και Ουρά

καθώς και σχετικό βίντεο περιγραφής (https://www.youtube.com/watch?v=j8PETzZtqtY) τους
 
 
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: dihatzou στις 04 Δεκ 2015, 02:28:07 μμ
Στις σημειωσεις αναφερεις λειτουργιες επι της στοιβας κ της ουρας, οπως αναζητηση κ προσπελαση. Μηπως δεν πρεπει να αναφερθουν καθολου;
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: P.Tsiotakis στις 04 Δεκ 2015, 07:25:28 μμ
Καλησπέρα,

δεν τις ανέπτυξα περισσότερο διότι πρόκειται για σάρωση (προσπέλαση) και αναζήτηση σε μονοδιάστατο πίνακα, δηλαδή οι κλασσικές επεξεργασίες.

Αν έχεις μια στοίβα σε κωδικοποίηση, δεν μπορείς να την τυπώσεις;
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: dihatzou στις 04 Δεκ 2015, 09:20:54 μμ
Οχι απλα το λεω γιατι η λογικη λειτουργιας της στοιβας κ της ουρας περιοριζεται στην εισαγωγη-διαγραφη κομβων (lifo-fifo). Οι πινακες ειναι απλα εργαλειο αναπτυξης τους.
Τουλαχιστον εγω αυτο λεω στους μαθητες μου κ φοβαμαι μηπως οι επιπλεον λειτουργιες μπερδεψουν την αντιληψη που εχουν για τις δομες αυτες.
Εκτος αν κανω λαθος...
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: P.Tsiotakis στις 05 Δεκ 2015, 10:39:11 πμ
Η ώθηση και η απώθηση είναι οι λειτουργίες διαμόρφωσης της στοίβας. Όμως, μετά τη δημιουργία της λογικά θα πρέπει να αξιοποιείται. Συνεπώς εκεί έρχονται άλλες επεξεργασίες. Άλλωστε και το βιβλίο λέει: "οι κύριες επεξεργασίες είναι η ώθηση και η απώθηση.."

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

Απλά είπα πριν πως η προσπέλαση και η αναζήτηση είναι προφανείς αλγόριθμοι, αφού ουσιαστικά είναι ένας πίνακας, και γι' αυτό δεν τους ανέφερα.
Απο τη στιγμή που η στοίβα πλέον συζητείται ως υλοποίηση δεν μπορούμε να μείνουμε μόνο στην προσθαφαίρεση στοιχείων...
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: pgrontas στις 05 Δεκ 2015, 03:19:15 μμ
Δεν ξέρω αν κατάλαβα καλά το αντικείμενο της συζήτησης, αλλά στην στοίβα και στην ουρά δεν θέλουμε να 'κρυφοκοιτάμε' στο εσωτερικό της, πχ. στον πίνακα. Οι μόνες λειτουργίες πρόσβασης είναι η ώθηση και απώθηση. Η άμεση προσπέλαση κατευθείαν σε στοιχείο, μέσω του πίνακα, έρχεται σε αντιδιαστολή με αυτό. Όπως και η αναζήτηση η προσπέλαση (έμμεσα)  μπορεί να γίνει με διαδοχικές απωθήσεις. 

Οπότε ναι όσες από τις γενικές λειτουργίες των δομών έχουν νόημα, υπάρχουν και στη στοίβα και στην ουρά, αλλά αυτό δεν σημαίνει ότι υλοποιούνται με τον ίδιο τρόπο όπως στους πίνακες.
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: P.Tsiotakis στις 07 Δεκ 2015, 11:50:52 πμ
Στην άσκηση στοίβας στις οδηγίες https://drive.google.com/file/d/0B4550y5SvJsIZTRJQ1RMOHloZ2s/view
σελίδα 5

μπορεί να ερωτηθεί "αν στο πλοίο έχει επιβιβαστεί το αυτοκίνητο ΚΡΗ5555";
κι αν μπορει να ερωτηθεί, θα αδειάσω τη στοίβα ψάχνοντας και θα την ξαναγεμίσω;


Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: gpapargi στις 07 Δεκ 2015, 12:56:44 μμ
Στην άσκηση στοίβας στις οδηγίες https://drive.google.com/file/d/0B4550y5SvJsIZTRJQ1RMOHloZ2s/view
σελίδα 5

μπορεί να ερωτηθεί "αν στο πλοίο έχει επιβιβαστεί το αυτοκίνητο ΚΡΗ5555";
κι αν μπορει να ερωτηθεί, θα αδειάσω τη στοίβα ψάχνοντας και θα την ξαναγεμίσω;


Η γνώμη μου είναι ότι αν θέλουμε απάντηση σε τέτοιο ερώτημα τότε δεν πρέπει να χρησιμοποιήσουμε στοίβα. Τη στοίβα τη βλέπουμε σαν αφηρημένη δομή δεδομένων με πράξεις ώθηση και απώθηση και αδιαφορώντας για το αν έχει γίνει στατική ή δυναμική υλοποίηση. Αν "δεις" πχ τον πίνακα που  φιλοξενεί την ΑΔΔ της στοίβας και κάνεις άμεση προσπέλαση σε κάποια θέση, τότε δεν είναι στοίβα αυτή η δομή. δεν της φέρεσαι σαν να είναι στοίβα. Για να δεις τι έχει κάποια θέση πρέπει να βγάλεις όλα τα προηγούμενα. Ξαναλέω ότι ανάλογα με το τι ερωτήματα θέλεις να απαντήσεις, διαλέγεις και την κατάλληλη δομή. Μπορεί η στοίβα να μην είναι η καλύτερη επιλογή σε κάποια προβλήματα. Πίνακα από κάτω δεν πρέπει να βλέπεις. 
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: itt στις 07 Δεκ 2015, 01:15:28 μμ
Στην άσκηση στοίβας στις οδηγίες https://drive.google.com/file/d/0B4550y5SvJsIZTRJQ1RMOHloZ2s/view
σελίδα 5

μπορεί να ερωτηθεί "αν στο πλοίο έχει επιβιβαστεί το αυτοκίνητο ΚΡΗ5555";
κι αν μπορει να ερωτηθεί, θα αδειάσω τη στοίβα ψάχνοντας και θα την ξαναγεμίσω;

Με τη λογική που υπάρχει αυτή τη στιγμή ναι, δεν μπορείς να το κάνεις αλλιώς.
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: gpapargi στις 07 Δεκ 2015, 01:35:04 μμ
Ας αφήσουμε τη λογική που υπάρχει αυτή τη στιγμή. Το ερώτημα είναι: "σε μια στοίβα μπορείς να κάνεις άμεση προσπέλαση σε κάποιο ενδιάμεσο στοιχείο χωρίς να βγάλεις τα από πάνω;" Εγώ λέω όχι. Αν το κάνεις παύει να είναι στοίβα. Επίσης δεν πρέπει να "δεις" τον πίνακα που τη φιλοξενεί (πράγμα που έχει νόημα μόνο σε στατική υλοποίηση).
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: itt στις 07 Δεκ 2015, 03:08:22 μμ
Ας αφήσουμε τη λογική που υπάρχει αυτή τη στιγμή. Το ερώτημα είναι: "σε μια στοίβα μπορείς να κάνεις άμεση προσπέλαση σε κάποιο ενδιάμεσο στοιχείο χωρίς να βγάλεις τα από πάνω;" Εγώ λέω όχι. Αν το κάνεις παύει να είναι στοίβα. Επίσης δεν πρέπει να "δεις" τον πίνακα που τη φιλοξενεί (πράγμα που έχει νόημα μόνο σε στατική υλοποίηση).

Μα δεν αλλάζει κάτι σε αυτό που είπα. Αν θες, για κάποιο λόγο να κάνεις αυτό που είπε ο Παναγιώτης (με στοίβα), θα πρέπει να κάνεις pop κάθε στοιχείο και να τα ξανακάνεις (με σωστή σειρά) push πάλι πίσω. Προφανώς και έχεις δίκιο, μια στοίβα είναι ένας adaptor που προσφέρει ένα συγκεκριμένο interface και τον υλοποιείς πάνω από τον πίνακα στην περίπτωσή μας. Δεν έχει νόημα η αναζήτηση ή η τυχαία προσπέλαση, γιατί η στοίβα εξυπηρετεί άλλες λειτουργίες. Γνώμη μου πώς ασκήσεις που αφορούν στοίβα, θα πρέπει να είναι σχεδιασμένες για το interface της στοίβας (parser, DFS κλπ).
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: gpapargi στις 07 Δεκ 2015, 03:13:38 μμ
Ναι... βασικά παρερμήνευσα αυτό που έγραψες "με τη λογική που υπάρχει αυτή τη στιγμή".
Το κατάλαβα σαν "με τη λογική του βιβλίου", ενώ εσύ εννοούσες "με τη λογική της στοίβας". Συμφωνούμε.
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: pgrontas στις 07 Δεκ 2015, 04:37:06 μμ
Γνώμη μου πώς ασκήσεις που αφορούν στοίβα, θα πρέπει να είναι σχεδιασμένες για το interface της στοίβας (parser, DFS κλπ).
Συμφωνώ, αν και δεν χρειάζεται να πάμε τόσο μακριά. To undo για παράδειγμα είναι μια εφαρμογή της στοίβας, γνωστή στα παιδιά, που δείχνει πολλά από τα παραπάνω. Για παράδειγμα, το ότι δεν έχει σημασία να απομονώσουμε την 5η πχ. ενέργεια (με άμεση προσπέλαση) γιατί δεν είναι ανεξάρτητη ούτε αυτή, ούτε οι επόμενες.
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: iomil στις 16 Φεβ 2016, 03:33:16 μμ
Δύο ερωτήσεις πάνω στη στοίβα (ίσως λίγο χαζές):
1) αν γνωρίζω ότι μία στοίβα έχει ήδη 10 στοιχεία, θα μπορούσα να γράψω το παρακάτω;
   ΓΙΑ I ΑΠΟ 1 ΜΕΧΡΙ 10
       ΔΙΑΒΑΣΕ ΣΤ[Ι]
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
   Top <-- 10

2) Για την ώθηση μπορώ να γράψω κατευθείαν:
    ΑΝ Top<N ΤΟΤΕ
        Top <--Top +1
        ΔΙΑΒΑΣΕ ΣΤ[Top]
    ΤΕΛΟΣ_ΑΝ

    Χωρίς δηλαδή να έχουμε πρώτα ΔΙΑΒΑΣΕ Χ και μετά Χ <-- ΣΤ[Top];
Τίτλος: Απ: Στοίβα και Ουρά (new)
Αποστολή από: petrosp13 στις 16 Φεβ 2016, 03:42:41 μμ
Νομίζω ότι η στοίβα και η ουρά είναι κυρίως υλοποιήσεις LIFO και FIFO
Κάθε κώδικας που υλοποιεί αυτές τις ιδέες θα πρέπει να θεωρείται σωστός