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

asked 2014-10-08 16:24:33 +0100

Greg

303 ●15 ●18 ●30

updated 2014-10-09 09:46:27 +0100

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ěď...

answered 2014-10-08 16:49:39 +0100

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.

edit flag offensive delete publish 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 ( 2014-10-08 18:43:35 +0100 )edit

Proto je tam isFull, nepocita se se zvysovanim kapacity.

Ashrak ( 2014-10-17 08:50:44 +0100 )edit

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

1 Answer

Comments

Your answer

Question tools

Stats

Related questions