Tartalom

• Összehasonlító táblázat
• A stack meghatározása
• Példa
• A sor meghatározása
• Példa
• Verem megvalósítása
• Várakozási sor végrehajtása
• Műveletek a veremben
• Műveletek egy sorban
• A verem alkalmazásai
• Queue alkalmazások
• Következtetés

A Stack és a Queue egyaránt nem primitív adatszerkezetek. A verem és a sorok közötti fő különbségek az, hogy a stack LIFO (utoljára az elsőben) módszert használ az adatelemek eléréséhez és hozzáadásához, míg a Queue a FIFO (első az elsőben ki) módszert használja az adatelemek eléréséhez és hozzáadásához.

A veremnek csak az egyik vége van nyitva az adatelemek tolásához és elbuktatásához, a sornak pedig mindkét vége nyitva van az adatelemek elvarázsolására és eltávolítására.

A verem és a sor az adatelemek tárolására használt adatszerkezetek, és valójában valamilyen valós egyenértékre épülnek. Például a verem egy CD-verem, amelyből ki lehet venni és CD-lemezbe helyezheti a CD-verem tetején keresztül. Hasonlóképpen, a sor a színházi jegyek sora, ahol az első helyen, azaz a sor elején álló személyt kiszolgálják először, és az érkező új személy megjelenik a sor hátuljában (a sor hátsó vége).

1. Összehasonlító táblázat
2. Meghatározás
3. Főbb különbségek
4. Végrehajtás
5. Tevékenységek
6. Alkalmazások
7. Következtetés

Összehasonlító táblázat

Az összehasonlítás alapja	Kazal	sorban áll
Működési elv	LIFO (utoljára az elsőben)	FIFO (első az elsőben)
Szerkezet	Ugyanezt a végét használják az elemek beszúrására és törlésére.	Az egyik végét beillesztésre használják, azaz a hátsó végét, a másik végét az elemek törlésére, azaz az első végét használják.
A használt mutatók száma	Egy	Kettő (egyszerű sor esetén)
Végzett műveletek	Push and Pop	Enqueque and dequeue
Üres állapot vizsgálata	Felső == -1	Elöl == -1 || Elöl == Hátsó + 1
Teljes állapot vizsgálata	Felső == legfeljebb 1	Hátsó == Max - 1
Változatok	Nincs változata.	Változatai vannak, például körkörös sor, prioritási sor, kétszer véget érő sor.
Végrehajtás	egyszerűbb	Viszonylag bonyolult

A stack meghatározása

A Stack nem primitív lineáris adatstruktúra. Rendezett lista, ahol hozzáadódik az új elem, és a meglévő elemet csak az egyik végéből törlik, amelyet verem tetejének (TOS) hívnak. Mivel az összes törlés és beillesztés a verembe a verem tetejéről történik, az utoljára hozzáadott elem lesz az első, amelyet eltávolítanak a veremből. Ez az oka annak, hogy a stackot „Last-in-first-out” (LIFO) típusú listának nevezzük.

Vegye figyelembe, hogy a veremben gyakran hozzáférhető elem a legfelső elem, míg az utolsó elérhető elem a verem alján található.

Példa

Néhányan enni keksz (vagy poppins) lehet. Ha feltételezi, a fedél csak az egyik oldala szakad el, és a kekszek egyenként kerülnek ki. Ezt nevezik poppingnak, és hasonlóképpen, ha később el akarja tartani néhány kekszet, akkor ugyanazon szakadt végén keresztül visszaszorítja őket a csomagolásba.

A sor meghatározása

A sor egy lineáris adatszerkezet a nem primitív típusú kategóriába tartozik. Hasonló típusú elemek gyűjteménye. Az új elemek hozzáadása az egyik végén, úgynevezett hátsó oldalon történik. Hasonlóképpen, a meglévő elemek törlésére a front-end nevű másik végről kerül sor, és logikusan ez az első az elsőben (FIFO) típusú lista.

Példa

Napi életünkben számos olyan helyzettel találkozunk, amikor ki kell várnunk a kívánt szolgáltatást, ott be kell lépnünk a várakozási sorba a sorunkra, hogy kiszolgálást kapjunk. Ez a várakozási sor sor lehet.

1. A Stack követi a LIFO mechanizmust, a Queue pedig a FIFO mechanizmust követi az elemek hozzáadásához és eltávolításához.
2. Egy halomban ugyanazt a végét használják az elemek beszúrására és törlésére. Éppen ellenkezőleg, a sorban két különböző vég van felhasználva az elemek beillesztésére és törlésére.
3. Mivel a veremnek csak egy nyitott vége van, ez az oka annak, hogy csak egy mutatót használjunk a verem tetejére való hivatkozáshoz. De a sor két mutatót használ a sor elülső és hátsó részének hivatkozására.
4. A Stack két, push és pop néven ismert műveletet hajt végre, míg a várólistában az enqueque and dequeue néven ismert.
5. A köteg végrehajtása könnyebb, míg a sorok végrehajtása bonyolult.
6. A sornak vannak variációi, például körkörös sor, prioritási sor, kétszer véget érő sor stb. Ezzel szemben a stack-nek nincs változata.

Verem megvalósítása

A verem kétféle módon alkalmazható:

