καλύτερη υλοποίηση ουράς

[Anastasis13]

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

ΕΙΣΑΓΩΓΗ:

Αν rear = n τότε 
  Γράψε "Γεμάτη ουρά"
αλλιώς 
  rear <- rear + 1 
  Διάβασε ουρά[rear]
τέλος_αν 

ΕΞΑΓΩΓΗ:

Αν rear = 0 τότε 
  Γράψε "Άδεια ουρά"
αλλιώς 
  Γράψε "Εξάγεται το ",ουρά[1]
  Για i από 1 μέχρι rear - 1 ! Ολίσθηση στοιχείων της ουράς στις πρώτες θέσεις, όπως σε μία πραγματική κατάσταση ουράς
    ουρά <- ουρά
  τέλος_επανάληψης 
  rear <- rear - 1
τέλος_αν 

Παρατηρήσεις: 
i. Ο δείκτης rear αρχικοποιείται με τιμή μηδέν ( rear <- 0 ).
ii. Ο δείκτης front είναι περιττός.
iii. Γνωρίζω ότι η ολίσθηση υπάρχει στην άσκηση με το ταχυδρομείο αλλά ο κώδικας εκεί είναι αχρείαστα πολύπλοκος, γιαυτό και προτείνω έναν πιο απλό κώδικα.

[Foto]

Ένας αποδοτικός αλγόριθμος για ουρά χωρίς ολίσθηση θα χρησιμοποιούσε μια δομή με τιμή και δείκτη επόμενης θέσης. Αυτή η δομή λέγεται κόμβος. Όταν ο δείκτης επόμενης θέσης είναι 0 τότε σημαίνει Null, άρα ο κόμβος είναι τερματικός. Τα νούμερα για τους δείκτες θα έρχονται από μια στοίβα που θα χρησιμοποιεί τους κόμβους χωρίς να ενδιαφέρεται για την τιμή στο κόμβο.
Για να δουλέψει όλο αυτό χρειαζόμαστε δύο πίνακες μονοδιάστατους. Ο ένας θα έχει τις τιμές και ο άλλος τους δείκτες  Έστω ότι οι πίνακες έχουν 50 στοιχεία, από 1 μέχρι 50. Η αρχική κατάσταση του πίνακα ΔΕΙΚΤΗΣ[] θα είναι: ΔΕΙΚΤΗΣ[1]<-2 δηλαδή η θέση 1 δείχνει στη θέση 2. Στη θέση 50 θα έχουμε το 0, δεν υπάρχει άλλο! Η στοίβα θα δουλέψει με μια μεταβλητή έστω Σ που θα δείχνει στο 1. Όταν θα θέλουμε κόμβο θα κοιτάμε αν το Σ είναι 0 και αν δεν είναι τότε θα παίρνουμε αυτόν τον κόμβο για χρήση στην ουρά και θα βάζουμε στο Σ την τιμή του ΔΕΊΚΤΗΣ[Σ]. Κάθε φορά που θέλουμε να επιστρέψουμε έναν κόμβο έστω ήταν αυτός στη θέση 10, τότε θα βάζουμε στο ΔΕΙΚΤΗΣ[Σ] την τιμή του Σ και στο Σ το 10. Έτσι δουλεύει η στοίβα για τους κενούς κόμβους.
Για την ουρά χρειαζόμαστε δύο μεταβλητές. Την ΕΙΣ για να βάλουμε το κόμβο που θα εισάγουμε και την ΕΞ για να βάλουμε τον κόμβο που θα εξάγουμε Όταν τα ΕΙΣ και ΕΞ είναι 0 τότε η ουρά είναι άδεια. Αν είναι άδεια η ουρά και θέλουμε να βάλουμε ένα κόμβο έστω τον 10, τότε τα ΕΙΣ και ΕΞ θα πάρουν την τιμή 10, ενώ ο ΔΕΊΚΤΗΣ[10] θα πάρει την τιμή ΕΙΣ που είναι 0. Αν βάλουμε έστω τον κόμβο 15 (ότι μας δώσει η στοίβα) τότε το ΔΕΙΚΤΗΣ[10] θα δείχνει το 15,  όπου το ΕΙΣ είναι το 10, και το ΕΙΣ θα πάρει το 15. Έτσι γεμίζουμε την ουρά. Τι γίνεται όμως στο διάβασμα. Επειδή κατά την εγγραφή της ουράς οι δείκτες δείχνουν προς το τελευταίο που μπήκε στο ΕΞ που είναι το 10 θα μας δώσει ο ΔΕΊΚΤΗΣ[ΕΞ] το 15, και θα το βάλουμε ως νέο ΕΞ. Την επόμενη φορά θα πάρουμε το 0 οπότε μηδενίζουμε και το ΕΙΣ (δηλαδή σε κάθε απόσυρση από την ουρά ελέγχουμε για null τιμή). Μας ενδιαφέρει στο άδειασμα των κόμβων τα ΕΙΣ και ΕΞ να γίνουν 0, γιατί σε επόμενη εισαγωγή πρέπει εκτός από τον ΕΙΣ να φτιάξουμε και τον ΕΞ.
Δεν έχω βάλει την χρήση του άλλου πίνακα, που θα μπουν οι τιμές. Αλλά για τη λογική της ουράς με κόμβους δεν χρειάζεται.
Η ουρά με κόμβους δεν έχει μετακινήσεις. Η χρήση της στοίβας για τους κενούς κύβους απαιτεί μια μεταβλητή και κατάλληλη αρχικοποίηση όλων των δεικτών. Η χρήση της ουράς απαιτεί μόνο δύο μεταβλητές και όλα είναι τυποποιημένα. Στην εισαγωγή ελέγχουμε αν το ΕΙΣ είναι μμηδεν και βάζουμε ίδιο δείκτη κόμβου στα ΕΙΣ και ΕΞ. Στην εξαγωγή του τελευταίου όταν το ΕΞ γίνει μηδέν κάνουμε και το ΕΙΣ μηδέν. Στην εισαγωγή ενός κόμβου εκτός του πρώτου απλά γράφουμε στο ΔΕΙΚΤΗΣ[ΕΙΣ] το το νούμερο του νέου κόμβου, βάζουμε στο ΕΙΣ το νούμερο του νέου κόμβου και στο ΔΕΙΚΤΗΣ[ΕΙΣ] τιμή μηδέν. Στην εξαγωγή αν έχουμε ΕΞ διάφορο του μηδέν τότε βγάζουμε αυτόν τον κόμβο με απλή αντικατάσταση τιμής στο ΕΞ την τιμή του ΔΕΙΚΤΗΣ[ΕΞ], κοιτάμε αν είναι μηδέν και αν ναι τότε αλλάζουμε σε μηδέν και την ΕΙΣ. Επειδή θέλουμε να επιστρέψουμε το κόμβο στη στοίβα πριν αλλάξουμε την ΕΞ κραταμε την τιμή σε μια Επ (επιστρεφόμενο) και κάνουμε το Επ εισαγωγή στη στοίβα.
Δεν υπάρχουν προσθέσεις, αφαιρέσεις, συγκρίσεις μικρό ή και μεγάλο. Γίνονται μόνο μεταθέσεις τιμών και έλεγχος για το μηδέν. Η μόνη πρόσθεση γίνεται στην αρχικοποίηση της στοίβας όπου εκεί ξερά βάζουμε τους δείκτες στην θέση 1 να δείχνει το 2, μέχρι τη θέση 49 να δείχνει την 50 και στην 50 να δείχνει το 0.
Νομίζω ότι με τις οδηγίες αυτές όλοι μπορούν να φτιάξουν μια πετυχημένη ουρά με κόμβους.

