ADT Stack - ΑΤΔ Στοίβα

ΑΦΗΡΗΜΕΝΟΙ ΤΥΠΟΙ ΔΕΔΟΜΕΝΩΝ (ΑΤΔ) : 

ΑΦΗΡΗΜΕΝΟΙ ΤΥΠΟΙ ΔΕΔΟΜΕΝΩΝ (ΑΤΔ) ABSTRACT DATA TYPES (ADT)

ΑΦΗΡΗΜΕΝΟΣ ΤΥΠΟΣ ΔΕΔΟΜΕΝΩΝ : 

Στοίβα - Stack ΑΦΗΡΗΜΕΝΟΣ ΤΥΠΟΣ ΔΕΔΟΜΕΝΩΝ Πράξη Δημιουργία Πράξη Κενή Πράξη Ώθηση Πράξη Εξαγωγή

ΣΤΟΙΒΑ - STACK : 

Αποτελεί μία συλλογή αντικειμένων με γραμμική διάταξη. Όλες οι εισαγωγές (pushes) και εξαγωγές (pops) πραγματοποιούνται από το ένα άκρο που ονομάζεται κορυφή (top) της στοίβας. Αντίθετα, το άλλο άκρο παραμένει σταθερό και αποτελεί τη βάση (bottom) της στοίβας. 3 ΣΤΟΙΒΑ - STACK

Slide 4: 

ΧΑΡΑΚΤΗΡΙΣΤΙΚΗ ΙΔΙΟΤΗΤΑ της ΣΤΟΙΒΑΣ Το τελευταίο στοιχείο που εισήχθη είναι το πρώτο που θα εξαχθεί. Αποτελεί, κατ’ ουσίαν, μία LIFO (Last In First Out) λίστα. Οπότε, για να αφαιρεθεί ένα αντικείμενο, πρέπει να αφαιρεθούν όλα τα αντικείμενα που βρίσκονται πάνω του. Συνεπώς, ένα αντικείμενο τοποθετείται μόνο στην κορυφή (top) της στοίβας ή εξάγεται μόνο από την κορυφή (top) αυτής.

Slide 5: 

4 είναι οι βασικές πράξεις του ΑΤΔ Στοίβα: Δημιουργία στοίβας Έλεγχος κενής στοίβας Εισαγωγή στη στοίβα (ώθηση – push) Εξαγωγή από την στοίβα (pop)

Slide 7: 

Τις πράξεις αυτές θα τις υλοποιήσουμε χρησιμοποιώντας τη γλώσσα προγραμματισμού C.

Slide 8: 

Η υλοποίηση αφορά στην πιο απλή μορφή του ΑΤΔ Στοίβα χρησιμοποιώντας τη δομή του πίνακα: #define PLITHOS ... /* το μέγεθος του πίνακα */ typedef ... typos_stoixeiou; /* ο τύπος των στοιχείων του πίνακα */ typedef typos_stoixeiou typos_pinaka [PLITHOS]; typedef struct { int top; typos_pinaka pinakas; } typos_stoivas;

Slide 9: 

Πράξη Δημιουργία

Πράξη Δημιουργία : 

Η πράξη Δημιουργία, δημιουργεί μία νέα κενή στοίβα. void dimiourgia (typos_stoivas *stoiva) { stoiva->top = -1; } Πράξη Δημιουργία

Πράξη Δημιουργία : 

Στα αριστερά φαίνεται μία νέα κενή στοίβα. Ο πίνακας της στοίβας στη μνήμη (αριστερά επάνω) και η γραφική απεικόνισή της (αριστερά κάτω). Πράξη Δημιουργία

Slide 12: 

Πράξη Κενή

Πράξη Κενή : 

Η πράξη Κενή, επιστρέφει την τιμή 1 εάν η στοίβα είναι κενή (δεν έχει στοιχεία) ή την τιμή 0 εάν έχει έστω ένα στοιχείο. int keni (typos_stoivas stoiva) { return (stoiva.korifi == -1); } Πράξη Κενή

Slide 14: 

Πράξη Ώθηση (push)

Πράξη Ώθηση (push) : 

Η λειτουργία της πράξης Ώθηση (push) αποτελείται από 3 ενέργειες: Αν η στοίβα είναι γεμάτη, τότε τυπώνεται ένα μήνυμα και σταματά η εκτέλεση του προγράμματος. Η κορυφή (top) δείχνει στην επόμενη θέση. Εισάγεται το νέο στοιχείο στη θέση που δείχνει, πλέον, η κορυφή (top). Πράξη Ώθηση (push)

Πράξη Ώθηση (push) : 

Η πράξη Ώθηση (push): void push (typos_stoivas *stoiva, typos_stoixeiou stoixeio) { if (stoiva->top == PLITHOS-1) printf (“Η στοίβα είναι γεμάτη“); else { stoiva->top++; stoiva->pinakas [stoiva->top] = stoixeio; } } Πράξη Ώθηση (push)

Πράξη Ώθηση (push) : 

Στα αριστερά φαίνεται η ώθηση του πρώτου στοιχείου στην κενή στοίβα. Αριστερά επάνω: ο πίνακας της στοίβας στη μνήμη. Αριστερά κάτω: η γραφική απεικόνισή της. Πράξη Ώθηση (push)

Πράξη Ώθηση (push) : 

Ακολούθως, η ώθηση του δεύτερου στοιχείου στην, πλέον, μη κενή στοίβα. Αριστερά επάνω: ο πίνακας της στοίβας στη μνήμη. Αριστερά κάτω: η γραφική απεικόνισή της. Πράξη Ώθηση (push)

Πράξη Ώθηση (push) : 