1. Statikus megvalósítás tömbök segítségével verem létrehozásához. A statikus megvalósítás ugyan erőfeszítés nélküli technika, de nem rugalmas létrehozási módszer, mivel a verem méretének deklarálását a program megtervezésekor kell elvégezni, miután a méret nem változtatható. Ezenkívül a statikus megvalósítás nem túl hatékony a memóriahasználat szempontjából. Mivel a tömböt (a verem megvalósításához) a művelet megkezdése előtt deklarálják (a program tervezési idején). Most, ha a verembe nagyon kevesebb elem válik sorba, akkor a statikusan kiosztott memória pazarolásra kerül. Másrészt, ha több elemet kell tárolni a veremben, akkor nem tudjuk megváltoztatni a tömb méretét kapacitásának növelése érdekében, hogy új elemek elférjenek.
2. Dinamikus megvalósítás az összekapcsolt lista reprezentációjának is nevezik, és mutatókat használ a verem típusú adatszerkezet megvalósításához.

Várakozási sor végrehajtása

A várólistát kétféle módon lehet megvalósítani:

1. Statikus megvalósítás: Ha egy sort tömbökkel valósítanak meg, akkor a sorban tárolni kívánt elemek pontos számát előbb biztosítani kell, mert a tömb méretét a tervezéskor vagy a feldolgozás megkezdése előtt be kell jelenteni. Ebben az esetben a tömb eleje a sor elejévé válik, és a tömb utolsó helye a sor hátsó részeként fog működni. A következő kapcsolat biztosítja, hogy a teljes elemek léteznek a sorban, ha tömbökkel valósítják meg:
   elöl - hátul + 1
   Ha „hátsó <elülső”, akkor a sorban nincs elem, vagy a sor mindig üres.
2. Dinamikus megvalósítás: Várakozási sorok végrehajtása mutatók segítségével, a fő hátrány az, hogy egy összekapcsolt ábrázolásban lévő csomópontok több memóriahelyet fogyasztanak, mint a tömb ábrázolásának megfelelő elemei. Mivel minden csomópontban legalább két mező van az egyikben az adatmezőhöz, a másik pedig a következő csomópont címének tárolására, míg a kapcsolt ábrázolásban csak az adatmező található. A kapcsolt ábrázolás használatának érdeme nyilvánvalóvá válik, amikor egy elem beillesztésére vagy törlésére van szükség más elemek csoportjának közepén.

Műveletek a veremben

A veremben működtethető alapműveletek a következők:

1. NYOM: új elem hozzáadásakor a verem tetejére PUSH műveletnek nevezzük. Egy elemnek a verembe történő benyomása az elem hozzáadását vonja maga után, mivel az új elem tetején lesz. Minden egyes lenyomás után a tetejét eggyel megnövelik. Ha a tömb megtelt, és nem lehet új elemet hozzáadni, akkor ezt STACK-FULL feltételnek vagy STACK OVERFLOW-nak nevezzük. NYOMÁS MŰKÖDÉS - funkció C-ben:
   A stack figyelembe vételével
   int stack, top = -1;
érvénytelen nyomás ()
{
int elem;
if (felső <4)
{
f ("Írja be a számot");
pásztázás ("% d", & elem);
top = top + 1;
stack = elem;
}
más
{
f ("A stack megtelt");
}
}
2. POP: Ha egy elemet törölnek a verem tetejéről, akkor POP műveletnek nevezik. A köteg minden pop-művelet után egy-egyre csökken. Ha nincs elemet a veremben, és a pop végrehajtódik, akkor ez STACK UNDERFLOW állapotot eredményez, ami azt jelenti, hogy a verem üres. POP MŰKÖDÉS - funkciók C-ben:
   A stack figyelembe vételével
   int stack, top = -1;
érvénytelen pop ()
{
int elem;
if (felül> = 4)
{
tétel = halom;
top = top - 1;
f ("Törölt szám =% d", tétel);
}
más
{
f ("A köteg üres");
}
}

Műveletek egy sorban

A sorban végrehajtható alapműveletek a következők:

1. Enqueue: Egy elem beszúrása a sorba. A működési funkció végrehajtása a C-ben:
   A várólistát:
   int sorban, elöl = -1 és hátul = -1;
void add ()
{
int elem;
if (hátsó <4)
{
f ("Írja be a számot");
pásztázás ("% d", & elem);
if (elöl == -1)
{
elöl = 0;
hátsó = 0;
}
más
{
hátsó = hátsó + 1;
}
sor = tétel;
}
más
{
f ("A sor megtelt");
}
}

2. Dequeue: Egy elem törlése a sorból. A C funkció működési funkciójának végrehajtása:
   A várólistát:
   int sorban, elöl = -1 és hátul = -1;
érvénytelen törlés ()
{
int elem;
if (elöl! = -1)
{
tétel = sor;
if (elöl == hátul)
{
elöl = -1;
hátsó = -1;
}
más
{
elöl = elöl + 1;
f ("Törölt szám =% d", tétel);
}
}
más
{
f ("üres a sor");
}
}

A verem alkalmazásai

• Elemzés egy fordítóban.
• Java virtuális gép.
• Visszavonás egy szövegszerkesztőben.
• Vissza gomb egy webböngészőben.
• PostScript nyelv az ers számára.
• Funkcióhívások végrehajtása fordítóban.

Queue alkalmazások

• Adatpufferek
• Aszinkron adatátvitel (fájl IO, csövek, aljzatok).
• A kérelmek megosztása megosztott erőforráson (er, processzor).
• Forgalom elemzése.
• Határozza meg a szupermarketben lévő pénztárosok számát.

Következtetés

A Stack és a Queue lineáris adatstruktúrák bizonyos szempontból különböznek, például a működési mechanizmus, a szerkezet, a megvalósítás, a variánsok, de mindkettőt használják a listában szereplő elemek tárolására és a listán szereplő műveletek végrehajtására, például az elemek hozzáadására és törlésére. Annak ellenére, hogy vannak korlátozások az egyszerű sorra, amelyet más típusú sor használatával lehet visszanyerni.