Kolejka - implementacja z użyciem tablicy

Jak to zrobić tą implementację z udziałem tablicy do tego :

#include <iostream>
using namespace std;

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

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

     void usun (int elem)
    {
       kolejka[poczatek++];
       if(poczatek==100)
       {
           poczatek=0;
       }
        }
        void rozmiarKolejki()
        {
         if(koniec>=poczatek)
          cout<< koniec - poczatek <<endl;
         else
            cout << 100-(poczatek - koniec) << endl;
        }
        int main ()
        {
            char pol;
            cout<< "wcisnij : d -dodaj , u - usun , r - rozmiar " <<endl;
            cin>>pol;
            while(pol!='q')
            {
                int elem;
                if (pol=='d')
                {

                }
            }

        }
```cpp

https://www.tutorialspoint.com/cplusplus-program-to-implement-queue-using-array

Mam nadzieje ze ACTA 2 mnie za ten link nie dojedzie :(

A jak mam to :

#include <iostream>
using namespace std;

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

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

     void usun (int elem)
    {
       kolejka[poczatek++];
       if(poczatek==100)
       {
           poczatek=0;
       }
        }
        void rozmiarKolejki()
        {
         if(koniec>=poczatek)
          cout<< koniec - poczatek <<endl;
         else
            cout << 100-(poczatek - koniec) << endl;
        }
        int main ()
        {
            char pol;
            cout<< "wcisnij : d -dodaj , u - usun , r - rozmiar " <<endl;
            cin>>pol;
            while(pol!='q')
            {
                int elem;
                if (pol=='d')
                {

                }
            }

        }
```cpp 
to jaki jest najszybszy sposób implementacji ?

To ma byc kolejka FIFO/ LIFO?

https://wandbox.org/permlink/jpoptVZSreXf2yIg

Na szybko:

1. Funkcja usun ma nieuzywany element, czyli usuwanie nie dziala tak jak zostalo zaprojektowane :(
2. W pewny mmomecie dojdziesz do takiego momentu, ze poczatek > koniec - dlatego tablice trzeba przesuwac na przod - tutaj jesli to Twoj poziom to zaincluduj <alhorithm> i uzyj np move_backward :) https://en.cppreference.com/w/cpp/algorithm/move_backward

Z czym wiecej masz problem - postaram sie pomoc

Ma być FIFO
Jaki element w usun jest nieużywany?
Nie wiem jak zrobić tą implementację , mógłbyś wytłumaczyć mi to na tym przykładzie?

Popatrz:

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

W deklaracji masz void usun (int elem) czyli funkcja musi przyjac jakis parametr typu int(tutaj nazwalas go elem) ale potem nigdzie go nie uzywasz.

Zobacz na kod ktory ja Ci pokazalem, widac ze Twoja kolejka dziala do pewnego momentu, dotad az nie usuniesz i 100 elementow i bedziesz chciala dodac kolejny

To co powinnam dać zamiast elem ? początek czy co, żeby to poprawnie działało?

#include <iostream>
using namespace std;

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

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

     void usun()
    {
       kolejka[poczatek++];
       if(poczatek==100)
       {
           poczatek=0;
       }
        }
        void rozmiarKolejki()
        {
         if(koniec>=poczatek)
          cout<< koniec - poczatek <<endl;
         else
            cout << 100-(poczatek - koniec) << endl;
        }
      /*  int main ()
       {
            char pol;
        cout<< "wcisnij : d -dodaj , u - usun , r - rozmiar " <<endl;
         cin>>pol;
        while(pol!='q')
        {
                int elem;
                if (pol=='d')
                {

                }
            }*/