[Foto]

Μια απλή οπτικοποίηση του παραπάνω αλγορίθμου γίνεται με βελάκια.
Έστω έχουμε 5 μόνο κενούς κόμβους:
ΕΙΣ = 0
ΕΞ = 0
Σ = 1
1->2 2->3- 3>4 4->5 5->0. (ο 5 δείχνει 0)
Παίρνουμε το κόμβο στο Σ
Σ = 2
2->3 3->4 4->5 5->0
Βάζουμε το κόμβο 1 στην ουρά
ΕΙΣ = 1
ΕΞ = 1
0<-1 (ο 1 δείχνει το 0)
Βάζουμε το κόμβο 2 (δεν δείχνω τώρα τη στοίβα, είναι εύκολο να την κατανόηση κανείς)
ΕΙΣ =  2
ΕΞ =  1
0<-2 2<-1
Εδώ βλέπουμε ότι τον δείκτη στο προηγούμενο ΕΙΣ που δεν είναι 0 (ΕΙΣ διάφορο του μηδέν) είχαμε τιμή μηδέν και μετά την εισαγωγή έγινε τιμή 2.
Στην εξαγωγή από την ουρά ξέρουμε ότι θα πάρουμε τον κόμβο ΕΞ αν δεν είναι μηδέν, και νέα τιμή στο ΕΞ θα δώσουμε το 2 επειδή ο κόμβος 1 έδειχνε το 2
Για να βάλουμε τον κόμβο 1 πίσω στη στοίβα αρκεί να γράψουμε σαν νέο δείκτη την τιμή Σ και να δώσουμε στο Σ το 1.
Σ = 1
1->3 3->4 4->5 5->0
Βλέπουμε ότι στην στοίβα αρχίζουν οι κόμβοι να αλλάζουν την αρχική σειρά. Μας είναι όμως αδιάφορο το πώς θα γίνει.

