ΑΝΑΠΤΥΞΗ ΕΦΑΡΜΟΓΩΝ ΣΕ ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΟ ΠΕΡΙΒΑΛΛΟΝ - ΠΛΗΡΟΦΟΡΙΚΗ |
|
Εκτυπώσιμη μορφή:
6o Φυλλάδιο θεωρίας - Κεφ3 Ενότητα 1 Στοίβα Ουρά
|
Ενότητα 1. Δομές Δεδομένων και Αλγόριθμοι
1. Τι ονομάζεται στοίβα;
Στοίβα (stack), ονομάζεται μια δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που βρίσκονται στην κορυφή της στοίβας λαμβάνονται πρώτα, ενώ αυτά που βρίσκονται στο βάθος της στοίβας λαμβάνονται τελευταία.
Η παραπάνω μέθοδος ονομάζεται Τελευταίο Μέσα, Πρώτο Έξω ή LIFO (=Last In First Out).
2. Ποιες είναι οι κύριες λειτουργίες σε μια στοίβα;
• Η ώθηση (push) στοιχείου στην κορυφή της στοίβας. Στη διαδικασία της ώθησης ελέγχουμε αν η στοίβα είναι γεμάτη. Στην περίπτωση που προσπαθήσουμε να «προσθέσουμε» ένα στοιχείο σε μια ήδη γεμάτη στοίβα, έχουμε υπερχείλιση (overflow) της στοίβας.
• Η απώθηση (pop) στοιχείου από τη στοίβα. Στη διαδικασία της απώθησης ελέγχουμε αν υπάρχει ένα τουλάχιστον στοιχείο στη στοίβα. Στην περίπτωση που προσπαθήσουμε να «αφαιρέσουμε» ένα στοιχείο από μία κενή στοίβα, έχουμε υποχείλιση (underflow) της στοίβας.
3. Πως υλοποιείται η στοίβα με χρήση μονοδιάστατου πίνακα;
Χρησιμοποιούμε μια μεταβλητή (top), που δείχνει το στοιχείο που τοποθετήθηκε τελευταίο στην κορυφή της στοίβας. Όταν η στοίβα είναι άδεια, έχει τιμή 0.
• Η ώθηση ενός νέου στοιχείου στη στοίβα (εισαγωγή στοιχείου στον πίνακα) γίνεται πάντα στην κορυφή της.
Συγκεκριμένα, η μεταβλητή top αυξάνεται κατά ένα: top ← top+1 και στη συνέχεια γίνεται η ώθηση του στοιχείου.
• Η απώθηση ενός στοιχείου από τη στοίβα (εξαγωγή από τον πίνακα) γίνεται πάντα από την κορυφή της στοίβας.
Συγκεκριμένα, εξάγεται το στοιχείο που δείχνει η μεταβλητή top και στη συνέχεια η μεταβλητή top μειώνεται κατά ένα: top ← top-1
ΠΡΟΓΡΑΜΜΑ ΣΤΟΙΒΑ
ΜΕΤΑΒΛΗΤΕΣ
ΧΑΡΑΚΤΗΡΕΣ: A[10]
ΑΚΕΡΑΙΕΣ: top, απάντηση, i
ΑΡΧΗ
top <- 0
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'Δώστε 1: ώθηση 2: απώθηση 9:έξοδος'
ΔΙΑΒΑΣΕ απάντηση
ΑΝ απάντηση = 1 ΤΟΤΕ
! *******************
! ώθηση
ΑΝ top < 10 ΤΟΤΕ
top <- top + 1
ΓΡΑΨΕ 'Δώστε τιμή για ώθηση : '
ΔΙΑΒΑΣΕ A[top]
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Γεμάτη στοίβα'
ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ_ΑΝ απάντηση = 2 ΤΟΤΕ
! *******************
! απώθηση
ΑΝ top > 0 ΤΟΤΕ
ΓΡΑΨΕ 'Απώθηση : ', A[top]
A[top] <- ''
top <- top - 1
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Αδεια στοίβα'
ΤΕΛΟΣ_ΑΝ
ΜΕΧΡΙΣ_ΟΤΟΥ απάντηση = 9
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
4. Τι ονομάζεται ουρά;
Ουρά (Queue), ονομάζεται μια δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που τοποθετήθηκαν πρώτα στην ουρά να λαμβάνονται επίσης πρώτα.
Η παραπάνω μέθοδος ονομάζεται Πρώτο Μέσα, Πρώτο Έξω ή FIFO (=First In First Out).
5. Ποιες είναι οι κύριες λειτουργίες σε μια ουρά;
• Η εισαγωγή (enqueue) στοιχείου στο πίσω άκρο της ουράς.
• Η εξαγωγή (dequeue) στοιχείου από το εμπρός άκρο της ουράς.
6. Πως υλοποιείται η ουρά με χρήση μονοδιάστατου πίνακα;
• Χρησιμοποιούμε δύο μεταβλητές, την front (ή εμπρός) που δείχνει τη θέση του 1ου στοιχείου της ουράς και την rear (ή πίσω) που δείχνει τη θέση του τελευταίου στοιχείου.
Ως αρχικές τιμές των μεταβλητών rear και front θεωρούμε το μηδέν.
• Η εισαγωγή ενός νέου στοιχείου γίνεται από το πίσω άκρο της ουράς και η τιμή της μεταβλητής rear αλλάζει ως εξής: rear ← rear+1
Κατά την εισαγωγή, πρώτα αυξάνουμε τον δείκτη rear κατά ένα και μετά εισάγουμε το στοιχείο στον πίνακα.
Αυτό υπό την προϋπόθεση ότι υπάρχει χώρος (rear < max).
Aν το στοιχείου που βάζουμε είναι το πρώτο (rear=1) τότε θέτουμε και front ← 1
• Η εξαγωγή ενός στοιχείου γίνεται από το εμπρός άκρο της ουράς και η τιμή της μεταβλητής front αλλάζει ως εξής: front ← front +1
Κατά την εξαγωγή ενός στοιχείου, αυξάνεται ο δείκτης front κατά ένα (δείχνει στην επόμενη θέση του πίνακα) χωρίς στην πραγματικότητα να γίνεται καμία παρέμβαση στα περιεχόμενα του πίνακα (χωρίς να διαγράφεται κάποιο στοιχείο). Αυτό υπό την προϋπόθεση ότι υπάρχει στοιχείο (front <= rear και front > 0).
Όταν γίνεται εξαγωγή του τελευταίου στοιχείου της ουρά (front = rear) οι δείκτες παίρνουν πάλι τις αρχικές τιμές (0).
• Το πλήθος των στοιχείων που βρίσκονται μέσα στην ουρά είναι :
rear - front +1, αν front > 0 , ή
0 αν η ουρά είναι άδεια (front = 0 και rear =0)
ΠΡΟΓΡΑΜΜΑ ΟΥΡΑ
ΜΕΤΑΒΛΗΤΕΣ
ΧΑΡΑΚΤΗΡΕΣ: A[10]
ΑΚΕΡΑΙΕΣ: f, r, απάντηση, i
ΑΡΧΗ
f <- 0
r <- 0
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'Δώστε 1: εισαγωγή 2: εξαγωγή 9:έξοδος'
ΔΙΑΒΑΣΕ απάντηση
ΕΠΙΛΕΞΕ απάντηση
! *******************
! Εισαγωγή
ΠΕΡΙΠΤΩΣΗ 1
ΑΝ r < 10 ΤΟΤΕ
ΑΝ f = 0 ΤΟΤΕ
f <- 1
r <- 1
ΑΛΛΙΩΣ
r <- r + 1
ΤΕΛΟΣ_ΑΝ
ΓΡΑΨΕ 'Δώστε τιμή για εισαγωγή : '
ΔΙΑΒΑΣΕ A[r]
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Γεμάτη ουρά'
ΤΕΛΟΣ_ΑΝ
! *******************
! Εξαγωγή
ΠΕΡΙΠΤΩΣΗ 2
ΑΝ f > 0 ΤΟΤΕ
ΓΡΑΨΕ 'Eξαγωγή : ', A[f]
A[f] <- ''
ΑΝ f = r ΤΟΤΕ
f <- 0
r <- 0
ΑΛΛΙΩΣ
f <- f + 1
ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Αδεια ουρά'
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΙΛΟΓΩΝ
ΜΕΧΡΙΣ_ΟΤΟΥ απάντηση = 9
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
|
|
|
Για τους ακουστικούς τύπους, που ο ρυθμός μπορεί να τους βοηθήσει στην εκμάθηση της θεωρίας
η αποτύπωση της σε μελωδική μορφή. Μην χάσετε χρόνο βλέποντας τα βίντεο. Δείτε τα μόνο αν σας βοηθάνε στη μελέτη σας! Ιστοσελίδες ΑΙ που χρησιμοποιήθηκαν: https://suno.com:για δημιουργία τραγουδιών https://www.bing.com/images/create : για δημιουργίας εικόνας https://www.heygen.com/ : για δημιουργίας βίντεο 
|
|
|
|
