ψευδογλωσσα μπλοκαρισμα

[billydot]

να σχεδιασετε ενα αλγοριθμο που να αντιγραφει τα περιεχομενα μιας ουρας σε μια στοιβα,ετσι ωστε τα περιεχομενα και στις δυο να διατρεχονται με την ιδια σειρα . δεν θελω καμια λυση αυθαιρετη μονο συμβουλες δεν ειναι ουτε ασκηση ουτε τιποτα απλα επειδη εχει πεσει σε παλαιοτερα θεματα θα ηθελα να ειχα μια ιδεα για το πως μπορει να γινει ευχαριστω εκ το προτερων.

[gon1332]

Μία ουρά ακολουθεί την πολιτική FIFO (First In First Out), που σημαίνει ότι το πρώτο στοιχείο που θα "μπει" σε αυτή τη δομή θα "βγει" και πρώτο, όπως μία ουρά στην τράπεζα.

 

Μία στοίβα ακολουθεί την πολιτική LIFO (Last In First Out), που σημαίνει ότι το πρώτο που θα εισαχθεί, θα εξαχθεί τελευταίο, όπως συμβαίνει με τα φύλλα μίας τράπουλα σε μία στοίβα.

 

Let's visualize it:

FIFO

       ----------------------
  <--   a  b  c  d  e  f  g   <--
       ----------------------
    out                      in

LIFO

      +----------------------
      | a  b  c  d  e  f  g   <-- & -->
      +----------------------
                             in/out

Στην ουσία θέλεις εσύ πρέπει να διατρέχεις ένα-ένα τα στοιχεία της ουράς, από in σε out και στη συνέχεια θα τα εισάγεις στη στοίβα.

Με αυτή τη τεχνική, το πρώτο στοιχείο που θα διαβάσεις από την ουρά, δηλαδή το g, το οποίο προβλέπεται να βγει τελευταίο από αυτή θα εισαχθεί πρώτο στη στοίβα. Επίσης, όπως είπαμε στη στοίβα ό,τι μπει πρώτο, βγαίνει τελευταίο, άρα πετύχαμε τη λειτουργικότητα της ουράς γι' αυτό το στιγμιότυπο διάτρεξης.

 

Για να το κάνεις πιο γενικό, αν και μάλλον δε θα ζητείται κάτι τέτοιο, πρέπει να ελέγχεις συνέχεια την ουρά σου για τυχόν νέα εισαγωγή στοιχείου. Αν συμβεί κάτι τέτοιο, πρέπει να το εισάγεις στον "πάτο" της στοίβας σου και όχι στην αρχή. Στην ουσία παρανομείς για να πετύχεις αυτό που θέλεις.

 

EDIT: Αν μπορείς άλλαξε τον τίτλο του topic σε κάτι πιο περιγραφικό για το κοινό.

[billydot]

σε ευχαριστω,δηλαδη θα βγαζω το στοιχειο απο την ουρα και θα το βαζω στην στοιβα τοσο απλα 

[gon1332]

σε ευχαριστω,δηλαδη θα βγαζω το στοιχειο απο την ουρα και θα το βαζω στην στοιβα τοσο απλα 

 

Σωστά, αρκεί να το βγάζεις από το σωστό σημείο της ουράς, δηλαδή το in. Το τελικό αποτέλεσμα θα είναι κάπως έτσι:

Αν η FIFO ήταν έτσι

    ----------------------
<--  a  b  c  d              <--
    ----------------------
 out                      in

τότε η LIFO με τη διάτρεξη του αλγορίθμου ανά στοιχείο προκύπτει έτσι:

+----------------------
| d                    <-- & -->
+----------------------
                       in/out

+----------------------
| d  c                 <-- & -->
+----------------------
                       in/out

+----------------------
| d  c  b              <-- & -->
+----------------------
                       in/out

+----------------------
| d  c  b  a           <-- & -->
+----------------------
                       in/out

[defacer]

Σωστά, αρκεί να το βγάζεις από το σωστό σημείο της ουράς, δηλαδή το in.

 

Μα ο ορισμός του in είναι πως δε μπορείς να βγάλεις από εκεί, το λέει και το όνομα.

 

Γενικά προτείνεις πράγματα ("να βάλεις στον πάτο της στίβας") τα οποία νομίζω πως εξ' ορισμού δεν επιτρέπονται. Εγώ αν διατύπωνα άσκηση και έλεγα stack, πάει να πει ότι έχεις στη διάθεσή σου push και pop, τελεία. Αντίστοιχα αν μου έλεγες "βγάζω από το in του queue" θα σου έλεγα "δεν έχεις καταλάβει τι είναι queue" μιας και πας κόντρα στον ορισμό της έννοιας.

 

Για μένα η λύση αυτού του προβλήματος είναι π.χ. να κάνεις dequeue ένα ένα τα στοιχεία και push σε ένα stack, οπότε θα γίνει αυτό:

Queue: [IN]     d c b a  [OUT]
Stack: [BOTTOM] a b c d  [TOP]

και μετά να κάνεις pop ένα ένα τα στοιχεία από το stack και push σε ένα δεύτερο stack οπότε θα γίνει αυτό:

Stack #2: [BOTTOM] d c b a [TOP]

Οπότε βγάζοντας τώρα ένα ένα τα στοιχεία από το δεύτερο αυτό stack θα βγουν με την ίδια σειρά που βγήκαν αρχικά από το queue.

[gon1332]

Συμφωνώ με αυτό που λες, αλλά το παιδί έγραψε για αντιγραφή. με το dequeue είναι σα να κάνεις extract.

Η λογική μου βασίστηκε στο γεγονός πως σε μία ουρά γνωρίζουμε 2 δείκτες, τον in και τον out. Δε μίλησα

για εξαγωγή από το in, αλλά για αντιγραφή. Βέβαια για τη στοίβα έχεις ακόμη πιο μεγάλο δίκαιο και γι'αυτο

διευκρίνησα ότι πρόκειται για παρανομία. Βέβαια υπάρχουν αρχιτεκτονικές οι οποίες δείχνουν στον "πάτο"

της στοίβας δεδομένων μέσω κάποιου δείκτη, όπως πχ ο frame pointer register του MIPS.

[defacer]

Η λογική μου βασίστηκε στο γεγονός πως σε μία ουρά γνωρίζουμε 2 δείκτες, τον in και τον out.

 

Αυτό το γνωρίζουμε μόνο όταν είμαστε η ουρά (και ακόμα και τότε όχι πάντα, π.χ. η std::queue στη c++ είναι container adapter και για να παρέχει τις υπηρεσίες της χρησιμοποιεί έναν άλλο container, ο οποίος δεν αποκαλύπτει τίποτα σχετικό στην queue).

 

Όταν χρησιμοποιούμε την ουρά έχουμε στη διάθεσή μας μόνο το public interface, από το οποίο δε γνωρίζουμε τίποτα τέτοιο (αυτό είναι και ένα από τα βασικά χαρακτηριστικά ενός abstract data structure: δε μας ενδιαφέρει πώς υλοποιείται).

[gon1332]

Αυτό το γνωρίζουμε μόνο όταν είμαστε η ουρά (και ακόμα και τότε όχι πάντα, π.χ. η std::queue στη c++ είναι container adapter και για να παρέχει τις υπηρεσίες της χρησιμοποιεί έναν άλλο container, ο οποίος δεν αποκαλύπτει τίποτα σχετικό στην queue).

 

Όταν χρησιμοποιούμε την ουρά έχουμε στη διάθεσή μας μόνο το public interface, από το οποίο δε γνωρίζουμε τίποτα τέτοιο (αυτό είναι και ένα από τα βασικά χαρακτηριστικά ενός abstract data structure: δε μας ενδιαφέρει πώς υλοποιείται).

 

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

[defacer]

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

 

Μα εδώ, στα πλαίσια της άσκησης, είσαι ο τελικός χρήστης. Διαφορετικά σε οποιαδήποτε άσκηση λέει π.χ. "κάντε το με stack", με την άλλη οπτική που παραθέτεις μπορώ να έρθω εγώ και να πω "να έχω εδώ ένα δικό μου stack το οποίο βασικά είναι array και θα το χρησιμοποιήσω σαν array". Πέρα από τη φιλοσοφία δηλαδή, στα πλαίσια μιας άσκησης τι νόημα έχει να το βλέπεις σα δημιουργός;

 

BTW αυτό που λες ότι θα γνώριζες τα πάντα γενικά μιλώντας δεν ισχύει στην πράξη. Όσο περισσότερα γνωρίζεις τόσο λιγότερο reusable είναι η δομή που έγραψες (μιας και για να "γνωρίζεις" κάτι πρέπει να είναι fixed στον κώδικα), και επειδή σ' αυτά τα πράγματα ένας από τους στόχους είναι το reusability έπεται ότι κατευθύνεσαι "από τη δύναμη της βαρύτητας" προς το να ξέρεις όλο και λιγότερα (container adapter που είπα νωρίτερα, δεν ξέρει απολύτως τίποτα για τη δομή).

[gon1332]

BTW αυτό που λες ότι θα γνώριζες τα πάντα γενικά μιλώντας δεν ισχύει στην πράξη. Όσο περισσότερα γνωρίζεις τόσο λιγότερο reusable είναι η δομή που έγραψες (μιας και για να "γνωρίζεις" κάτι πρέπει να είναι fixed στον κώδικα), και επειδή σ' αυτά τα πράγματα ένας από τους στόχους είναι το reusability έπεται ότι κατευθύνεσαι "από τη δύναμη της βαρύτητας" προς το να ξέρεις όλο και λιγότερα (container adapter που είπα νωρίτερα, δεν ξέρει απολύτως τίποτα για τη δομή).

 

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

[albNik]

Αν τα βαλεις απο ουρα σε στοιβα θα τα εχεις αντιστροφα στη στοιβα.

 

Βαλτα απο

ουρα --> προσωρινή στοιβα

προσωρινή στοιβα -->τελικη στοιβα

 

Εδιτ

αυτο ειπε και ο defacer