Καθηγητής Πληροφορικής, ΠΕ86

3.4 (ΠΒ) – 1.1, 1.1.1, 1.1.2 (ΝΒ)

Στοίβα
 ΣΥΖΗΤΗΣΕΙΣ ΕΝΟΤΗΤΑΣ

ΘΕΩΡΙΑ – ΠΑΡΑΔΕΙΓΜΑΤΑ

Από το σχολικό βιβλίο:

Κ3Ε ΘΕΩΡΙΑ ΠΒ

Κ1Α ΘΕΩΡΙΑ ΝΒ

Σημειώσεις – Διαφάνειες:

ΔΙΑΦΑΝΕΙΕΣ – (612η μέχρι 626η)

MORE…

Βιντεομαθήματα:

Στοίβα – ΣΠΥΡΟΣ ΓΕΩΡΓΙΟΣ ΖΥΓΟΥΡΗΣ

Στοίβα-Ασκήσεις – ΣΠΥΡΟΣ ΓΕΩΡΓΙΟΣ ΖΥΓΟΥΡΗΣ

ΕΡΩΤΗΣΕΙΣ

Από το σχολικό βιβλίο:

Από άλλο υλικό:

ΑΣΚΗΣΕΙΣ

Από το σχολικό βιβλίο:

Από άλλο υλικό:

Άσκηση 1

Να γράψετε πρόγραμμα σε ΓΛΩΣΣΑ το οποίο να διαβάζει ακεραίους αριθμούς και να τους ωθεί σε στοίβα 50 το πολύ στοιχείων. Όταν γεμίσει η στοίβα να γίνει απώθηση όλων των στοιχείων της στοίβας μέχρι αυτή να αδειάσει.

Λύση

ΠΡΟΓΡΑΜΜΑ ΣΤ1
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ :  Σ[50], ΚΟΡΥΦΗ, ΑΡΙΘΜΟΣ
ΛΟΓΙΚΕΣ : DONE
ΑΡΧΗ
ΚΟΡΥΦΗ <-0    !ΓΕΜΙΣΜΑ ΣΤΟΙΒΑΣ – ΩΘΗΣΗ
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΔΙΑΒΑΣΕ ΑΡΙΘΜΟΣ
ΑΝ ΚΟΡΥΦΗ<50 ΤΟΤΕ   !ΕΛΕΓΧΟΣ ΑΝ ΕΧΕΙ ΓΕΜΙΣΕΙ Η ΣΤΟΙΒΑ
ΚΟΡΥΦΗ<-ΚΟΡΥΦΗ+1
Σ[ΚΟΡΥΦΗ]<-ΑΡΙΘΜΟΣ
DONE<-ΑΛΗΘΗΣ
ΑΛΛΙΩΣ 
DONE<-ΨΕΥΔΗΣ !ΟΤΑΝ ΨΕΥΔΗΣ ΣΗΜΑΙΝΕΙ ΟΤΙ ΓΕΜΙΣΕ Η ΣΤΟΙΒΑ
ΤΕΛΟΣ_ΑΝ
ΜΕΧΡΙΣ_ΟΤΟΥ DONE<-ΨΕΥΔΗΣ

!ΑΔΕΙΑΣΜΑ ΣΤΟΙΒΑΣ – ΑΠΩΘΗΣΗ
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ
ΚΟΡΥΦΗ=0 ΤΟΤΕ   !Η ΣΤΟΙΒΑ ΕΙΝΑΙ ΑΔΕΙΑ;
DONE<-ΨΕΥΔΗΣ
ΑΛΛΙΩΣ
ΑΡΙΘΜΟΣ<-Σ[ΚΟΡΥΦΗ]
ΓΡΑΨΕ ΑΡΙΘΜΟΣ
ΚΟΡΥΦΗ<-ΚΟΡΥΦΗ – 1
DONE<- ΑΛΗΘΗΣ
 ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Άσκηση 2

