A veremnek csak egy vége van, amely megnyitja az adatelemek megnyomására és feltöltésére, a másik oldalon a Queue mindkét vége nyitva van az adatelemek enqueuing és dequeuing számára.
A verem és a várakozási sor az adatelemek tárolására használt adatstruktúrák, és valójában valamilyen valós világegyenértéken alapulnak. Például a verem egy CD halmaza, ahová kivehet és CD-t helyezhet a CD-köteg tetején. Hasonlóképpen, a sor a színházi jegyek sora, ahol az első helyen álló személy, vagyis a sor eleje lesz szolgálva, és az új személy érkezik meg a sor hátoldalán (a sor hátsó vége).
Összehasonlító táblázat
| Az összehasonlítás alapja | Kazal | sorban áll |
|---|---|---|
| Működési elv | LIFO (Utoljára először) | FIFO (Először először) |
| Szerkezet | Ugyanaz a vége az elemek beillesztéséhez és törléséhez. | Az egyik végét a behelyezésre használjuk, azaz a hátsó véget és egy másik véget használjuk az elemek törlésére, azaz az elülső végre. |
| Az alkalmazott mutatók száma | Egy | Két (egyszerű soros esetben) |
| A végrehajtott műveletek | Push és Pop | Enqueue és dequeue |
| Üres állapot vizsgálata | Top == -1 | Front == -1 || Front == Hátsó + 1 |
| Teljes állapot vizsgálata | Top == Max - 1 | Hátsó == Max - 1 |
| Változatok | Nincs változata. | Változatokkal rendelkezik, mint például körkörös sor, elsőbbségi sor, kétszeresen befejezett sor. |
| Végrehajtás | egyszerűbb | Összehasonlítóan összetett |
A verem meghatározása
A Stack egy nem primitív lineáris adatszerkezet. Ez egy rendezett lista, ahol az új elem hozzáadásra kerül, és a meglévő elemet csak az egyik végéről törli, amelyet a verem tetejének neveznek (TOS). Mivel az összes törlés és beillesztés egy verembe a verem tetejéről történik, az utolsó hozzáadott elem lesz az első, amelyet eltávolítunk a veremből. Ez az oka annak, hogy a verem az utolsó lista (LIFO) listája.
Ne feledje, hogy a veremben gyakran elérhető elem a legfelső elem, míg az utolsó elérhető elem a verem alján található.
Példa
Néhányan kekszet (vagy Poppint) fogyaszthatnak. Ha feltételezzük, csak a fedél egyik oldala szakadt, és a kekszeket egyenként elveszik. Ez az, amit poppingnek neveznek, és hasonlóan, ha néhány kekszet egy ideig később meg akarunk őrizni, visszahelyezzük őket a csomagba ugyanazon szakadt végen keresztül, amit rámenősnek neveznek.
A sor meghatározása
A sor egy lineáris adatstruktúra, amely a nem primitív típusú kategóriába tartozik. Hasonló típusú elemek gyűjteménye. Az új elemek felvétele az egyik végén a hátsó vég. Hasonlóképpen, a meglévő elemek törlése a másik végén, a Front-end néven történik, és logikailag egy első FIFO (FIFO) típusú lista.
Példa
A mindennapi életünkben sok olyan helyzetben találkozunk, ahol ki kell várnunk a kívánt szolgáltatást. Ez a várakozási sor várakozásnak tekinthető.
Kulcs különbségek a verem és a sor között
- A stack követi a LIFO-mechanizmust, a másik viszont a FIFO-mechanizmust követi az elemek hozzáadásához és eltávolításához.
- Egy veremben ugyanazt a véget használjuk az elemek beillesztéséhez és törléséhez. Éppen ellenkezőleg, két különböző véget használnak a sorban az elemek beillesztéséhez és törléséhez.
- Mivel a Stacknek csak egy nyílt vége van, az az oka, hogy csak egy mutatót használunk a verem tetejére. A várakozási sor azonban két mutatót használ a sor elejére és hátuljára.
- A stack két műveletet ismertet, amelyek a push és pop néven ismertek, míg a Queue-ban úgynevezett enqueue és dequeue.
- A verem végrehajtása könnyebb, míg a sorok végrehajtása trükkös.
- A sorban vannak olyan változatok, mint a kör alakú sor, a prioritási sor, a kétszeresen befejezett sor stb. Ezzel szemben a veremnek nincs változata.
Verem végrehajtása
A verem kétféleképpen alkalmazható:
- A statikus implementáció tömböket használ a verem létrehozásához. A statikus kivitelezés azonban könnyed technika, de nem a létrehozás rugalmas módja, mivel a verem méretének deklarációját a programtervezés során kell elvégezni, azt követően a méret nem változtatható meg. Emellett a statikus implementáció nem túl hatékony a memóriahasználat tekintetében. Mivel egy tömböt (a verem végrehajtásához) a művelet megkezdése előtt (a program tervezési idejében) jelent meg. Most, ha a rendezendő elemek száma kevésbé van a veremben, akkor a statikusan kiosztott memória elvesznek. Másrészről, ha több olyan elem van, amelyet a veremben tárolunk, akkor nem tudjuk megváltoztatni a tömb méretét, hogy növelje kapacitását, így új elemeket tud elhelyezni.
- A dinamikus implementációt összekapcsolt listaképzésnek is nevezik, és mutatókat használ az adatszerkezet veremtípusának megvalósításához.
Sor végrehajtása
A sor kétféleképpen valósítható meg:
- Statikus megvalósítás : Ha egy sorot tömbök segítségével valósítunk meg, akkor a sorban tárolni kívánt elemek pontos számát biztosítani kell, mivel a tömb méretét a tervezési időben vagy a feldolgozás megkezdése előtt kell bejelenteni. Ebben az esetben a tömb eleje a sor elejévé válik, és a sor utolsó helye a sor hátulja. A következő összefüggések a tömbök használatakor a sorban lévő összes elemet megadják:
elöl - hátul + 1
Ha a „hátsó <elülső”, akkor nem lesz elem a sorban, vagy a sor mindig üres lesz. - Dinamikus megvalósítás : Sorok végrehajtása mutatókkal, a fő hátránya az, hogy a csatolt reprezentáció csomópontja több memóriát foglal el, mint egy megfelelő elem a tömb ábrázolásában. Mivel mindegyik csomópontban legalább két mező van az adatmező számára, és más a következő csomópont címének tárolásához, míg a kapcsolt ábrázolásban csak az adatmező van. A kapcsolt ábrázolás előnye nyilvánvalóvá válik, amikor egy elem elhelyezése vagy törlése más elemek közepén van.
Műveletek a Stack-en
Az alapműveletek, amelyek a veremben működtethetők, a következők:
- PUSH : ha egy új elemet hozzáadnak a köteg tetejéhez, akkor PUSH műveletnek nevezik. Egy elem elhelyezése a veremben az elem hozzáadására hívja fel a figyelmet, mivel az új elem a tetejére kerül. Mindegyik nyomási művelet után a felsőt egy-egy növeli. Ha a tömb tele van, és új elem nem adható hozzá, akkor azt STACK-FULL vagy STACK OVERFLOW néven hívják. PUSH OPERATION - funkció C-ben:
Figyelembe véve, hogy a verem bejelentettint stack [5], top = -1;void push(){int item;if (top < 4){printf ("Enter the number") ;scan ("%d", & item) ;top = top + 1;stack [top] = item;}else{printf (" Stack is full");}} - POP : Ha egy elemet törölnek a köteg tetejéről, akkor POP műveletnek nevezik. A verem egyenként csökken, minden pop művelet után. Ha nincs elem a veremen, és a pop megjelenik, akkor ez STACK UNDERFLOW állapotot eredményez, ami azt jelenti, hogy a verem üres. POP OPERATION - funkciók C-ben:
Figyelembe véve, hogy a verem bejelentettint stack [5], top = -1;void pop(){int item;if (top >= 4){item = stack [top];top = top - 1;printf ("Number deleted is = %d", item) ;}else{printf (" Stack is empty");}}
Műveletek egy sorban
A sorban végrehajtandó alapvető műveletek a következők:
- Enqueue : Elem beillesztése egy sorba.Kapcsolási művelet funkció C:
A várólistát mintint queue [5], Front = -1 and rear = -1;void add (){int item;if ( rear < 4){printf ("Enter the number") ;scan ("%d", & item) ;if (front == -1){front =0 ;rear =0 ;}else{rear = rear + 1;}queue [rear] = item ;}else{printf ("Queue is full") ;}} - Dequeue : Elem törlése a sorból.Kapcsolási művelet funkció C:
A várólistát mintint queue [5], Front = -1 and rear = -1;void delete (){int item;if ( front ! = -1){item = queue [ front ] ;if (front == rear){front =-1 ;rear =-1 ;}else{front = front + 1;printf ("Number deleted is = %d", item) ;}}else{printf ("Queue is empty") ;}}
Stack alkalmazások
- Összeállítás a fordítóban.
- Java virtuális gép.
- Visszavonás egy szövegszerkesztőben.
- Vissza a webböngészőben.
- PostScript nyelv a nyomtatókhoz.
- Funkcióhívások végrehajtása egy fordítóban.
Queue alkalmazások
- Adatpufferek
- Aszinkron adatátvitel (IO fájl, csövek, aljzatok).
- Kérések megosztása egy megosztott erőforráson (nyomtató, processzor).
- Forgalmi elemzés.
- Határozza meg a szupermarketben a pénztárak számát.
Következtetés
A stack és a Queue lineáris adatstruktúrák bizonyos módon különböznek egymástól, mint a munkamechanizmus, a szerkezet, a implementáció, a változatok, de mindkettőt a listában lévő elemek tárolására és a listán szereplő műveletek végrehajtására használják, mint például az elemek hozzáadása és törlése. Bár vannak olyan korlátozások az egyszerű sorban, amelyet más típusú sorok felhasználásával nyerünk vissza.
