Mam za zadanie zaimplementować kolejkę dwustronną w tablicy, ale tak żeby czas zamortyzowany wstawiania i usuwania elementów ( zarówno z początku jak i końca ) był stały.
Czy ma ktoś jakieś pomysły, zadania może być nawet w pseudokodzie czy c++, chodzi mi o ogólną ideę tego zadania.
[Algorytmy] Kolejka dwustronna w tablicy
- elbargetni
- Użytkownik
- Posty: 189
- Rejestracja: 22 wrz 2013, o 11:25
- Płeć: Mężczyzna
- Lokalizacja: PL
- Podziękował: 1 raz
- Pomógł: 1 raz
[Algorytmy] Kolejka dwustronna w tablicy
Ostatnio zmieniony 28 gru 2014, o 13:56 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 1588
- Rejestracja: 16 maja 2013, o 17:56
- Płeć: Mężczyzna
- Lokalizacja: Trójmiasto
- Podziękował: 11 razy
- Pomógł: 245 razy
[Algorytmy] Kolejka dwustronna w tablicy
tworzysz tablicę, może być stałej wielkości np. 1000
zakładasz dwie zmienne int - head i tail i ustawiasz je tak, że:
n = 1000 - rozmiar tablicy
head = 0
tail = 1
teraz dostawienie na koniec kolejki robisz jako wpisanie na tab[tail] i tail++ mod n
zabranie z końca odwrotnie, cofasz tail na poprzednią pozycję w mod n i sczytujesz
operacje na początku analogicznie, wstawienie wstawiasz do tab[head] i cofasz head w mod n, zabranie zwiększasz head i odczyt
musisz tylko pilnować tego, że jeśli tail jest o 1 mniejszy od head to kolejka jest pełna
w ten sposób implementuje się kolejkę cykliczną, nie trzeba dzięki temu przesuwać elementów po operacjach
no i czas jest stały
zakładasz dwie zmienne int - head i tail i ustawiasz je tak, że:
n = 1000 - rozmiar tablicy
head = 0
tail = 1
teraz dostawienie na koniec kolejki robisz jako wpisanie na tab[tail] i tail++ mod n
zabranie z końca odwrotnie, cofasz tail na poprzednią pozycję w mod n i sczytujesz
operacje na początku analogicznie, wstawienie wstawiasz do tab[head] i cofasz head w mod n, zabranie zwiększasz head i odczyt
musisz tylko pilnować tego, że jeśli tail jest o 1 mniejszy od head to kolejka jest pełna
w ten sposób implementuje się kolejkę cykliczną, nie trzeba dzięki temu przesuwać elementów po operacjach
no i czas jest stały
- elbargetni
- Użytkownik
- Posty: 189
- Rejestracja: 22 wrz 2013, o 11:25
- Płeć: Mężczyzna
- Lokalizacja: PL
- Podziękował: 1 raz
- Pomógł: 1 raz