[Anastasis13]

Ναι αλλά πως ακριβώς θα το καταλάβει όλο αυτό ο μέσος μαθητής που δυσκολεύεται να καταλάβει τι κάνει η ταξινόμηση φυσαλίδας; Η λύση με την ολίσθηση είναι πολύ πιο απλοϊκή και σχετίζεται άμεσα με την πραγματικότητα, επομένως είναι και πιο εύκολη στην κατανόηση.

[alkisg]

https://alkisg.mysch.gr/steki/index.php?topic=8149.0
https://alkisg.mysch.gr/steki/index.php?topic=8654.0

[Foto]

Ναι αλλά πως ακριβώς θα το καταλάβει όλο αυτό ο μέσος μαθητής που δυσκολεύεται να καταλάβει τι κάνει η ταξινόμηση φυσαλίδας; Η λύση με την ολίσθηση είναι πολύ πιο απλοϊκή και σχετίζεται άμεσα με την πραγματικότητα, επομένως είναι και πιο εύκολη στην κατανόηση.

Ο τρόπος που έδειξα είναι πολύ καλύτερος και πιο απλός. Μαθαίνει ο μαθητής ότι ο προγραμματισμός δεν είναι μαθηματικά. Ότι πράγματα (τιμές) μπορούν να διευθετηθούν χωρίς να μετακινηθούν. Η υλοποίηση τέτοιου παραδείγματος μαθαίνει την ουσία στο μαθητή. Όταν ξέρεις την ουσία τότε η ολίσθηση ή οαπλος πίνακας για ουρά είναι παιχνίδι.
Αν μείνει το μάθημα σε καρικατούρες τύπου ουρά με ολίσθηση, τότε δεν χρειάζεται καν να υπάρχει προγραμματισμός, μπορεί άνετα να διδαχθεί με κύβους όπως στο νηπιαγωγείο.

[Anastasis13]

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

[Foto]

Αφού ποτέ δεν έχουν πει στο μαθητή ότι ο οποιοσδήποτε αλγόριθμος που θα γίνει πρόγραμμα πρέπει να διατηρεί μια απλούστατη αρχή: Οποιαδήποτε ενέργεια του εγκεφάλου έχει να κάνει με έναν συσσωρευτή που κρατάει ένα δυαδικό νούμερο. Σε αυτό μπορεί να  κάνει πράξεις με αλλά νούμερα, να κάνει συγκρίσεις πάντα όμως για ένα νούμερο.
Όταν λοιπόν έδωσαν στις εξετάσεις δυαδικό δένδρο με τρεις κόμβους και του ζήτησαν τις τέσσερις εκδοχές για κάθε μία νέα τιμή, νέο κόμβο από ένα σύνολο τεσσάρων κάποιοι έκαναν αναδιάταξη του δένδρου. Με δεδομένη την απλή αρχή που έδειξα παραπάνω η σκέψη του μαθητή θα έπρεπε να πάει στην μια προς μια σύγκριση και να φθάσει στο σημείο που θα "φύτευε" το κόμβο, ακολουθούσε τον κανόνα για τα αριστερά και δεξιά φύλλα. Η αναδιάταξη του δένδρου μπορεί να φαίνεται σωστή αλλά αυτή στέκει μόνο σε νηπιαγωγείο με κυβάκια.

[iordanissav]

https://alkisg.mysch.gr/steki/index.php?topic=8149.0
https://alkisg.mysch.gr/steki/index.php?topic=8654.0

Μπαίνω ξανά στο Στέκι, μετά από χρόνια απουσίας από την ΑΕΠΠ και παρατηρώ παράπονα από μαθητές και συναδέλφους για τις ουρές. Ποιο ήταν δηλαδή το βασικό πρόβλημα μέχρι σήμερα κατά τη διδασκαλία της στην τάξη;
Και για ποιο λόγο να μη διδάσκεται μια υλοποίηση όπως αυτή στην εικόνα, την οποία ανέβασα πρόσφατα στην ομάδα "Εκπαιδευτικοί Πληροφορικής ΠΕ86" στο FB (για όποιον/α την είδε), αντί αυτής της τόσο αστείας του βιβλίου; Δεν πιστεύω ότι οι μαθητές θα είχαν πρόβλημα να υιοθετήσουν αμέσως και διανοητικά.

-- init --
front <- 1
rear <- 0

-- ΕΙΣΑΓΩΓΗ (όπως ακριβώς στη στοίβα) --

Αν rear < Ν τότε
       rear <- rear + 1
       Ουρά[ rear ] <- στοιχείο     
   Αλλιώς
        Γράψε 'Γεμάτη ουρά'
   Τέλος_αν
 
