Επιλογή δομών δεδομένων βάσει των πραγματικών λειτουργιών

Η στοίβα εξυπηρετεί πρώτα το τελευταίο στοιχείο που προστέθηκε (LIFO), ενώ η ουρά εξυπηρετεί πρώτα το παλαιότερο (FIFO). Το σύνολο είναι κατάλληλο για ελέγχους ύπαρξης, αλλά δεν διατηρεί πολλαπλές εμφανίσεις του ίδιου στοιχείου. Η επιλογή δομής αλλάζει όχι μόνο την ταχύτητα αλλά και την ορθότητα του αποτελέσματος.

Εκτελέσιμο παράδειγμα ουράς στην Python

from collections import deque

pending = deque(["first", "second"])
pending.append("third")
assert pending.popleft() == "first"
assert pending.popleft() == "second"
assert list(pending) == ["third"]

Η deque επιτρέπει αποτελεσματική αφαίρεση από την αρχή. Αν αφαιρείς συνεχώς το πρώτο στοιχείο μιας Python list, τα υπόλοιπα μετακινούνται και κάθε τέτοια πράξη απαιτεί γραμμική δουλειά. Αντίθετα, για στοίβα η list είναι κατάλληλη με append και pop από το τέλος. Η βασική ερώτηση είναι ποιο στοιχείο θέλεις να επεξεργάζεσαι πρώτο.

Έλεγχος κανόνα και ακραία περίπτωση

Αν μπουν στη σειρά A, B, C, μια ουρά επιστρέφει πρώτο το A· η στοίβα επιστρέφει πρώτο το C. Με κενή deque, το popleft προκαλεί IndexError, επομένως ο κώδικας πρέπει είτε να ελέγχει πρώτα αν υπάρχουν στοιχεία είτε να χειρίζεται την εξαίρεση. Ο έλεγχος αυτός είναι μέρος της λογικής του προγράμματος, όχι απλώς λεπτομέρεια της σύνταξης.

Πότε χρησιμοποιούμε set και dictionary;

Για πολλά ερωτήματα «υπάρχει ο κωδικός;» ένα set προσφέρει κατά μέσο όρο γρήγορη αναζήτηση. Αυτό δεν σημαίνει εγγυημένο O(1) στη χειρότερη περίπτωση, επειδή υπάρχουν συγκρούσεις κατακερματισμού. Αν κάθε κωδικός προϊόντος πρέπει να συνδέεται με ποσότητα, χρειάζεται dictionary. Αν πρέπει να διατηρηθούν διπλά συμβάντα με τη σειρά τους, ένα set θα καταστρέψει χρήσιμες πληροφορίες.

Άσκηση με αποδείξιμο αποτέλεσμα

Σχεδίασε επεξεργαστή τεσσάρων εργασιών, με έναν επαναλαμβανόμενο κωδικό. Γράψε την αναμενόμενη σειρά πριν εκτελέσεις το πρόγραμμα. Πρόσθεσε ακύρωση συγκεκριμένης εργασίας και εξήγησε γιατί η αφαίρεση βάσει τιμής διαφέρει από την αφαίρεση του πρώτου στοιχείου. Κατάγραψε έκδοση Python και αληθινή έξοδο αν εκτελέσεις τον κώδικα· μην παρουσιάζεις τη θεωρητική ανάλυση ως πραγματικό benchmark.