Technika: Reprezentace zásobniku, fronty a bifronty

TECHNIKA: REPREZENTACE ZÁSOBNÍKU, FRONTY A BIFRONTY

Lineární seznam je množina N>=0 prvků A.1,A.2,...,A.N. Lineární seznamy, u kterých se operace vložení a odebrání aplikují pouze na první nebo poslední prvky, jsou:

Zásobník
- operace vložení i odebrání se provádí pouze na jednom konci lineárního seznamu.

Fronta
- operace vložení se provádí na jednom konci, operace odebrání na druhém konci lineárního seznamu.

Bifronta
- "fronta se dvěma konci" je lineární seznam, u kterého se operace vložení i odebrání provádí na obou koncích.

EXTERNÍ DATOVÁ FRONTA
Následující velmi jednoduché podprogramy nám umožňují reprezentovat základní typy lineárních seznamů:

Zásobník
pomocí INSERT_ON_RIGHT a DELETE_FROM RIGHT

Frontu
pomocí INSERT_ON_LEFT a DELETE_FROM_RIGHT

Bifrontu s omezeným výstupem
pomocí INSERT_ON_RIGHT, INSERT_ON_LEFT,
DELETE_FROM_RIGHT

INITIALIZE: do while \EMPTY(); pull; end; return

INSERT_ON_RIGHT: push ARG(1); return

INSERT_ON_LEFT: queue ARG(1); return

DELETE_FROM_RIGHT:
if EMPTY()
  then do
    call UNDERFLOW
    return ""
  end
  else do
    pull X
    return X
  end

EMPTY: return QUEUED() = 0

UNDERFLOW: return

POLE
Nejjednodušší a nejpřirozenější způsob reprezentace zásobníku v paměti počítače využívá pole.

Zásobník
můžeme snadno reprezentovat pomocí podprogramů INSERT_ON_RIGHT a DELETE_FROM_RIGHT.

INITIALIZE: procedure expose R
R = 0; return

INSERT_ON_RIGHT: procedure expose A. R
R = R + 1; A.R = ARG(1)
return

DELETE_FROM_RIGHT: procedure expose A. R
if EMPTY()
  then do
    call UNDERFLOW
    return ""
  end
  else do
    S = R; R = R - 1
    return A.S
  end

EMPTY: procedure expose R; return R = 0

UNDERFLOW: return

ŘETĚZEC
Jsou-li prvky seznamu slova, můžeme k reprezentaci lineárního seznamu využít řetězec slov. Jednotlivé struktury pak lze reprezentovat jednoduše takto:

Zásobník
pomocí INSERT_ON_LEFT a DELETE_FROM_LEFT

Frontu
pomocí INSERT_ON_RIGHT a DELETE_FROM_LEFT

Bifrontu s omezeným výstupem
pomocí INSERT_ON_RIGHT, INSERT_ON_LEFT,
DELETE_FROM_LEFT

INITIALIZE: procedure expose A
A = ""; return

INSERT_ON_RIGHT: procedure expose A
A = A ARG(1); return

INSERT_ON_LEFT: procedure expose A
A = ARG(1) A; return

DELETE_FROM_LEFT: procedure expose A
if EMPTY()
  then do
    call UNDERFLOW
    return ""
  end
  else do
    parse var A X A
    return X
  end

EMPTY: procedure expose A
return A = ""

UNDERFLOW: return ""

POROVNÁNÍ
Časovou složitost různých reprezentací zásobníku jsem porovnal pomocí následující programu. Zaznamenal jsem dobu běhu při práci s prvky seznamu o délce K, kde K byl nejprve jen jeden znak a potom deset tisíc znaků.

Seed = RANDOM(,,481989); K = 10000
String = COPIES("*", K)
call TIME "R"
call INITIALIZE
do 1000000
  Rnd = RANDOM(1)
  if Rnd = 0 then call INSERT_ON_LEFT String
             else X = DELETE_FROM_LEFT()
end
say TIME("R") seconds
exit
...

Výsledek

Časová složitost v sekundách
Reprezentace K = 1 K = 10000

Ext. datová fronta 37.96 464.78

Pole 67.39 241.51

Řetězec 59.32 ?^*)

^*) Násilně jsem výpočet ukončil po 3600 sekundách.

SOUVISLOSTI

Topologické třídění - užití více reprezentací fronty v jediném programu.
QUICKSORT a Eliminace rekurze - užití zásobníku.

Literatura
Knuth D. E., Fundamental Algorithms, vol. 1 of The Art of Computer Programming
- 2nd ed. Addison-Wesley, 1973