Ez a néhány sor arról fog szólni, hogy miként tudjuk implementálni a verem (stack) adatszerkezetet as3-ban. Azoknak, akik nem tudnák, hogy mi is az a verem leírom néhány sorban, a többiek nyugodtan ugorjanak a következő bekezdéshez. Ez egy LIFO szerkezet (Last-In First-Out), igazából nagyon szemléletes a neve, mert, ha bedobáljuk az elemeket, közülük mindig csak az utolsót láthatjuk, és ahhoz tudunk csak hozzáférni, ha meg akarjuk tudni, mi van alatta ki kell vennünk. A reprezentáció általában aritmetikai (tömbös), de lehet láncolt is. Műveletei: Push – betesz egy elemet a verembe, Pop – kivesz egy elemet, Top – megmondja mi a legfelső elem, IsEmpty – megadja, hogy üres-e a vermünk. Az ok, amiért ezt az adatszerkezetet választottam azaz, hogy elég egyszerű, de mégis szemléletes, ill. rengeteg gyakorlati alkalmazása van (végrehajtási verem, fordítóprogramok szintaktikai helyességellenőrzése, és még sorolhatnám). A kis fejtágítás után kezdjünk is bele a megvalósításba.
Reprezentáció terén nincs sok választásunk, pointerek híján láncolt szerkezetet nem tudunk megvalósítani, meg különben is ki akarna vermet láncolva ábrázolni?! Megjegyzem, lehetne pointerek nélkül is láncolni (statikus láncolás), de erre itt semmi szükségünk. Nézzük milyen változókra lesz szükségünk: kell egy tömb, kell egy változó, amiben a verem legfölső elemének az indexét tároljuk, ill. a példa kedvéért egy max, amivel megmondjuk, hogy maximum hány elemű lehet a tömbünk.
private var stackarray:Array=new Array; private var stacktop:int; private var stackmax:int;
A csomagokat az előző postban elég jól kiveséztük szóval azt most átugranám. Viszont, amire kitérnék azok a private adattagok. Megint visszautalnék az előző írásomra. Ott ugye a Button osztály 2 adattagját internálnak választottam, mert jól szemléltette az elérhetőségi szabályokat. De valójában, az hogy egy változót osztályon kívülről változtatgatunk az eléggé távol áll az objektumorientált felfogástól. Persze van 1-2 kivétel, mint például a c++ friend függvényei, itt a hatékonyság érdekében hozzuk ezt az áldozatot. Viszont a vermünknél semmi szükségünk arra, hogy bárki más szórakozzon a változóinkkal.
Programunk konstruktora rendkívül egyszerű:
public function Stack(max:int):void {
stacktop=0;
stackmax=max;
}
Inicializálja a stacktop privát változónkat 0-val, ill. az egyetlen függvényparaméterét értékül adja a stackmax-nak.
Most vegyük sorra a műveleteket. Itt fontos megjegyeznem, hogy mindegyik függvényünk publikus lesz, hiszen ezeket mind szeretnénk használni a főprogramunkban.
Push:
public function Push(element:int):void {
if (stacktop<stackmax) {
stacktop++;
stackarray[stacktop]=element;
} else {
trace("Stack is full");
}
}
A Push egyetlen paramétert vár, azt amit bele szeretnénk dobni a vermünkbe. A feltétel vizsgálattal megnézzük, hogy tömbünk elérte-e már képzeletbeli határát. Itt érdemes azt megjegyezni, hogy egy tömb soha nem tud betelni csakis a memória szabhat neki határt. Kezdetben lefoglalódik neki egy adott méretű tárhely, ha ez betelik, akkor foglal egy 2* akkorát stb. Ez a valóságban elég hatékony, hiszem nem kerül sor sok duplázásra, hiszen, mint tudjuk az exponenciális függvény nagyon gyorsan nő. Abban az esetben, ha a feltétel nem teljesül egy egyszerű kiíratást csinálunk.
Pop:
public function Pop() {
if (stacktop>0) {
stacktop--;
return stackarray[stacktop+1];
} else {
trace("Stack is empty");
}
}
Itt is figyelnünk kell, hogy nehogy üres veremből adjuk vissza elemet. Ha belép az if-be akkor csak csökkentjük a veremtetőt egyel és visszaadjuk a legfelső elemet. A return utasítás hatására a függvényünk kilép és visszatér a hívás helyére egy értékkel, adott esetben egy tömbelemmel, ami integer. Fontos, hogy a return előtt kell csökkentenem a stacktop változómat, mert után ez már nem lehetséges, és ennek folyományaként stacktop+1-gyel kell visszatérnünk. És természetesen itt is kiírunk egy kis üzenetet, ha valami nem stimmel.
Top:
public function Top() {
if (stacktop>=0) {
return stackarray[stacktop];
} else {
trace("Stack is empty");
}
}
A Top kódja nagyon hasonló a Pop függvényhez, nem is szeretném túlmagyarázni, mindössze annyira kell figyelnünk, hogy csak visszaadjuk az elemet és ne kivegyük azt (stacktop értéke nem változik).
IsEmpty:
public function IsEmpty() {
return stacktop<1;
}
Ez a legegyszerűbb műveletünk, hiszen csak egy logikai értékkel térünk vissza.
Végül a teljes kód egyben:
package hu.actionscript.stack{
public class Stack {
private var stackarray:Array=new Array ;
private var stacktop:int;
private var stackmax:int;
public function Stack(max:int):void {
stacktop=0;
stackmax=max;
}
public function Push(element:int):void {
if (stacktop<stackmax) {
stacktop++;
stackarray[stacktop]=element;
} else {
trace("Stack is full");
}
}
public function Pop() {
if (stacktop>0) {
stacktop--;
return stackarray[stacktop+1];
} else {
trace("Stack is empty");
}
}
public function Top() {
if (stacktop>=0) {
return stackarray[stacktop];
} else {
trace("Stack is empty");
}
}
public function IsEmpty() {
return stacktop<1;
}
}
}
Ha ezzel megvagyunk, akkor már csak tesztelnünk kell. Hozzunk létre egy új .fla-t és a legelső framere írjuk be ezt a pár sort:
import hu.actionscript.stack.*;
var verem:Stack=new Stack(10);
for (var i:int=0; i<5; i++) {
verem.Push(i);
}
trace("A legfelső elem a(z): ", verem.Top(),"\n");
while (!verem.IsEmpty()) {
trace(verem.Pop());
}
Semmi érdekes nem történik, igazából csak leteszteljük az osztályt. Legelsőnek importáljuk, majd példányosítunk. Ezek után feltöltjük 0..4-ig a vermünket (vigyázzunk, maximum 10 elem fér el a mostani adatszerkezetünkben, ha többre van szükségünk nagyobb értékkel kell deklarálnunk). A Top művelettel lekérjük a legfelső elemet, majd kiürítjük a vermet. Ha mindet jól csináltunk ebből: 0,1,2,3,4 ezt kell kapnunk: 4,3,2,1,0.
A verem kimenete
Lenne még mit csinosítani ezen a megoldáson, mert nincs pl. rendes hibakezelésünk, de ezt majd egy másik postban orvosoljuk. Most hogy megírtuk az osztályunkat, elmondhatom, hogy nem igen fogjuk használni élesben, mert az actionscript 3-ban vannak erre a célra definiált függvények (pop, push, concat, shift, stb.), de mindenkép hasznos hogy látjuk hogyan is kell egy ilyet megvalósítani. Ez olyasmi, mint amikor megírjuk c++-ban a saját listánkat, de soha nem fogjuk használni, mert az STL által kínált megoldás sokkal hatékonyabb és kényelmesebb, mindazonáltal gyakorlásnak nagyon jó, és ad egy szemléletet.
