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


Obálka Obsah Index Hlavní stránka

změněno 30. července 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.