Στοίβα και Ουρά (new)

Ξεκίνησε από P.Tsiotakis, 02 Νοε 2015, 12:11:53 ΠΜ

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

P.Tsiotakis

Ετοίμασα ένα φυλλάδιο για τις Δομές Δεδομένων Στοίβα και Ουρά

καθώς και σχετικό βίντεο περιγραφής τους


dihatzou

Στις σημειωσεις αναφερεις λειτουργιες επι της στοιβας κ της ουρας, οπως αναζητηση κ προσπελαση. Μηπως δεν πρεπει να αναφερθουν καθολου;

P.Tsiotakis

Καλησπέρα,

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

Αν έχεις μια στοίβα σε κωδικοποίηση, δεν μπορείς να την τυπώσεις;

dihatzou

#3
Οχι απλα το λεω γιατι η λογικη λειτουργιας της στοιβας κ της ουρας περιοριζεται στην εισαγωγη-διαγραφη κομβων (lifo-fifo). Οι πινακες ειναι απλα εργαλειο αναπτυξης τους.
Τουλαχιστον εγω αυτο λεω στους μαθητες μου κ φοβαμαι μηπως οι επιπλεον λειτουργιες μπερδεψουν την αντιληψη που εχουν για τις δομες αυτες.
Εκτος αν κανω λαθος...

P.Tsiotakis

Η ώθηση και η απώθηση είναι οι λειτουργίες διαμόρφωσης της στοίβας. Όμως, μετά τη δημιουργία της λογικά θα πρέπει να αξιοποιείται. Συνεπώς εκεί έρχονται άλλες επεξεργασίες. Άλλωστε και το βιβλίο λέει: "οι κύριες επεξεργασίες είναι η ώθηση και η απώθηση.."

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

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

pgrontas

Δεν ξέρω αν κατάλαβα καλά το αντικείμενο της συζήτησης, αλλά στην στοίβα και στην ουρά δεν θέλουμε να 'κρυφοκοιτάμε' στο εσωτερικό της, πχ. στον πίνακα. Οι μόνες λειτουργίες πρόσβασης είναι η ώθηση και απώθηση. Η άμεση προσπέλαση κατευθείαν σε στοιχείο, μέσω του πίνακα, έρχεται σε αντιδιαστολή με αυτό. Όπως και η αναζήτηση η προσπέλαση (έμμεσα)  μπορεί να γίνει με διαδοχικές απωθήσεις. 

Οπότε ναι όσες από τις γενικές λειτουργίες των δομών έχουν νόημα, υπάρχουν και στη στοίβα και στην ουρά, αλλά αυτό δεν σημαίνει ότι υλοποιούνται με τον ίδιο τρόπο όπως στους πίνακες.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

P.Tsiotakis

Στην άσκηση στοίβας στις οδηγίες https://drive.google.com/file/d/0B4550y5SvJsIZTRJQ1RMOHloZ2s/view
σελίδα 5

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



gpapargi

Παράθεση από: Παναγιώτης Τσιωτάκης στις 07 Δεκ 2015, 11:50:52 ΠΜ
Στην άσκηση στοίβας στις οδηγίες https://drive.google.com/file/d/0B4550y5SvJsIZTRJQ1RMOHloZ2s/view
σελίδα 5

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


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

itt

Παράθεση από: Παναγιώτης Τσιωτάκης στις 07 Δεκ 2015, 11:50:52 ΠΜ
Στην άσκηση στοίβας στις οδηγίες https://drive.google.com/file/d/0B4550y5SvJsIZTRJQ1RMOHloZ2s/view
σελίδα 5

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

Με τη λογική που υπάρχει αυτή τη στιγμή ναι, δεν μπορείς να το κάνεις αλλιώς.

gpapargi

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

itt

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

Μα δεν αλλάζει κάτι σε αυτό που είπα. Αν θες, για κάποιο λόγο να κάνεις αυτό που είπε ο Παναγιώτης (με στοίβα), θα πρέπει να κάνεις pop κάθε στοιχείο και να τα ξανακάνεις (με σωστή σειρά) push πάλι πίσω. Προφανώς και έχεις δίκιο, μια στοίβα είναι ένας adaptor που προσφέρει ένα συγκεκριμένο interface και τον υλοποιείς πάνω από τον πίνακα στην περίπτωσή μας. Δεν έχει νόημα η αναζήτηση ή η τυχαία προσπέλαση, γιατί η στοίβα εξυπηρετεί άλλες λειτουργίες. Γνώμη μου πώς ασκήσεις που αφορούν στοίβα, θα πρέπει να είναι σχεδιασμένες για το interface της στοίβας (parser, DFS κλπ).

gpapargi

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

pgrontas

Παράθεση από: itt στις 07 Δεκ 2015, 03:08:22 ΜΜ
Γνώμη μου πώς ασκήσεις που αφορούν στοίβα, θα πρέπει να είναι σχεδιασμένες για το interface της στοίβας (parser, DFS κλπ).
Συμφωνώ, αν και δεν χρειάζεται να πάμε τόσο μακριά. To undo για παράδειγμα είναι μια εφαρμογή της στοίβας, γνωστή στα παιδιά, που δείχνει πολλά από τα παραπάνω. Για παράδειγμα, το ότι δεν έχει σημασία να απομονώσουμε την 5η πχ. ενέργεια (με άμεση προσπέλαση) γιατί δεν είναι ανεξάρτητη ούτε αυτή, ούτε οι επόμενες.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

iomil

Δύο ερωτήσεις πάνω στη στοίβα (ίσως λίγο χαζές):
1) αν γνωρίζω ότι μία στοίβα έχει ήδη 10 στοιχεία, θα μπορούσα να γράψω το παρακάτω;
   ΓΙΑ I ΑΠΟ 1 ΜΕΧΡΙ 10
       ΔΙΑΒΑΣΕ ΣΤ[Ι]
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
   Top <-- 10

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

    Χωρίς δηλαδή να έχουμε πρώτα ΔΙΑΒΑΣΕ Χ και μετά Χ <-- ΣΤ[Top];

petrosp13

Νομίζω ότι η στοίβα και η ουρά είναι κυρίως υλοποιήσεις LIFO και FIFO
Κάθε κώδικας που υλοποιεί αυτές τις ιδέες θα πρέπει να θεωρείται σωστός
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής