Αποστολέας Θέμα: Στοίβα και Ουρά (new)  (Αναγνώστηκε 3700 φορές)

P.Tsiotakis

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3304
  • agent romanoff you miss me?
    • P.Tsiotakis
Στοίβα και Ουρά (new)
« στις: 02 Νοέ 2015, 12:11:53 πμ »
Ετοίμασα ένα φυλλάδιο για τις Δομές Δεδομένων Στοίβα και Ουρά

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

dihatzou

  • Θαμώνας
  • ***
  • Μηνύματα: 26
Απ: Στοίβα και Ουρά (new)
« Απάντηση #1 στις: 04 Δεκ 2015, 02:28:07 μμ »
Στις σημειωσεις αναφερεις λειτουργιες επι της στοιβας κ της ουρας, οπως αναζητηση κ προσπελαση. Μηπως δεν πρεπει να αναφερθουν καθολου;

P.Tsiotakis

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3304
  • agent romanoff you miss me?
    • P.Tsiotakis
Απ: Στοίβα και Ουρά (new)
« Απάντηση #2 στις: 04 Δεκ 2015, 07:25:28 μμ »
Καλησπέρα,

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

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

dihatzou

  • Θαμώνας
  • ***
  • Μηνύματα: 26
Απ: Στοίβα και Ουρά (new)
« Απάντηση #3 στις: 04 Δεκ 2015, 09:20:54 μμ »
Οχι απλα το λεω γιατι η λογικη λειτουργιας της στοιβας κ της ουρας περιοριζεται στην εισαγωγη-διαγραφη κομβων (lifo-fifo). Οι πινακες ειναι απλα εργαλειο αναπτυξης τους.
Τουλαχιστον εγω αυτο λεω στους μαθητες μου κ φοβαμαι μηπως οι επιπλεον λειτουργιες μπερδεψουν την αντιληψη που εχουν για τις δομες αυτες.
Εκτος αν κανω λαθος...
« Τελευταία τροποποίηση: 04 Δεκ 2015, 09:35:58 μμ από dihatzou »

P.Tsiotakis

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3304
  • agent romanoff you miss me?
    • P.Tsiotakis
Απ: Στοίβα και Ουρά (new)
« Απάντηση #4 στις: 05 Δεκ 2015, 10:39:11 πμ »
Η ώθηση και η απώθηση είναι οι λειτουργίες διαμόρφωσης της στοίβας. Όμως, μετά τη δημιουργία της λογικά θα πρέπει να αξιοποιείται. Συνεπώς εκεί έρχονται άλλες επεξεργασίες. Άλλωστε και το βιβλίο λέει: "οι κύριες επεξεργασίες είναι η ώθηση και η απώθηση.."

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

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

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1427
  • There are always possibilities...
Απ: Στοίβα και Ουρά (new)
« Απάντηση #5 στις: 05 Δεκ 2015, 03:19:15 μμ »
Δεν ξέρω αν κατάλαβα καλά το αντικείμενο της συζήτησης, αλλά στην στοίβα και στην ουρά δεν θέλουμε να 'κρυφοκοιτάμε' στο εσωτερικό της, πχ. στον πίνακα. Οι μόνες λειτουργίες πρόσβασης είναι η ώθηση και απώθηση. Η άμεση προσπέλαση κατευθείαν σε στοιχείο, μέσω του πίνακα, έρχεται σε αντιδιαστολή με αυτό. Όπως και η αναζήτηση η προσπέλαση (έμμεσα)  μπορεί να γίνει με διαδοχικές απωθήσεις. 

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

P.Tsiotakis

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3304
  • agent romanoff you miss me?
    • P.Tsiotakis
Απ: Στοίβα και Ουρά (new)
« Απάντηση #6 στις: 07 Δεκ 2015, 11:50:52 πμ »
Στην άσκηση στοίβας στις οδηγίες https://drive.google.com/file/d/0B4550y5SvJsIZTRJQ1RMOHloZ2s/view
σελίδα 5

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



gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Απ: Στοίβα και Ουρά (new)
« Απάντηση #7 στις: 07 Δεκ 2015, 12:56:44 μμ »
Στην άσκηση στοίβας στις οδηγίες https://drive.google.com/file/d/0B4550y5SvJsIZTRJQ1RMOHloZ2s/view
σελίδα 5

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


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

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 429
  • Real stupidity beats ΑΙ any time
