Stos a kolejka,

MI
  • Rejestracja:około 5 lat
  • Ostatnio:prawie 3 lata
  • Postów:58
0

Witam wszystkich, muszę stworzyć kolejkę, do przechowywania int'ów, i przygotować funkcje:
sprawdzania, czy kolejka jest pusta;
sprawdzania, czy kolejka jest pełna;
dodawania elementu do kolejki;
usuwania elementu z kolejki;
sprawdzania liczby elementów kolejki;
niszczenia kolejki.
O ile się nie mylę kolejka jest bardzo podobna do stosu, mam kod na stos, który ma wszystkie te funkcje (wypisuje wyraz wspak) ale nie do końca wiem jak go przerobić na kolejkę
powinienem w inny sposób dodawać i odejmować, lecz jak ? Oraz w jaki sposób zweryfikować czy ten kod działa? Liczę na jakąś pomoc z Waszej strony

Kopiuj
#include <iostream>
#include <cstring>
using namespace std;

struct kolejka
{
    char T[100];
    int rozmiar;
    char wyraz;
};

bool czyPusta(kolejka K)
{
    if(K.rozmiar == 0)
        return true;
    else
        return false;
}
bool czyPelna(kolejka K)
{
    if(K.rozmiar == 100)
        return true;
    else
        return false;
}

void dodaj(char x, kolejka &K)
{
    if(czyPelna(K) == false)
    {


        K.T[K.rozmiar] = x;
        ++K.rozmiar;
    }
}

char zdejmij(kolejka &K)
{
    if(czyPusta(K) == false)
    {
        --K.rozmiar;
        return K.T[K.rozmiar];
    }
    else
        return '*';
}

int rozmiar(kolejka K)
{
    return K.rozmiar;
}

void zniszcz(kolejka K)
{
    K.rozmiar = 0;
}

int main()
{
    kolejka K;
    K.rozmiar = 0;
    char slowo[100];
    cin >> slowo;
    for(int i = 0; i <strlen(slowo); i++)
    {
        dodaj(slowo[i],K);
    }
    while(czyPusta(K)== false)
    cout << zdejmij(K);

    return 0;
}

SA
  • Rejestracja:ponad 12 lat
  • Ostatnio:około godziny
  • Postów:1436
1

Operacja zdejmij na stosie pobiera ostatni element, w kolejce chcesz, żeby oddawała pierwszy dodany element. Ogólnie to różne struktury danych o różnych zastosowaniach. Możesz zrealizować kolejkę z zadana pojemnością na tablicy operując na wskaźniach na początek i koniec kolejki - jak jeden przesuwasz pobierając element, drugi dodając element.

MI
Czyli bardziej opłaca się pisać kod od nowa, niż edytować ten mój ?
SA
Na początku opłaca się przemyśleć co chcesz zrobić. Jeśli zrozumiesz jak zrobić kolejkę w tablicy to będziesz miał odpowiedz. Na pewno zdejmij wymaga innej implementacji, w strukturze kolejka musisz też trzymać indeks ostatniego pobranego elementu.
MI
Szczerze to nie wiem co chcę zrobić, muszę wykonać takie zadanie: Zaimplementuj strukturę kolejki, służącą do przechowywania liczb typu int, z użyciem tablicy (o co najwyżej 100 elementach). Przygotuj funkcje służące do sprawdzania, czy kolejka jest pusta; sprawdzania, czy kolejka jest pełna; dodawania elementu do kolejki; usuwania elementu z kolejki; sprawdzania liczby elementów kolejki; niszczenia kolejki. W funkcji main() zaprezentuj działanie zaimplementowanych funkcji.
AK
  • Rejestracja:prawie 7 lat
  • Ostatnio:około 2 miesiące
  • Postów:3561
0

Dlaczego to są gołe funkcje, a nie metody w klasie, w której pola by były niepubliczne ?


Bo C to najlepszy język, każdy uczeń ci to powie
MI
W taki sposób zostało to przedstawione przez mojego profesora, dopiero zaczynam z programowaniem i ciężko mi odpowiedzieć na to pytanie
SA
Nie przesadzajmy... Wg mnie to nie pora na technikalia, gdy kolega nie wie jak podejść do samego tematu kolejki.
SA
Brakuje tylko żeby ktoś wyskoczył że w STL jest kolejka i bezsens implementować samemu.
TomaszLiMoon
  • Rejestracja:prawie 10 lat
  • Ostatnio:około 12 godzin
  • Postów:530
0

Jeżeli masz w zadaniu wymóg zastosowania tablicy to użyj bufora cyklicznego.

MI
Będąc na moim poziomie nie bardzo wiem co to bufor cykliczny, nie jestem w tanie edytować tego kodu powyżej ? W celu implementacji kolejki, zamiast stosu
lion137
Bufor cykliczny to nie kolejka, no, nie zwykła kolejka.
kaczus
  • Rejestracja:około 10 lat
  • Ostatnio:3 minuty
  • Lokalizacja:Łódź
  • Postów:1402
0

Są 2 sposoby:
Łatwiejszy i wydajniejszy
Łatwiejszy: dodajesz na końcu tak jak na stosie, więc masz wszystko, sprawdzasz ilość, jak na stosie, więc przepełnienie tez sprawdzasz bez problemu, zdejmujesz - i tu jest brak wydajności, zdejmujesz 1 element i wszystkie dane przesuwasz w dół.

