Linked-Lists vs Stacks vs Queues

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

Για ανανέωση (ή προσθήκη νέου) avatar, πρέπει η μεγαλύτερη διάσταση της εικόνας να είναι 110 pixels.

[Egkelados]

Όντας νέος στον προγραμματισμό μου δημιουργήθηκε η εξής απορία. Για ποιο λόγο να χρησιμοποιούμε stacks και queues όταν έχουμε lists? Μια λίστα η οποία αποτελείται από head, tail και len δεν είναι πολύ πιο ολοκληρωμένη δομή με πολλές περισσότερες δυνατότητες από ότι οι stacks, queues?

Στην περίπτωση της στοίβας χρησιμοποιείς την τεχνική LIFO στην ουρά την FIFO όμως στη λίστα δεν περιορίζεσαι σε κανένα από τα δύο! Μπορείς να προσθέσεις ένα node σε όποιο σημείο της λίστα επιθυμείς μπορείς να το διαγράψεις ανά πάσα στιγμή μπορείς να το βάλεις από την αρχή από το τέλος και γενικά παρατηρώ ότι οι δυνατότητες μιας singly-linked-list είναι πολλές περισσότερες σε σχέση με stack και queue.

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

[Aristos]

Υπάρχει διαφορά ανάμεσα σε μια δομή που χρησιμοποιείς όταν γράφεις κώδικα και σε αυτό που λέμε αφηρημένη δομή δεδομένων. Ανάμεσα δηλαδή στην θεωρητική περιγραφή μιας δομής και στην υλοποίηση της σε κάποια γλώσσα προγραμματτισμού. Αυτό που μάλλον εννοείς είναι πως μια συνδεδεμένη λίστα είναι πολύ πιο γενική δομή απο μία στοίβα ή μια ουρά. Συνεπώς, υλοποιώντας μία συνδεδεμένη λίστα είσαι καλυμένος για όλες τις περιπτώσεις. Αν όμως ο αλγόριθμος σου χρειάζεται στοίβα θα ήταν ασφαλέστερο για σένα να χρησιμοποιήσεις μια άλλη δομή που θα υλοποιεί μόνο τα χαρακτηριστικά της στοίβας για να ξέρεις πχ οτι ένα καινούργιο στοιχείο θα εισάγεται ΜΟΝΟ στην κορυφή. Εσωτερικα αυτή η δομή μπορεί να χρησιμοποιεί τη συνδεδεμένη λίστα, αλλα είναι προτιμώτερο ο κώδικας σου να 'βλέπει' μόνο τις λειτουργίες της στοίβας.
Τέτοιου είδους θέματα συζητώνται πολύ σε ένα μάθημα του 5ου εξαμήνου που λέγεται δομές δεδομένων. Αρκετά καλό μάθημα θα έλεγα. Μπορείς να βρεις αρκετό σχετικό υλικό και εδώ και στο eThmmy καθώς και στο βιβλίο του μαθήματος "Δομές Δεδομένων και Αλγόριθμοι στη Java" του Lafore

[jimPster]

Χωρις να θυμαμαι ακριβως τις υλοποιησεις τους.
Αναλογα με την εφαρμογη σου. Αν χρειαζεται  την queue δεν θα χρησιμοποιησεις linked-list
γτ απλα η queue ειναι πιο γρηγορη και πιανει λιγοτερο χωρο στην μνημη.

Και εστω οτι εχουν και ιδιες ταχυτητες (γτ δεν θυμαμαι) η queue σιγουρα πιανει λιγοτερο χωρο ("bookkeeping") μνημης απο linked list.

Και αντε μπορει τα στοιχεια σου να ειναι στις χιλιαδες (κλαιν οι διαφορες τους ) αν εχεις
εκατομμυρια στοιχεια...

[Egkelados]

Ναι αλλα αυτο δεν μπορω να καταλαβω. Γιατι να χρησιμοποιησω λιστα και ουρα που περιοριζουν τις δυνατοτητες μου? Που χρειαζεται μια τετοια δομη;

[Eragon]

Όταν χρησιμοποιείς μια λίστα δεσμεύεις συγκεκριμένο συνεχόμενο χώρο στη μνήμη. Αυτός ο χώρος σε ορισμένα συστήματα μπορεί να μην είναι εφικτό να δεσμευτεί εφάπαξ. Η στοίβα και η ουρά προσφέρουν δυναμικότητα στη δέσμευση. Κατά τ'άλλα το ότι μια δομή φαίνεται να είναι κατά κάποιο τρόπο υποσύνολο μιας άλλης δεν την καθιστά αυτομάτως και άχρηστη. Για παράδειγμα, στη java μπορείς να πάρεις το πρώτο στοιχείο μιας λίστας με

Code:

if (!myList.isEmpty()) myList.remove(0)

ενώ στην ουρά θα αρκούσε να γράψεις

Code:

myQueue.poll()

Αυτό μπορεί να φαίνεται χαζό ως πλεονέκτημα, αλλά συνεισφέρει σημαντικά στην αναγνωσιμότητα και τη συντήρηση του κώδικα. Είναι σα να λες πωωωωωωω θα πάρω Φερράρι και να την κυκλοφορείς στην Εγνατία   Καλή η Φερράρι, αλλά αν δεν την αξιοποιείς γιατί να την πάρεις?
Δες κι εδώ : http://stackoverflow.com/questions/17436530/when-to-use-queue-over-arraylist

[jimPster]

"
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)

[Egkelados]

Σας ευχαριστώ όλους παιδιά η βοήθεια σας είναι πολύτιμη!