Απ: Στοίβα και Ουρά (new)
« Απάντηση #8 στις: 07 Δεκ 2015, 01:15:28 μμ »
Στην άσκηση στοίβας στις οδηγίες https://drive.google.com/file/d/0B4550y5SvJsIZTRJQ1RMOHloZ2s/view
σελίδα 5

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

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

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Απ: Στοίβα και Ουρά (new)
« Απάντηση #9 στις: 07 Δεκ 2015, 01:35:04 μμ »
Ας αφήσουμε τη λογική που υπάρχει αυτή τη στιγμή. Το ερώτημα είναι: "σε μια στοίβα μπορείς να κάνεις άμεση προσπέλαση σε κάποιο ενδιάμεσο στοιχείο χωρίς να βγάλεις τα από πάνω;" Εγώ λέω όχι. Αν το κάνεις παύει να είναι στοίβα. Επίσης δεν πρέπει να "δεις" τον πίνακα που τη φιλοξενεί (πράγμα που έχει νόημα μόνο σε στατική υλοποίηση).

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 429
  • Real stupidity beats ΑΙ any time
Απ: Στοίβα και Ουρά (new)
« Απάντηση #10 στις: 07 Δεκ 2015, 03:08:22 μμ »
Ας αφήσουμε τη λογική που υπάρχει αυτή τη στιγμή. Το ερώτημα είναι: "σε μια στοίβα μπορείς να κάνεις άμεση προσπέλαση σε κάποιο ενδιάμεσο στοιχείο χωρίς να βγάλεις τα από πάνω;" Εγώ λέω όχι. Αν το κάνεις παύει να είναι στοίβα. Επίσης δεν πρέπει να "δεις" τον πίνακα που τη φιλοξενεί (πράγμα που έχει νόημα μόνο σε στατική υλοποίηση).

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

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Απ: Στοίβα και Ουρά (new)
« Απάντηση #11 στις: 07 Δεκ 2015, 03:13:38 μμ »
Ναι... βασικά παρερμήνευσα αυτό που έγραψες "με τη λογική που υπάρχει αυτή τη στιγμή".
Το κατάλαβα σαν "με τη λογική του βιβλίου", ενώ εσύ εννοούσες "με τη λογική της στοίβας". Συμφωνούμε.

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1427
  • There are always possibilities...
Απ: Στοίβα και Ουρά (new)
« Απάντηση #12 στις: 07 Δεκ 2015, 04:37:06 μμ »
Γνώμη μου πώς ασκήσεις που αφορούν στοίβα, θα πρέπει να είναι σχεδιασμένες για το interface της στοίβας (parser, DFS κλπ).
Συμφωνώ, αν και δεν χρειάζεται να πάμε τόσο μακριά. To undo για παράδειγμα είναι μια εφαρμογή της στοίβας, γνωστή στα παιδιά, που δείχνει πολλά από τα παραπάνω. Για παράδειγμα, το ότι δεν έχει σημασία να απομονώσουμε την 5η πχ. ενέργεια (με άμεση προσπέλαση) γιατί δεν είναι ανεξάρτητη ούτε αυτή, ούτε οι επόμενες.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

iomil

  • Θαμώνας
  • ***
  • Μηνύματα: 24
Απ: Στοίβα και Ουρά (new)
« Απάντηση #13 στις: 16 Φεβ 2016, 03:33:16 μμ »
Δύο ερωτήσεις πάνω στη στοίβα (ίσως λίγο χαζές):
1) αν γνωρίζω ότι μία στοίβα έχει ήδη 10 στοιχεία, θα μπορούσα να γράψω το παρακάτω;
   ΓΙΑ I ΑΠΟ 1 ΜΕΧΡΙ 10
       ΔΙΑΒΑΣΕ ΣΤ[Ι]
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
   Top <-- 10

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

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

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2313
Απ: Στοίβα και Ουρά (new)
« Απάντηση #14 στις: 16 Φεβ 2016, 03:42:41 μμ »
Νομίζω ότι η στοίβα και η ουρά είναι κυρίως υλοποιήσεις LIFO και FIFO
Κάθε κώδικας που υλοποιεί αυτές τις ιδέες θα πρέπει να θεωρείται σωστός
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής