|
Title: Linked-Lists vs Stacks vs Queues Post by: Egkelados on April 17, 2016, 18:03:09 pm Όντας νέος στον προγραμματισμό μου δημιουργήθηκε η εξής απορία. Για ποιο λόγο να χρησιμοποιούμε stacks και queues όταν έχουμε lists? Μια λίστα η οποία αποτελείται από head, tail και len δεν είναι πολύ πιο ολοκληρωμένη δομή με πολλές περισσότερες δυνατότητες από ότι οι stacks, queues?
Στην περίπτωση της στοίβας χρησιμοποιείς την τεχνική LIFO στην ουρά την FIFO όμως στη λίστα δεν περιορίζεσαι σε κανένα από τα δύο! Μπορείς να προσθέσεις ένα node σε όποιο σημείο της λίστα επιθυμείς μπορείς να το διαγράψεις ανά πάσα στιγμή μπορείς να το βάλεις από την αρχή από το τέλος και γενικά παρατηρώ ότι οι δυνατότητες μιας singly-linked-list είναι πολλές περισσότερες σε σχέση με stack και queue. Σίγουρα κάνω κάποιο λάθος γιατί δεν γνωρίζω πολλά σχετικά με τον προγραμματισμό αφού τώρα ξεκίνησα να μαθαίνω απλά διαβάζοντας, γράφοντας και παρατηρώντας μου δημιουργήθηκε αυτή η απορία και όσο και αν προσπάθησα δεν μπόρεσα να βρω που μπορεί να υπερτερεί μια στοίβα ή μια ουρά έναντι μιας λίστας. Title: Re: Linked-Lists vs Stacks vs Queues Post by: Aristos on April 17, 2016, 19:17:15 pm Υπάρχει διαφορά ανάμεσα σε μια δομή που χρησιμοποιείς όταν γράφεις κώδικα και σε αυτό που λέμε αφηρημένη δομή δεδομένων. Ανάμεσα δηλαδή στην θεωρητική περιγραφή μιας δομής και στην υλοποίηση της σε κάποια γλώσσα προγραμματτισμού. Αυτό που μάλλον εννοείς είναι πως μια συνδεδεμένη λίστα είναι πολύ πιο γενική δομή απο μία στοίβα ή μια ουρά. Συνεπώς, υλοποιώντας μία συνδεδεμένη λίστα είσαι καλυμένος για όλες τις περιπτώσεις. Αν όμως ο αλγόριθμος σου χρειάζεται στοίβα θα ήταν ασφαλέστερο για σένα να χρησιμοποιήσεις μια άλλη δομή που θα υλοποιεί μόνο τα χαρακτηριστικά της στοίβας για να ξέρεις πχ οτι ένα καινούργιο στοιχείο θα εισάγεται ΜΟΝΟ στην κορυφή. Εσωτερικα αυτή η δομή μπορεί να χρησιμοποιεί τη συνδεδεμένη λίστα, αλλα είναι προτιμώτερο ο κώδικας σου να 'βλέπει' μόνο τις λειτουργίες της στοίβας.
Τέτοιου είδους θέματα συζητώνται πολύ σε ένα μάθημα του 5ου εξαμήνου που λέγεται δομές δεδομένων. Αρκετά καλό μάθημα θα έλεγα. Μπορείς να βρεις αρκετό σχετικό υλικό και εδώ και στο eThmmy καθώς και στο βιβλίο του μαθήματος "Δομές Δεδομένων και Αλγόριθμοι στη Java" του Lafore Title: Re: Linked-Lists vs Stacks vs Queues Post by: jimPster on April 17, 2016, 19:18:53 pm Χωρις να θυμαμαι ακριβως τις υλοποιησεις τους.
Αναλογα με την εφαρμογη σου. Αν χρειαζεται την queue δεν θα χρησιμοποιησεις linked-list γτ απλα η queue ειναι πιο γρηγορη και πιανει λιγοτερο χωρο στην μνημη. Και εστω οτι εχουν και ιδιες ταχυτητες (γτ δεν θυμαμαι) η queue σιγουρα πιανει λιγοτερο χωρο ("bookkeeping") μνημης απο linked list. Και αντε μπορει τα στοιχεια σου να ειναι στις χιλιαδες (κλαιν οι διαφορες τους ) αν εχεις εκατομμυρια στοιχεια... Title: Re: Linked-Lists vs Stacks vs Queues Post by: Egkelados on April 17, 2016, 22:09:07 pm Ναι αλλα αυτο δεν μπορω να καταλαβω. Γιατι να χρησιμοποιησω λιστα και ουρα που περιοριζουν τις δυνατοτητες μου? Που χρειαζεται μια τετοια δομη;
Title: Re: Linked-Lists vs Stacks vs Queues Post by: Eragon on April 17, 2016, 22:47:00 pm Όταν χρησιμοποιείς μια λίστα δεσμεύεις συγκεκριμένο συνεχόμενο χώρο στη μνήμη. Αυτός ο χώρος σε ορισμένα συστήματα μπορεί να μην είναι εφικτό να δεσμευτεί εφάπαξ. Η στοίβα και η ουρά προσφέρουν δυναμικότητα στη δέσμευση. Κατά τ'άλλα το ότι μια δομή φαίνεται να είναι κατά κάποιο τρόπο υποσύνολο μιας άλλης δεν την καθιστά αυτομάτως και άχρηστη. Για παράδειγμα, στη java μπορείς να πάρεις το πρώτο στοιχείο μιας λίστας με
Code: if (!myList.isEmpty()) myList.remove(0) Code: myQueue.poll() Δες κι εδώ : http://stackoverflow.com/questions/17436530/when-to-use-queue-over-arraylist (http://stackoverflow.com/questions/17436530/when-to-use-queue-over-arraylist) Title: Re: Linked-Lists vs Stacks vs Queues Post by: jimPster on April 18, 2016, 00:09:58 am "
Stack: In operating systems stack is to stored memory locations when a function is called, when a function calls an another one the OS pushes the return address on the top, when the current routine returns it pops the memory location and the control jumps there. Think how recursive functions can be replaced with a stack? Queue: While we work with a computer, several processes runs behind, each process wants to get some CPU time. Some process needs a lot of time, some need a very little time, some processes needs to processed very urgently. What OS does is to put them in a queue. There are different CPU allocation methods such as batch, time shared etc. In most cases priority queues are used. Linked List: Think about an selection sort algorithm, each time we find the element which needs to be put in the correct position we need to shift the entire elements by one position if we use an array. That could take a lot of time, instead if we use a linked list, all we need to update is 3 links. " Και υπαρχουν και αλλες εφαρμογες... Stacks και queues κατα κορον σε λειτουργικα συστηματα,μικροεπεξεργαστες, parsing κτλ Και επειδη μαλλον τα εχεις μπερδεψει οι δομες δεδομενων δεν περιοριζουν, το αντιθετο... Εχεις εφαρμογη που εχει LIFO λειτουργικοτητα θα χρησιμοποιησεις stack οχι Linked-list γτ δεν χρειαζεσαι την εxtra λειτουργικοτητα ( δεν θα την χρησιμοποιησεις ποτε) Θες αντι για stack na χρησιμοποιησεις linked-list you're welcome to do it αλλα απο κει που το προγραμμα σου ηθελε πχ 50 mb ram για να τρεξει στο pc σ τωρα θελει 100 mb γτ κανεις "bookkeeping (pointers,variables)" για την extra λειτουργικοτητα την οποια δεν τν χρειαζεσαι Εχεις εφαρμογη που θελει και τις 2 λειτουργικοτητες , ε ναι τοτε Linked-list. Ολα εξαρτωνται απο την εφαρμογη σου. Γι' αυτο υπαρχουν δεκαδες δομες δεδομενων με διαφορες ιδιοτητες ,πλεονεκτηματα και μειονεκτηματα στην ταχυτητα και χωρο μνημης. Αλλα ποτε δεν διαλεγεις δομη που κανει extra πραγματα ενω δεν τα χρειαζεται η εφαρμογη σου γτ θα σου τρωει extra ram για το τπτ και ταχυτητα. Αργοτερα αν η εφαρμογη σ θελει και κατι extra μπορεις και αλλαζεις και βαζεις αλλη δομη. Οι δομες διευκολυνουν την ζωη σου, σου προσφερουν ετοιμες και βελτιστοποιημενες λυσεις για προβληματα με συγκεκριμενες ιδιοτητες και αναγκες. Και κατι τελευταιο αναλογικα θελω μια συσκευη ωστε να δεχομαι και να κανω κλησεις σε αλλους, μονο αυτο! Τι θα παρεις smartphone η ενα απλο κινητο? Οπου η τιμη των συσκευων παει αναλογικα με ταχυτητα και μνημη για δομες και λειτουργικοτητες ( απλο κινητο -> stack, smartphone-> linked-list) Title: Re: Linked-Lists vs Stacks vs Queues Post by: Egkelados on April 18, 2016, 01:21:57 am Σας ευχαριστώ όλους παιδιά η βοήθεια σας είναι πολύτιμη!
|