int main () {
   int e;
   cout << "1) Wstaw element do kolejki" << endl;
   cout << "2) Usuń element z kolejki" << endl;
   cout << "3) Wyświetl wszystkie elementy kolejki" << endl;
   cout << "4) Wyjście" << endl;
do {
   cout << "Wprowadź swój wybór:" << endl;
   cin >> e;
switch (e) {
   case 1 : dodaj();
           break;
  case 2 : usun();
           break;
   case 3: rozmiarKolejki();
            break;
    case 4: cout << "Wyjście" << endl;
            break;
 default: cout << "Nieprawidłowy wybór" << endl;
}

} 
while (e!=4);
return 0;
}
```cpp

Mam wrazenie ze nie wiesz jak dziala kolejka.
Przyjmijmy takie cos, dla uproszczenia mamy kolejke ktora pomiesci 5 elementow typu int;
Dodatkowo potrzebujemy zmiennej pomocniczej ktora powie nam ile elementow obecnie znajduje sie w kolejce. nazwijmy ja rozmiar

int kolejka[5];
int rozmiar = 0;

Teraz chcesz kolejke FIFO czyli ona dziala tak:

Jesli kolejka jest pusta to ta tablica wyglada tak: {0, 0, 0, 0, 0}

Jesli dodajesz cos do kolejki ty wykonujesz metode dodaj(XXX), gdzie XXX to jakas liczba bo dodaj przyjmuje element typu int.

dodaj(1);

Teraz kolejka wyglada tak {1, 0, 0, 0, 0}, a zmienna rozmiar powinna wynosic 1.

Teraz dodajmy sobie kilka elementow powiedzmy 4:

dodaj(2);
dodaj(3);
dodaj(4);
dodaj(5);

I nasza kolejka wyglada tak: {1, 2, 3, 4, 5}. A zmienna rozmiar = 5;
Ok i teraz dodajmy kolejny element:

dodaj(6);

I tutaj pojawia sie problem bo chcesz wpisac w adres pamieci poza tablice... - to nalezy obsluzyc.

Nasza funkcja moze wygladac tak:

void dodaj(int elem) 
{
    if (rozmiar >= 5) {
        cout<<"Kolejka jest pelna. Nie mozna dodac kolejnego elementu";
        
        // tutaj wychodzimy aby nie wykonac kolejnych instrukcji
        return; 
    }

    //A tutaj dodajemy element do kolejki i zwiekszamy rozmiar;
    kolejka[rozmiar] = elem;
    rozmiar++;
}

I rozwiazalismy jeden problem.

Teraz zalozmy ze mamy kolejke z 5 elementami: {1, 2, 3, 4, 5}. A zatem zmienna rozmiar = 5;
Jesli chcemy usunac element to powinnismy miec funkcje usun. Z razji, ze funkcja nazywa sie usun, nie zwraca ona nic(void). Zakladamy, ze funkcja usuwa jeden element, czyli nie przyjmuje zadnych parametrow.

Ok jak nasze usuwanie ma wygladac:

usun();

Teraz nasza tablica z kolejka wyglada tak: {2, 3, 4, 5, 0} - moze wygladac inaczej, ale dla uproszczenia przyjmijmy sobie ze wyglada tak..., a rozmiar = 0;
Widzisz co sie stalo Wszystkie elementy poczawszy od drugiego sie przesunely na poczatek i rozmiar sie zmniejszyl. Ty tego nie robisz!

Teraz usunmy kolejny kilka elementow - powiedzmy 4

usun();
usun();
usun();
usun();

Usuwajac wszystkie elementy nasza kolejka wyglada tak: {0, 0, 0, 0, 0}, a rozmiar = 0

I teraz pojawia sie kolejna sytuacja ktorej nie przewidzialas bo co jesli kolejka jest pusta a my chcemy dalej usuwac?

I wiedzac jak dziala kolejka na podstawie zalozen ktore mamy wyzej mozemy zaimplementowac nastepujaca funkcje usuwanie:

void usun()
{
    if (rozmiar < 1) {
        // Nie mamy co usunac wiec nie usuwamy nic...
        return;
    }

    // Tutaj przepisujemy wszystkie wartosci do przodu (nie jest to najwydajniejsze ale latwo Ci bedzie zalapac)...

    //Poczawszy od drugiego elementu(index = 1) wszystkie wartosci wpicujemy w index tablicy o jeden mniejszy :)
    for (int i=1; i<rozmiar; i++) {
        kolejka[i-1] = kolejka[i];
    }
    
    rozmiar--;
}

Dodatkowym waznym elementem kolejki jest funkcja zwroc. Defacto ona dziala tak samo jak usun() tylko zwraca usuniety element. I moze wygladac tak:

int zwroc()
{
    if (rozmiar < 1) {
        // Nie mamy co zwrocic wiec zwracamy null albo wypisujemy jakis komunikat - whatever...
        return NULL;
    }

    // Pobieramy wartosc przed nadpisaniem jej...
    int zwracana_wartosc = kolejka[0];

    for (int i=1; i<rozmiar; i++) {
        kolejka[i-1] = kolejka[i];
    }
    
    rozmiar--;

    return zwracana_wartosc;
}

A tutaj masz przyklad jak to dziala: https://wandbox.org/permlink/Q2lnrTrxEI7qMRx6

Siostra Nency Black to wycwaniona bestyja - nauczona doświadczeniem, że gotowców nie dajemy szuka sobie jakiś w necie, aby z grubsza pasowały do tematu, po czym wkleja nam tutaj niby to jako zrobione przez nią dopytując się o szczegóły w taki mniej więcej sposób. I tak się "dopytuje" aż forumowicze zrobią zadanie za nią. Szczwane :]
To też tłumaczy "dziwne" dopytywania się autorki o szczegóły, jakie powinna sama znać skoro napisała. No to już Bracia wiecie, skąd się to bierze.

A co do Ciebie Nency - do roboty leniwa gangreno, a nie na nas spychasz :P

@Nency Black: Czy coś takiego oczekujesz?

push zwraca true jeśli udało się dodać do kolejki, false w przeciwnym wypadku. pop i pop_Nth zwracają wartość, którą się usunęło z kolejki lub -1 jeśli nie udało się usunąć wartości (albo kolejka już jest pusta, albo próbuje się accessować N-ty index który nie istnieje. Pierwszy element to N = 1, a nie 0). display_queue wyświetla aktualną zawartość kolejki i jej rozmiar. rozmiarKolejki nie robiłem, skoro cur_size jest globalne.

#include <iostream>

#define CAPACITY 3

int pqueue[CAPACITY] = {};
int cur_size = 0;

bool push(int val)
{
    if (cur_size < CAPACITY) {
        pqueue[cur_size++] = val;
        return true;
    }
    return false;
}

int pop()
{
    if (cur_size != 0) {
        int popped_value = pqueue[0];
        for (int i = 0; i < cur_size - 1; i++)
            pqueue[i] = pqueue[i + 1];

        cur_size--;
        return popped_value;
    }
    return -1;
}

int pop_Nth(int N)
{
    if (N <= cur_size && N > 0) {
        int popped_value = pqueue[N-1];

        for (N-- ; N < cur_size - 1; N++)
            pqueue[N] = pqueue[N + 1];

        cur_size--;
        return popped_value;
    }
    return -1;
}

void display_queue()
{
    std::cout << '\n';
    for (int i = 0; i < cur_size; i++)
        std::cout << pqueue[i] << " ";

    std::cout << "\nsize: " << cur_size << "\n";
}

int main()
{
    push(111);
    push(333);
    push(555);
    push(11); // this value wont be added
    display_queue();

    int x = pop();
    std::cout << "popped value: " << x << std::endl;
    display_queue();

    x = pop();
    std::cout << "popped value: " << x << std::endl;
    display_queue();

    x = pop();
    std::cout << "popped value: " << x << std::endl;
    display_queue();

    x = pop();
    std::cout << "popped value: " << x << std::endl;
    display_queue();

    std::cout << "\npop n-th:\n\n";
    push(11);
    push(22);
    push(33);
    push(44); // this value won't be added
    display_queue();

    x = pop_Nth(2);
    std::cout << "popped n-th value: " << x;
    display_queue();

    x = pop_Nth(2);
    std::cout << "popped n-th value: " << x;
    display_queue();

    x = pop_Nth(2);
    std::cout << "popped n-th value: " << x;
    display_queue();
}

W każdym razie lepiej to ustandardyzować i pozbyłbym się tych globalnych containerów.

Żeby uzyskać stałe czasy podstawowych operacji: pop, push, size, isEmpty, lepiej to zaimplenetować z użyciem Linked List.

EDIT: Zaraz, zaraz, można zrobić też tak: https://stackoverflow.com/questions/8722216/implementing-a-simple-queue-using-arrays