Ένα οχηματαγωγό πλοίο, χωρητικότητας 250 αυτοκινήτων, εκτελεί το δρομολόγιο ΠΕΙΡΑΙΑΣ – ΑΙΓΙΝΑ. Τα οχήματα που επιβιβάζονται πρώτα είναι αυτά που θα αποβιβαστούν τελευταία. Στο λιμάνι του Πειραιά προσέρχονται τα αυτοκίνητα για αναχώρηση. Να γίνει πρόγραμμα το οποίο:

Να υπάρχει μενού επιλογής:

1. Επιβίβαση 2. Αποβίβαση 3. Έξοδος

Στη περίπτωση που επιλεχθεί η Επιβίβαση θα διαβάζει τον αριθμό κυκλοφορίας καθενός από τα αυτοκίνητα που προσέρχονται και ο αριθμός κυκλοφορίας του να καταχωρείται στη στοίβα ΟΧΗΜΑΤΑ. Κάθε φορά που επιβιβάζεται ένα αυτοκίνητο να τυπώνεται το ερώτημα “Υπάρχει άλλο αυτοκίνητο (Ν/Ο); “. Αν ο χρήστης απαντήσει Ν (=ΝΑΙ), επαναλαμβάνεται η διαδικασία επιβίβασης, ενώ αν απαντήσει Ο (=ΟΧΙ), σταματά η διαδικασία επιβίβασης και επιστρέφει το πρόγραμμα στο μενού Επιλογής.
Αν το πλοίο γεμίσει η επιβίβαση σταματά εμφανίζεται κατάλληλο μήνυμα και επιστρέφει το πρόγραμμα στο μενού επιλογής.
Στη περίπτωση που επιλεχθεί η Αποβίβαση, εξάγει και εμφανίζει από την στοίβα ΟΧΗΜΑΤΑ όλους τους αριθμούς αυτοκινήτων που είχαν επιβιβαστεί στον ΠΕΙΡΑΙΑ, με τη σειρά που αποβιβάζονται. Στο τέλος να τυπώνεται το πλήθος των αυτοκινήτων που αποβιβάστηκαν στο λιμάνι της ΑΙΓΙΝΑΣ

Λύση

ΠΡΟΓΡΑΜΜΑ  Λιμάνι
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: τοπ, επ1, πλ
ΧΑΡΑΚΤΗΡΕΣ: επ2, αρ, π[250]
ΑΡΧΗ
τοπ <- 0
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ ‘             Μενού Επιλογών’
ΓΡΑΨΕ ‘              1. Επιβίβαση’
ΓΡΑΨΕ ‘              2. Αποβίβαση’
ΓΡΑΨΕ ‘              3. Έξοδος’
ΓΡΑΨΕ ‘        Δώσε επιλογή:’
ΔΙΑΒΑΣΕ επ1
ΑΝ επ1 = 1 ΤΟΤΕ
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ ‘                  Υπάρχει αυτοκίνητο για επιβίβαση (Ν/Ο);’
ΔΙΑΒΑΣΕ επ2
ΑΝ επ2 <> ‘Ν’ ΚΑΙ επ2 <> ‘ν’ ΚΑΙ επ2 <> ‘Ο’ ΚΑΙ επ2 <> ‘ο’ ΤΟΤΕ
ΓΡΑΨΕ ‘Λάθος επιλογή. Ξαναπροσπάθησε!!!’
ΤΕΛΟΣ_ΑΝ
ΜΕΧΡΙΣ_ΟΤΟΥ επ2 = ‘Ο’ Η επ2 = ‘ο’ Η επ2 = ‘Ν’ Η επ2 = ‘ν’
ΑΝ επ2 = ‘Ν’ Η επ2 = ‘ν’ ΤΟΤΕ
ΑΝ τοπ < 250 ΤΟΤΕ
ΓΡΑΨΕ ‘Δώσε αριθμό κυκλοφορίας του αυτοκινήτου:’
ΔΙΑΒΑΣΕ αρ
τοπ <- τοπ + 1
π[τοπ] <- αρ
ΑΝ τοπ = 250 ΤΟΤΕ
ΓΡΑΨΕ ‘Το πλοίο γέμισε και δεν χωρά άλλα αμάξια’
ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ
ΓΡΑΨΕ ‘Το πλοίο είναι γεμάτο’
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΑΝ
ΜΕΧΡΙΣ_ΟΤΟΥ τοπ = 250 Η επ2 = ‘Ο’ Η επ2 = ‘ο’
ΑΛΛΙΩΣ_ΑΝ επ1 = 2 ΤΟΤΕ
πλ <- 0
ΟΣΟ τοπ >= 1 ΕΠΑΝΑΛΑΒΕ
ΓΡΑΨΕ ‘Αποβιβάζεται το αυτοκίνητο με αριθμό κυκλοφορίας:’, π[τοπ]
π[τοπ] <- ‘ ‘
τοπ <- τοπ  1
πλ <- πλ + 1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ ‘Πλήθος οχημάτων που αποβιβάστηκαν στο λιμάνι της ΑΙΓΙΝΑΣ:’, πλ
ΤΕΛΟΣ_ΑΝ
ΜΕΧΡΙΣ_ΟΤΟΥ επ1 = 3
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ  Λιμάνι

