Processing math: 100%

Implementace fronty pomocí kruhového pole s $O(1)$ vkládáním

asked Oct 8 '14

Greg

303 ●15 ●18 ●30

updated Oct 9 '14

Miro Hrončok

1310 ●17 ●30 ●43 http://hroncok.cz/

Zdravím,

Chludil nás zaúkoloval, ať se doma koukneme, jak se implementuje fronta přes kruhové pole. Říkal myslím, že všechno tam může mít konstantní složitost a na přednáškách to bylo prezentovaný podobně.

image description

Nějak ale nemůžu vymyslet, jak udělat konstantní insert. Přece když mi dojde kapacita a musím nafukovat, je potřeba všechny prvky z jedné strany posunout nakonec/začátek ne? Nebo je tam nějaký trik, jak to obejít?

A nebo se automaticky předpokládá amortizovaná složitost?

Předem díky za odpověď...

add a comment

1 Answer

Sort by » oldest newest most voted

answered Oct 8 '14

MiB
291 ●5 ●8

Řekl bych, že se nepočítá s vyčerpáním kapacity. Někdy můžeš naalokovat celou velikost předem podle maximálního počtu prvků. Jinak je to jako s každým jiným polem – při zvětšení musíš kopírovat, jen v tomto případě kopíruješ dvě části zvlášť. Nicméně pokud zvětšuješ kapacitu po větších přírůstcích (např. 1,5× nebo 2×), můžeš to občasné překopírování zanedbat.

Pokud je maximální počet prvků příliš velký nebo se počet prvků dramaticky liší případ od případu, může být vhodnější implementace spojovým seznamem.

link

Comments

přesně tak, pokud se zařídí aby se kapacita nezmenšovala nebo aby od začátku byla správně velká, tak je i vkládání a zvyšování kapacity amortizovaně konstantní.

Sandokan (Oct 8 '14)

Proto je tam isFull, nepocita se se zvysovanim kapacity.

Ashrak (Oct 17 '14)

add a comment

Question tools

1 follower

Stats

Asked: Oct 8 '14

Seen: 903 times

Last updated: Oct 08 '14

Implementace fronty pomocí kruhového pole s $O(1)$ vkládáním

1 Answer

Comments

Your answer

Question tools

Stats

Related questions

Implementace fronty pomocí kruhového pole s O(1) O(1) vkládáním

1 Answer

Comments

Your answer

Question tools

Stats

Related questions

Implementace fronty pomocí kruhového pole s $O(1)$ vkládáním