A sor leírása nem primitív lineáris adatszerkezet, amely követi az FIFO sorrendet, amelyben az adatelemeket az egyik végéről (hátulról) helyezik el, és a másik végről törlik (elülső vég). A sor további variációi a kör alakú sor, a kétszeresen befejezett várakozási sor és a prioritási sor.
Összehasonlító táblázat
| Az összehasonlítás alapja | Lineáris sor | Körkörös sor |
|---|---|---|
| Alapvető | Az adatelemeket és utasításokat egymás után egymás után rendezi. | Az adatokat körkörös mintázatba rendezi, ahol az utolsó elem az első elemhez kapcsolódik. |
| A feladat végrehajtásának sorrendje | A feladatokat úgy hajtják végre, hogy azokat korábban elhelyezték (FIFO). | A feladat végrehajtásának sorrendje változhat. |
| Beillesztés és törlés | Az új elemet a hátsó részből kell hozzáadni és elölről eltávolítani. | A beillesztés és törlés bármely pozícióban elvégezhető. |
| Teljesítmény | Nem hatékony | Jobb, mint a lineáris sor. |
A lineáris sor meghatározása
A lineáris sor racionálisan az első a sorrendben. Ez úgynevezett lineáris, mert egyenes vonalhoz hasonlít, ahol az elemek egymás után helyezkednek el. Ez az elemek homogén gyűjteményét tartalmazza, amelyekben az új elemeket az egyik végén hozzáadják, és egy másik végből törlik. A várakozási sor fogalma az a példa, hogy a közönség várakozik a jegyszámlálón kívül, hogy megkapja a színházi jegyet. Ebben a sorban a személy csatlakozik a sor hátsó végéhez, hogy átvegye a jegyet, és a jegyet a sor elején adja ki.
A sorban több művelet is elvégezhető
- Először a várólistát nullára inicializáljuk (azaz üres).
- Határozza meg, hogy a sor üres-e vagy sem.
- Határozza meg, hogy a sor teljes vagy nem.
- Az új elem behelyezése a hátsó részből (Enqueue).
- Az elem törlése az elülső végről (Dequeue).
A sor kétféle módon valósítható meg
- Statikusan (tömbök használata)
- Dinamikusan (mutatók használata)
A lineáris sor korlátozása azt jelenti, hogy olyan forgatókönyvet hoz létre, ahol a sorban sem lehet új elemet hozzáadni, még akkor sem, ha a sor tartalmazza az üres tereket. Ez a fenti helyzet az alábbi ábrán látható. Itt a hátsó az utolsó indexre mutat, míg a dobozok még mindig üresek, új elemet nem lehet hozzáadni.
Körkörös sor meghatározása
A kör alakú sor a lineáris sor egy változata, amely hatékonyan leküzdi a lineáris sor korlátozását. Kör alakú sorban az új elem a sor első pozíciójában kerül hozzáadásra, ha az utolsó elfoglalt és a hely rendelkezésre áll. A lineáris sorban a behelyezés csak a hátsó részből és az elülső végből történő törléssel végezhető el. A sorban lévő sorozatok sorozata után egy teljes sorban egy olyan helyzet alakul ki, amelyben nincs új elem, még akkor sem, ha a rendelkezésre álló hely, mert az alulfolyási feltétel (hátsó = max - 1) továbbra is fennáll.
A kör alakú sor összekapcsolja a két véget egy mutatóval, ahol az első elem az utolsó elem után jön létre. Ezenkívül az első és a hátsó részt is nyomon követi, ha valamilyen extra logikát alkalmaz, hogy nyomon tudja követni a beillesztendő és törölendő elemeket. Ezzel a kör alakú sor nem generálja a túlcsordulás állapotát, amíg a várakozási sor nem teljes.
Néhány feltétel, amelyet a kör alakú sor követ:
- Az elsőnek az első elemre kell mutatnia.
- A sor üres lesz, ha az elülső = hátsó.
- Egy új elem hozzáadásakor a várakozási sor értéke egy értékkel (hátsó = hátsó + 1) növekszik.
- Ha egy elemet törlünk a sorból, az elülső értéket egyenként növekszik (elöl = elöl + 1).
A lineáris sor és a kör alakú sorok közötti különbségek
- A lineáris sor egy rendezett lista, amelyben az adatelemek sorrendben vannak elrendezve. Ezzel ellentétben a kör alakú sor a körkörös módon tárolja az adatokat.
- A lineáris sor a FIFO sorrendet követi a feladat végrehajtásához (az első pozícióban hozzáadott elem törlődik az első pozícióban). Ezzel szemben a kör alakú sorban az elemen végrehajtott műveletek sorrendje változhat.
- Az elemek beillesztése és törlése lineáris sorban van rögzítve, azaz a hátsó részből történő hozzáadás és az elülső vég törlése. Másrészről, a kör alakú sor képes elhelyezni és törölni az elemet bármely pontból, amíg az nincs elfoglalva.
- A lineáris várakozási sor a hulladék helyét pazarolja, míg a kör alakú sor a hely hatékony használatát teszi lehetővé.
A lineáris sor végrehajtása
Az alábbiakban megadott algoritmus egy sorban lévő elemek hozzáadását mutatja be:
A sornak három adatváltozót kell tartalmaznia, beleértve egy tömböt a sor tárolásához, másikat pedig az első és hátsó kezdeti pozíció tárolásához, azaz -1.
beillesztés (elem, sor, n, hátsó) {if (hátsó == n), majd nyomtassa ki a "várakozási sor túlcsordulását"; egyéb {hátsó = hátsó + 1; sor [hátsó] = tétel; }} Az alábbi algoritmus az elemek törlését mutatja egy sorban:
delete_circular (tétel, sor, hátsó, elülső) {if (hátsó == elöl), majd a "várakozási sor alulfolyása" nyomtatása; egyéb {front = front + 1; item = sor [front]; }} A kör alakú sor végrehajtása
Egy algoritmus az elem hozzáadásának értelmezéséhez a kör alakú sorban:
insert_circular (tétel, sor, hátsó, elülső) {hátsó = (hátsó + 1) mod n; ha (elülső == hátsó), majd a "várakozási sor teljes"; other {queue [rear] = tétel; }} Az algoritmus elmagyarázza az elem törlését a kör sorban:
delete_circular (tétel, sor, hátsó, elülső) {if (front == hátsó), majd nyomtatás ("üres sor"); egyéb {front = front + 1; item = sor [front]; }} Következtetés
A lineáris sor bizonyos esetekben nem hatékony, amikor az elemek a behelyezési művelet végrehajtásához szükségesek a üres helyekre való átálláshoz. Ez az oka annak, hogy a tárterületet pazarolja, míg a kör alakú sor megfelelő módon használja a tárolóterületet, mivel az elemeket bármilyen helyzetben adják hozzá, ha üres hely van.