wydajniejszy, zapamiętujesz początkowy element i końcowy. Dodajesz to za ostatnim elementem, zdejmujesz - pierwszy element, ale jednocześnie w każdym wypadku przesuwasz informację który element jest pierwszy, a który ostatni. Jak masz dodać element, a dochodzisz do maksymalnego w tabeli, to zwiększenie powoduje ustawienie się końca na początku tabeli. W sumie trudno to się opisuje, ale programuje niekoniecznie, ale trzeba sobie to wyobrazić - tak jakbyś chodził po okręgu.


Ogólnie na prace domowe mam stawki zaporowe. Czasem coś o programowaniu znajdzie się na mojej stronie
MI
  • Rejestracja:około 5 lat
  • Ostatnio:prawie 3 lata
  • Postów:58
0
Kopiuj
#include <iostream>
#include <cstring>

using namespace std;

struct stos
{
    char T[100];
    int rozmiar;
};

bool czyPusty(stos S)
{
    if(S.rozmiar == 0)
        return true;
    else
        return false;
}

bool czyPelny(stos S)
{
    if(S.rozmiar == 100)
        return true;
    else
        return false;
}

void dodaj(char x, stos &S)
{
    if(czyPelny(S) == false)
    {
        S.T[S.rozmiar] = x;
        S.rozmiar++;
    }
}

char zdejmij(stos &S)
{
    if(czyPusty(S) == false)
    {
        S.rozmiar--;
        return S.T[S.rozmiar];
    }
    else
        return '*';
}

int rozmiar(stos S)
{
    return S.rozmiar;
}

void zniszcz(stos &S)
{
    S.rozmiar = 0;
}

int main()
{
    stos S;
    S.rozmiar = 0;

    char slowo[100];
    cin >> slowo;

    for(int i = 0; i < strlen(slowo); i++)
    {
        dodaj(slowo[i], S);
    }

    while(czyPusty(S) == false)
    {
        cout << zdejmij(S);
    }

    return 0;
}
TomaszLiMoon
  • Rejestracja:prawie 10 lat
  • Ostatnio:około 12 godzin
  • Postów:530
0

Poniżej dodałem implementację generycznej kolejki z wykorzystaniem bufora kołowego będącego kontenerem danych.
Aby nie dawać rozwiązania gotowego na tacy, zrobiłem to w stylu bardziej zaawansowanym. Myślę jednak, że nie będziesz miał większych problemów z przerobieniem kodu na prostszą formę.

Kopiuj
template< typename T , int dim >
class queue
{
    unique_ptr<T[]> element;
    int tail {0};
    int head {0};

public:
    queue(){ element = unique_ptr<T[]>(new T[dim]); }

    bool isEmpty() const { return tail==head; }
    bool isFull() const { return (tail+1)%dim==head; }
    int size() const { return (head<=tail)?(tail-head):dim-(head-tail); }
    bool push( const T& e )
    {
        if( isFull() ) return false;
        element[tail] = e;
        tail = (tail+1)%dim;
        return true;
    }
    optional<T> pop()
    {
        if( isEmpty() ) return nullopt;
        auto ret = head;
        head =(head+1)%dim;
        return element[ret];
    } 
};
edytowany 1x, ostatnio: TomaszLiMoon
lion137
  • Rejestracja:ponad 8 lat
  • Ostatnio:minuta
  • Postów:4944
0

@mikko:
Tutaj:

Zaimplementuj strukturę kolejki, służącą do przechowywania liczb typu int, z użyciem tablicy (o co najwyżej 100 elementach). Przygotuj funkcje służące do sprawdzania, czy kolejka jest pusta; >sprawdzania, czy kolejka jest pełna; dodawania elementu do kolejki; usuwania elementu z kolejki; sprawdzania liczby elementów kolejki; niszczenia kolejki

Napisałeś o kolejce (FIFO)

A to: https://4programmers.net/Forum/C_i_C++/337632-stos_a_kolejka?p=1662689#id1662689 wygląda na stos (LIFO).
Stos czy kolejka?


MI
to jest napisany stos, a ja chcialbym w ten sam sposob napisac kolejke, ale nie do konca wiem jak
MI
  • Rejestracja:około 5 lat
  • Ostatnio:prawie 3 lata
  • Postów:58
0

Czy ktoś wskaże mi błędy oraz co powinienem umieścić w funkcji main ?

Kopiuj
#include <iostream>

using namespace std;

int kolejka[100];
int poczatek=0;
int koniec=0;

bool czyPusta()
{
    if(poczatek == NULL)
        return true;
    else
        return false;
}
bool czyPelna()
{
    if(S.rozmiar == 100)
        return true;
    else
        return false;

}
void dodaj(int elem)
{
    kolejka[++koniec]=elem;
    if(koniec == 100){
        koniec=0;
    }

}
int usun(int elem)
{
    kolejka[poczatek++];
    if(poczatek==100)
    {
        poczatek=0;
    }

}
int rozmiarKolejki()
{
    if(koniec>=poczatek)
        cout << koniec - poczatek << endl;
    else
        cout << 100-(poczatek - koniec) << endl;
}
void zniszcz()
{
        while(czyPusta() == false)
        usun();
}

int main()
{

    return 0;
}
lion137
Robiłeś jakieś testy, co działa, co nie?
MI
  • Rejestracja:około 5 lat
  • Ostatnio:prawie 3 lata
  • Postów:58
0

Coś cały czas mi nie działa ta kolejka, nie widzę żadnego błędu :(

edytowany 1x, ostatnio: mikko
kq
Moderator C/C++
  • Rejestracja:prawie 12 lat
  • Ostatnio:5 dni
  • Lokalizacja:Szczecin
0

A co mówi kompilator? Bo to nie ma prawa się skompilować.


MI
że S jest nie zadeklarowana
kq
Odpowiadaj w odpowiedziach

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.