Άσκηση 3

Οι web browsers (π.χ. Mozilla Firefox, Google Chrome) διατηρούν τις διευθύνσεις που επισκεφθήκαμε στο ιστορικό τους ώστε να είναι πιο εύκολη η μετάβαση σε αυτές όταν τις ζητήσουμε ξανά. Για το λόγο αυτό διαθέτουν τα κουμπιά ΕΜΠΡΟΣ και ΠΙΣΩ. Πατώντας σtο κουμπί ΠΙΣΩ ο browser μεταφέρεται στη σελίδα που επισκεφθήκαμε προηγουμένως. Αντίστοιχα, όταν βρισκόμαστε σε μία παλιά σελίδα, πατώντας ΕΜΠΡΟΣ προχωράμε στην αμέσως επόμενη. Κάθε φορά που εισάγουμε μία διεύθυνση, αυτή καταχωρείται στο ιστορικό. Όταν βλέπουμε μία παλιά σελίδα και πληκτρολογούμε μία διεύθυνση, τότε όλες οι μεταγενέστερες διευθύνσεις σβήνονται από το ιστορικό και μπαίνει μόνο αυτή.
Για παράδειγμα, έστω ότι έχουμε επισκεφθεί με τη σειρά τις σελίδες:
google.com -> amazon.co.uk -> facebook.com -> twitter.com -> stackoverflow.com
Αν ο χρήστης πατήσει 3 φορές πίσω, τότε θα πρέπει να μεταβεί στη σελίδα amazon.co.uk
Στην συνέχεια, αν πατήσει μπροστά, θα μεταβεί στην σελίδα facebook.com
Αν στη συνέχεια επιλέξει να εισάγει μια νέα διεύθυνση (π.χ. gmail.com), τότε οι σελίδες twitter.com και stackoverflow.com διαγράφονται από το ιστορικό και η διεύθυνση gmail.com τοποθετείται στην κορυφή, όπως φαίνεται παρακάτω:
google.com -> amazon.co.uk -> facebook.com -> gmail.com
Να γράψετε πρόγραμμα το οποίο θα χρησιμοποιεί μία στοίβα 200 θέσεων και θα εκτελεί τις παρακάτω λειτουργίες:
1) Θα ζητάει από τον χρήστη την εισαγωγή μίας εκ των τιμών, ΕΙΣΑΓΩΓΗ, ΠΙΣΩ, ΕΜΠΡΟΣ, ΕΞΟΔΟΣ. Δεν απατείται έλεγχος εγκυρότητας.
2) Όταν ο χρήστης γράψει ΕΙΣΑΓΩΓΗ τότε θα ζητείται η διεύθυνση του χρήστη και θα τοποθετείται στην στοίβα, ακριβώς μετά την τρέχουσα διεύθυνση.
3) Όταν ο χρήστης γράψει ΠΙΣΩ, το πρόγραμμα θα πρέπει να εμφανίζει την διεύθυνση που εισήγαγε προηγουμένως, εφόσον υπάρχει.
4) Όταν γράψει ΕΜΠΡΟΣ, θα πρέπει να εμφανίζει την επόμενη διεύθυνση εφόσον υπάρχει.
5) Μετά το τέλος των εντολών που περιγράφονται στα ερωτήματα 2, 3 και 4 το πρόγραμμα να ζητά νέα εντολή, όπως περιγράφεται στο ερώτημα 1. Η επανάληψη να τερματίζει όταν δοθεί η λέξη ΕΞΟΔΟΣ.
Σημείωση: Δεν απαιτείται έλεγχος για την περίπτωση της υπερχείλισης

