Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

[HOW] Kolejka w C++

pionas88 22 Sty 2009 12:52 10558 14
  • #1 22 Sty 2009 12:52
    pionas88
    Poziom 9  

    Witam!

    Mam pewien problem. Otóż mam taki kod:

    Kod: cpp
    Zaloguj się, aby zobaczyć kod


    Czy może mi ktoś podpowiedzieć gdzie i co przerobić aby stworzyć z tego kolejkę ;), chcę zrobić tzw "kolejkę" czyli usuwanie 1szego elementu i dodawanie i tak w koło macieju ;)

    Dziękuję i pozdrawiam

    0 14
  • #2 22 Sty 2009 20:15
    Dr.Vee
    VIP Zasłużony dla elektroda

    Możesz oprócz wskaźnika na 1 element dodać wskaźnik na ostatni element. Wtedy możesz bez problemu dodawać elementy na koniec i usuwać je z początku.

    Dostaniesz FIFO - o to Ci chodzi?

    Pozdrawiam,
    Dr.Vee

    0
  • #4 22 Sty 2009 21:02
    pionas88
    Poziom 9  

    Dr.Vee napisał:
    Możesz oprócz wskaźnika na 1 element dodać wskaźnik na ostatni element. Wtedy możesz bez problemu dodawać elementy na koniec i usuwać je z początku.

    Dostaniesz FIFO - o to Ci chodzi?

    Pozdrawiam,
    Dr.Vee


    Tak o to mi chodzi :)

    0
  • #5 23 Sty 2009 00:28
    elektryk
    Poziom 42  

    A jaki z tym masz problem? O ile ten program działa dobrze (a na taki wygląda) to właściwie on działa jak FIFO.

    0
  • #6 23 Sty 2009 11:15
    lord_dagoth
    Poziom 25  

    Najłatwiej byłoby Ci przygotować kolejke na wektorze. Podałem linka wyżej do wiki, gdzie masz wszystko jasno opisane, wraz z przykładami.

    0
  • #7 29 Sty 2009 14:07
    pionas88
    Poziom 9  

    elektryk napisał:
    A jaki z tym masz problem? O ile ten program działa dobrze (a na taki wygląda) to właściwie on działa jak FIFO.


    Tak działo on jako FIFO, ale nie wiem jak to przerobić na kolejkę ;)

    lord_dagoth - właśnie to nie może być na wektorach...

    0
  • #8 01 Lut 2009 23:17
    kerad85
    Poziom 11  

    A może to być zrobione w klasie i do tego ta struktura z danymi? Jak tak to mogę Ci przerobisz szybko ten program.

    0
  • #9 01 Lut 2009 23:32
    pionas88
    Poziom 9  

    No może być :) Aby działało jak należy :D
    Ew. ja sobie poprawię bo potrzebuję wskazówek jak to zrobić ;)

    0
  • Pomocny post
    #10 02 Lut 2009 22:46
    kerad85
    Poziom 11  

    Nie wiem czy o to Ci chodziło, ale ten programik robi mniej więcej kolejkę typu FIFO:

    Kod: cpp
    Zaloguj się, aby zobaczyć kod

    0
  • #11 02 Lut 2009 23:27
    pionas88
    Poziom 9  

    O wielkie dzięki... O takie coś mi chodziło :D

    0
  • #12 05 Lut 2009 14:06
    spwmarluk
    Poziom 9  

    kerad85 napisał:

    ...
    Kod: cpp
    Zaloguj się, aby zobaczyć kod

    ...


    Słaby jestem z obiektowego wiec mam pytanie:
    Co właściwie jest usuwane w tym destruktorze?
    Bo mi się wydaje, że elementy kolejki zostaną w pamięci, a jest usuwana pusta struktura temp.
    może jakoś tak?
    Kod: cpp
    Zaloguj się, aby zobaczyć kod

    0
  • #13 05 Lut 2009 15:07
    szelus
    Specjalista - Mikrokontrolery

    spwmarluk napisał:

    Bo mi się wydaje, że elementy kolejki zostaną w pamięci, a jest usuwana pusta struktura temp.
    może jakoś tak?
    Kod: cpp
    Zaloguj się, aby zobaczyć kod

    Zdecydowanie tak.

    0
  • #14 21 Sty 2011 10:56
    axyzzya
    Poziom 11  

    lord_dagoth napisał:
    Najłatwiej byłoby Ci przygotować kolejke na wektorze. Podałem linka wyżej do wiki, gdzie masz wszystko jasno opisane, wraz z przykładami.

    Przepraszam, że odgrzebuję temat sprzed roku ale..
    Robienie kolejki FIFO przy pomocy tego kontenera to nie najlepszy pomysł. Vector to po prostu tablica, przez co nadaje się prędzej na stos, niż na FIFO.
    O ile zdjąć lub wrzucić ostatni element można w O(1) (+ ewentualna realokacja) to zdjęcie pierwszego elementu przy n elementach w kolejce wymaga już O(n) operacji (każdy obiekt w kolejce musimy wówczas przemieścić na miejsce obiektu, który go poprzedzał), przez co złożoność wrzucenia n elementów i wyjęcia ich jest kwadratowa, co zazwyczaj jest nie do przyjęcia Inną opcją byłoby niewyrzucanie z vectora elementów, których już nie ma w kolejce, ale to z kolei wymaga dużej ilości pamięci (i ewentualnie czasu na realokacje). Wydajną i banalnie prostą w użyciu kolejka FIFO z stl'a jest kontener queue, jego implementacja przypomina zapewne program autora tematu.

    0
  • #15 22 Sty 2011 20:34
    Dr.Vee
    VIP Zasłużony dla elektroda

    Wykopaliska. Zamykam.

    0