Και ούτω καθεξής. Παρατηρείστε ότι η μεταβλητή top αλλάζει καθώς ωθούνται νέα στοιχεία στη στοίβα. Αριστερά επάνω: ο πίνακας της στοίβας στη μνήμη. Αριστερά κάτω: η γραφική απεικόνισή της. Πράξη Ώθηση (push)

Πράξη Ώθηση (push) : 

Μία διαφορετική υλοποίηση της πράξης Ώθηση (push), είναι η χρήση λογικής μεταβλητής, αντί μηνύματος, για τον χειρισμό της περίπτωσης όπου η στοίβα είναι γεμάτη. void push (typos_stoivas *stoiva, typos_stoixeiou stoixeio, int *overflow) { /* αν η στοίβα είναι πλήρης τότε η τιμή της overflow γίνεται 1, αλλιώς 0*/ if (stoiva->top == PLITHOS-1) *overflow = 1; else { *overflow = 0; stoiva->top++; stoiva->pinakas [stoiva->top]=stoixeio } } Πράξη Ώθηση (push)

Πράξη Ώθηση (push) : 

Αντίστοιχα, στο κύριο πρόγραμμα, από όπου και καλείται η πράξη Ώθηση (push), γράφεται ο κώδικας: push (&stoiva, stoixeio, &overflow); if (overflow) /* να γίνει διορθωτική ενέργεια */ else /* To stoixeio εισήχθη επιτυχώς στη στοίβα */ Πράξη Ώθηση (push)

Πράξη Ώθηση (push) : 

Η περίπτωση ώθησης ενόσω η στοίβα είναι γεμάτη. Το στοιχείο δεν θα εισαχθεί στη στοίβα, αλλά ανάλογα με τον αλγόριθμο θα τυπωθεί μήνυμα σφάλματος ή θα συμβεί υπερχείλιση (overflow). Αριστερά επάνω: ο πίνακας της στοίβας στη μνήμη. Αριστερά κάτω: η γραφική απεικόνισή της. Πράξη Ώθηση (push)

Slide 23: 

Πράξη Εξαγωγή (pop)

Πράξη Εξαγωγή (pop) : 

Η λειτουργία της πράξης Εξαγωγή (pop) αποτελείται, όπως και η Ώθηση, από 3 ενέργειες: Αν η στοίβα είναι κενή, τότε τυπώνεται ένα μήνυμα και σταματά η εκτέλεση του προγράμματος. Εξάγεται το στοιχείο που δείχνει η κορυφή (top) από τη στοίβα. Επιστρέφει την τιμή του στοιχείου που εξάχθηκε, στο κύριο πρόγραμμα. Πράξη Εξαγωγή (pop)

Πράξη Εξαγωγή (pop) : 

Η πράξη Εξαγωγή (pop): void pop (typos_stoivas *stoiva, typos_stoixeiou *stoixeio) { if (keni (*stoiva)) printf(“Η στοίβα είναι άδεια“); else { *stoixeio=stoiva->pinakas [stoiva->top]; stoiva->top--; } } Πράξη Εξαγωγή (pop)

Πράξη Εξαγωγή (pop) : 

Εξαγωγή του πρώτου στοιχείου από τη γεμάτη στοίβα. Αριστερά επάνω: ο πίνακας της στοίβας στη μνήμη. Αριστερά κάτω: η γραφική απεικόνισή της. Πράξη Εξαγωγή (pop)

Πράξη Εξαγωγή (pop) : 

Και ούτω καθεξής. Παρατηρείστε ότι η μεταβλητή top αλλάζει καθώς εξάγονται στοιχεία από τη στοίβα. Αριστερά επάνω: ο πίνακας της στοίβας στη μνήμη. Αριστερά κάτω: η γραφική απεικόνισή της. Πράξη Εξαγωγή (pop)

Πράξη Εξαγωγή (pop) : 

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

Πράξη Εξαγωγή (pop) : 

Μία διαφορετική υλοποίηση της πράξης Εξαγωγή (pop), είναι η χρήση, όπως και στην Ώθηση, λογικής μεταβλητής, αντί μηνύματος, για τον χειρισμό της περίπτωσης όπου η στοίβα είναι κενή. void pop (typos_stoivas *stoiva, typos_stoixeiou *stoixeio, int *underflow) { if (keni (*stoiva)) *underflow = 1; else { *underflow = 0; *stoixeio = stoiva->pinakas [stoiva->top]; stoiva->top = stoiva->top --; } } Πράξη Εξαγωγή (pop)

Πράξη Εξαγωγή (pop) : 

Αντίστοιχα, στο κύριο πρόγραμμα, από όπου και καλείται η πράξη Εξαγωγή (pop), γράφεται ο κώδικας: pop (&stoiva, &stoixeio, &underflow); if (underflow) /* να γίνει διορθωτική ενέργεια */ else /* stoixeio είναι το στοιχείο που εξάγεται από τη στοίβα */ Πράξη Εξαγωγή (pop)

Πράξη Εξαγωγή (pop) : 

Απόπειρα εξαγωγής στοιχείου από κενή στοίβα. Δεν θα γίνει καμία εξαγωγή, αντιθέτως και ανάλογα με τον αλγόριθμο θα τυπωθεί μήνυμα σφάλματος ή θα συμβεί υποχείλιση (underflow). Αριστερά επάνω: ο πίνακας της στοίβας στη μνήμη. Αριστερά κάτω: η γραφική απεικόνισή της. Πράξη Εξαγωγή (pop)

ΑΦΗΡΗΜΕΝΟΣ ΤΥΠΟΣ ΔΕΔΟΜΕΝΩΝ : 

Στοίβα - Stack ΑΦΗΡΗΜΕΝΟΣ ΤΥΠΟΣ ΔΕΔΟΜΕΝΩΝ