Λύση

ΠΡΟΓΡΑΜΜΑ περιηγητές
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: τοπ, τρέχων
  ΧΑΡΑΚΤΗΡΕΣ: ενέργεια, ιστορικό[200] 
ΑΡΧΗ
  τοπ <- 0 ! Ο δείκτης τοπ δείχνει στην τελευταία έγκυρη διεύθυνση στον πίνακα
  τρέχων <- 0 ! Ο δείκτης τρέχων δείχνει στη διεύθυνση όπου ο χρήστης βρίσκεται αυτή τη στιγμή
  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    ΔΙΑΒΑΣΕ ενέργεια
    ΑΝ ενέργεια = "ΕΙΣΑΓΩΓΗ" ΤΟΤΕ
      τρέχων <- τρέχων + 1
      ΔΙΑΒΑΣΕ ιστορικό[τρέχων] 
      τοπ <- τρέχων ! μετά από εισαγωγή, ακύρωσε όλα τα παλιά στοιχεία
    ΑΛΛΙΩΣ_ΑΝ ενέργεια = "ΠΙΣΩ" ΤΟΤΕ
      ΑΝ τρέχων > 1 ΤΟΤΕ
        τρέχων <- τρέχων - 1
        ΓΡΑΨΕ ιστορικό[τρέχων] 
      ΤΕΛΟΣ_ΑΝ
    ΑΛΛΙΩΣ_ΑΝ ενέργεια = "ΕΜΠΡΟΣ" ΤΟΤΕ
      ΑΝ τρέχων < τοπ ΤΟΤΕ
        τρέχων <- τρέχων + 1
        ΓΡΑΨΕ ιστορικό[τρέχων] 
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ
  ΜΕΧΡΙΣ_ΟΤΟΥ ενέργεια = "ΕΞΟΔΟΣ"
 
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Άσκηση 4

Χορευτικός Σύλλογος

Ένας χορευτικός σύλλογος έχει μέλη άντρες και γυναίκες. Πρόκειται να κάνει μια εκδήλωση με επίδειξη διάφορων χορών, μερικοί από τους οποίους χορεύονται σε ζεύγη που αποτελούνται από έναν άντρα και μία γυναίκα. Επειδή αυτοί οι χοροί προϋποθέτουν κάποια εμπειρία μεγαλύτερη από τους άλλους, ο σύλλογος θα δώσει προτεραιότητα στα αρχαιότερα μέλη του συλλόγου που μπορούν να φτιάξουν ζεύγη, με στόχο όμως να φτιαχτούν όσα περισσότερα ζευγάρια είναι δυνατό.

Να γράψετε πρόγραμμα που:

α) Θα διαβάζει το πλήθος των μελών του συλλόγου ελέγχοντας ώστε να είναι θετικός αριθμός και το πολύ ίσος με 100.
Θα διαβάζει σε έναν μονοδιάστατο πίνακα ΟΝΕΠ τα ονοματεπώνυμα των μελών του συλλόγου και σε έναν παράλληλο με αυτόν πίνακα ΦΥΛΟ το φύλο Α ή Γ του κάθε μέλους, για άντρα ή γυναίκα αντίστοιχα, κάνοντας τον απαιτούμενο έλεγχο εγκυρότητας για το φύλο.
Θεωρείστε δεδομένο ότι τα στοιχεία των μελών εισάγονται με σειρά αρχαιότητας συμμετοχής στο σύλλογο.

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

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

δ) Θα εμφανίζει επίσης πόσα ζευγάρια φτιάχτηκαν για να χορέψουν τελικά.

Λύση

ΠΡΟΓΡΑΜΜΑ ΧΟΡΕΥΤΙΚΟΣ_ΣΥΛΛΟΓΟΣ

ΣΤΑΘΕΡΕΣ

Ν = 100

ΜΕΤΑΒΛΗΤΕΣ

ΧΑΡΑΚΤΗΡΕΣ: ΟΝΕΠ[Ν], ΦΥΛΟ[Ν], StackMen[Ν], StackWomen[Ν], man, woman

ΑΚΕΡΑΙΕΣ: i, topm, topw, πλ, Ζευγάρια

ΑΡΧΗ

! α)

ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ

ΓΡΑΨΕ ‘Δώστε το πλήθος των μελών του συλλόγου’

ΔΙΑΒΑΣΕ πλ

ΜΕΧΡΙΣ_ΟΤΟΥ πλ > 0 ΚΑΙ πλ <= 100

ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ πλ

ΓΡΑΨΕ ‘Δώστε ονοματεπώνυμο μέλους’

ΔΙΑΒΑΣΕ ΟΝΕΠ[i]

ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ

ΓΡΑΨΕ ‘Δώστε το αντίστοιχο φύλλο Α= άντρας ή Γ= γυναίκα’

ΔΙΑΒΑΣΕ ΦΥΛΟ[i]

ΜΕΧΡΙΣ_ΟΤΟΥ ΦΥΛΟ[i] = ‘Α’ Η ΦΥΛΟ[i] = ‘Γ’

ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

!β)

! Ώθηση των ονομάτων στις δύο στοίβες, η προσπέλαση πρέπει να γίνει από την τελευταία

! γεμάτη θέση του πίνακα ΟΝΕΠ προς την πρώτη, για να ωθηθούν τα ονοματεπώνυμα στις

! στοίβες με βάση την περιγραφή που δόθηκε στη διατύπωση της άσκησης.

topm <– 0

topw <– 0

ΓΙΑ i ΑΠΟ πλ ΜΕΧΡΙ 1 ΜΕ ΒΗΜΑ -1

ΑΝ ΦΥΛΟ[i] = ‘Α’ ΤΟΤΕ

topm <–  topm + 1

StackMen[topm] <– ΟΝΕΠ[i]

ΑΛΛΙΩΣ

topw <– topw+ 1

StackWomen[topw] <– ΟΝΕΠ[i]

ΤΕΛΟΣ_ΑΝ

ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

!γ) δ)

ΓΡΑΨΕ ‘Τα ζευγάρια που φτιάχνονται είναι:’

Ζευγάρια <– 0

ΟΣΟ  topm <> 0 ΚΑΙ topw <> 0 ΕΠΑΝΑΛΑΒΕ

man <– StackMen[topm]

woman <– StackWomen[topw]

ΓΡΑΨΕ man, ‘ – ‘, woman

Ζευγάρια <– Ζευγάρια + 1

topm <–  topm – 1

topw <– topw – 1

ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

ΓΡΑΨΕ ‘Συνολικά φτιάχτηκαν ‘, Ζευγάρια, ‘ ζευγάρια’

ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΓΙΑ ΤΟ ΣΠΙΤΙ…

ΣΤΕΙΛΕ ΜΟΥ ΤΙΣ ΑΠΑΝΤΗΣΕΙΣ: ΕΔΩ