-- ΕΞΑΓΩΓΗ --

Αν front <= rear τότε
       στοιχείο <- Ουρά[ front ]
       front <- front + 1
 
      Αν front > rear τότε ! Η ουρά άδειασε
          front <- 1    ! Διατήρησε τον δείκτη front > rear 
         rear <- 0     ! αλλά τώρα στην αρχή
     Τέλος_αν   
   Αλλιώς       
      Γράψε 'Άδεια ουρά'     
   Τέλος_αν

[alkisg]

@iordanissav με μια γρήγορη ανάγνωση, αν έχουμε ουρά με 10 θέσεις, βάλουμε 10 στοιχεία, βγάλουμε 5, και πάμε να προσθέσουμε 1, η υλοποίησή σου θα βγάλει "γεμάτη ουρά" που δεν ισχύει.

[iordanissav]

@alkisg αυτό δεν το αντιμετωπίζει ούτε η επίσημη λύση, την οποία και ακολούθησα ως προϋπόθεση, δηλ. σε γεμάτη ουρά, να μη γινεται shift στα αριστερά όταν εισάγεται ένα στοιχείο αν υπάρχει χώρος στην αρχή (πολύς φόρτος για την ουρά). Θεωρεί ότι όταν γεμίσει η ουρά, μπορεί μόνο να αδειάζει μέχρι και το τελευταίο στη θέση Ν. Αυτό που καταθέτω είναι μια πιο απλή μορφή με μία εντολή εισαγωγής και εισαγωγής στοιχείου, αντί πολλών στα ΑΛΛΙΩΣ_ΑΝ, "παίζοντας" πιο αποδοτικά με τις front/rear.

Μια πιο πλήρης Εισαγωγή με Shift left αν χρειάζεται, θα δυσκόλευε λίγο την κατανόηση αλλά θα ολοκλήρωνε τους επίσημους αλγορίθμους του νέου βιβλίου, μάλλον θα ήταν η :

! shift αριστερά όταν είναι κατειλημμένο το Ν-στό στοιχείο
! κατά την εισαγωγή, αλλά υπάρχει θέση στην αρχή
Αν rear = N  KAI front > 1 τότε
      count <- rear - front + 1      ! κράτα πόσα είναι μέσα (θα γίνει το νέο rear)
      Για i από 1 μέχρι count
            Ουρά[ i ] <- Ουρά[ front + i - 1]
      τέλος_επανάληψης
      front <-1          ! η ουρά ξεκινά πλέον στην αρχή
      rear <- count   ! και έχει τέλος, το πλήθος που είχε αρχικά.
τέλος_αν

! τώρα μπορεί να εισαχθεί στοιχείο
Αν rear < Ν τότε
       rear <- rear + 1
       Ουρά[ rear ] <- στοιχείο     
Αλλιώς
        Γράψε 'Γεμάτη ουρά'
Τέλος_αν

[alkisg]

@iordanissav ναι όλος ο ντόρος εδώ στο Στέκι γίνεται ακριβώς επειδή πολλοί διαφωνούν με τις επίσημες λύσεις.
Το νέο διδακτικό πακέτο προτείνει είτε χαλασμένη ουρά (να μην γίνεται εισαγωγή ενώ υπάρχουν άδειες θέσεις) είτε αργή ουρά (με ολίσθηση και πολυπλοκότητα Ο(Ν)). Το αρχικό πακέτο δεν είχε αυτά τα προβλήματα.

Κάνοντας μόνο μία πραξούλα (είτε mod N είτε εντολή ΑΝ) η ουρά γίνεται κυκλική, με πολυπλοκότητα Ο(1), δουλεύει πάντα όταν υπάρχουν άδειες θέσεις, δεν χρειάζεται ολίσθηση ούτε εντολή for, και συμβαδίζει με αυτά που διδάσκουμε στα πανεπιστήμια.

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

[Foto]

Our Planet S1:E1 (Netflix)
Στο 20:40 δείχνει το χορό των πουλιών (μπλε μανακίνο), όπου ο αρχηγός με τρεις βοηθούς κάνουν το εκπληκτικό, ένα καρουσελ στυλ, όπου ο πρώτος της σειράς πετάει και πάει στην θέση του τελευταίου, ενώ ταυτόχρονα οι άλλοι τρεις περπατάνε μια θέση στο κλαδί πιο πάνω για να έρθει αυτός που πέταξε. Στο τέλος του κλαδιού είναι το θηλυκό που αξιολογεί τις κινήσεις! Εν τω μεταξύ κάνουν και δοκιμές πριν την παρουσίαση!

Καλό καλοκαίρι!