Κεφάλαιο 7

• Στοίβα (stack)


  Δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που βρίσκονται στην κορυφή της στοίβας λαμβάνονται πρώτα, ενώ αυτά που βρίσκονται στο βάθος της στοίβας λαμβάνονται τελευταία
• Στοίβα


  • Τελευταίο Μέσα, Πρώτο Έξω ή LIFO (=Last In First Out)
• Κύριες λειτουργίες σε μια στοίβα


  • Ώθηση (push) στοιχείου στην κορυφή της στοίβας
  • Απώθηση (pop) στοιχείου από τη στοίβα
• Ώθηση στοιχείου στη στοίβα

  1. Ελέγχουμε αν η στοίβα είναι γεμάτη

  2. Αν είναι γεμάτη, έχουμε υπερχείλιση (overflow) της στοίβας
• Απώθηση στοιχείου από τη στοίβα

  1. Ελέγχουμε αν υπάρχει ένα τουλάχιστον στοιχείο στη στοίβα

  2. Αν είναι κενή, έχουμε υποχείλιση (underflow) της στοίβας
• Υλοποίηση στοίβας με μονοδιάστατο πίνακα

  1. Χρησιμοποιούμε μεταβλητή (top) που δείχνει το στοιχείο που τοποθετήθηκε τελευταίο

  2. Ώθηση: top ← top+1

  3. Απώθηση: top ← top-1
• Ουρά (Queue)


  Δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που τοποθετήθηκαν πρώτα στην ουρά να λαμβάνονται επίσης πρώτα
• Ουρά


  • Πρώτο Μέσα, Πρώτο Έξω ή FIFO (=First In First Out)
• Κύριες λειτουργίες σε μια ουρά

  • Εισαγωγή (enqueue) στοιχείου στο πίσω άκρο της ουράς
  • Εξαγωγή (dequeue) στοιχείου από το εμπρός άκρο της ουράς
• Υλοποίηση ουράς με μονοδιάστατο πίνακα

  1. Χρησιμοποιούμε μεταβλητές front (εμπρός) και rear (πίσω)

  2. Εισαγωγή: rear ← rear+1

  3. Αν είναι το πρώτο στοιχείο, τότε front ← rear
• Ουρά


  Δομή δεδομένων όπου τα στοιχεία που τοποθετήθηκαν πρώτα λαμβάνονται επίσης πρώτα (FIFO)
• Ουρά


  • Εισαγωγή (enqueue) στοιχείου στο πίσω άκρο
  • Εξαγωγή (dequeue) στοιχείου από το εμπρός άκρο
• Υλοποίηση ουράς με μονοδιάστατο πίνακα

  1. Χρησιμοποιούμε μεταβλητές front και rear

  2. Εισαγωγή: Αυξάνουμε rear, εισάγουμε στοιχείο

  3. Εξαγωγή: Αυξάνουμε front, χωρίς να διαγράφουμε στοιχείο
• Όταν γίνεται εξαγωγή του τελευταίου στοιχείου, οι δείκτες παίρνουν πάλι τις αρχικές τιμές (0)
• Πρόγραμμα ουράς


  1. Αρχικοποίηση μεταβλητών f, r

  2. Επανάληψη: Επιλογή 1 για εισαγωγή, 2 για εξαγωγή, 9 για έξοδο

  3. Εισαγωγή: Αυξάνουμε r, εισάγουμε στοιχείο, αν r=1 τότε f=1

  4. Εξαγωγή: Εκτυπώνουμε στοιχείο, αυξάνουμε f, αν f>r τότε f=0, r=0