A számítástechnikában a sor olyan lineáris adatstruktúra, amelyben a komponensek az egyik végébe kerülnek, a másik végéről pedig eltávolítják a „first-in, first-out” (FIFO) elv szerint. Ez az adatstruktúra használható műveleti sorrend vezérlésére vagy adatok tárolására. A C egy számítógépes nyelv, amely tömbök vagy linkelt listák formájában van beépítve várólista.

Jellemzők:

• A várólista egyfajta lineáris adatstruktúra, amely egy tömbből vagy egy linkelt listából hozható létre.
• Az elemek a sor hátuljára helyeződnek át, míg elölről eltávolítják őket.
• Az enqueue (egy elem hozzáadása a hátuljához) és a dequeue (egy elem eltávolítása elölről) két sorművelet.
• Amikor gyakran adunk hozzá és távolítanak el elemeket, egy sor körkörös várólistaként hozható létre a memóriapazarlás elkerülése érdekében.

A tömb használata:

Ha C-ben szeretne várólista tömböt használni, először határozza meg a sor maximális méretét, és deklaráljon egy ekkora tömböt. Az elülső és a hátsó egész szám 1-re lett állítva. Az elülső változó a sor elülső elemét, a hátsó változó pedig a hátsó elemet jelöli.

Mielőtt az új elemet a sor végső helyére tolnánk, meg kell növelnünk a hátsó változót 1-gyel. A sor most megtelt, és nem lehet további elemeket hozzáadni, amikor a hátsó pozíció eléri a sor maximális kapacitását. Hozzáadunk egy elemet a sor elejéhez, és csak eggyel növeljük a front változót, hogy eltávolítsunk egy elemet a sorból. Ha az első és a hátsó pozíció megegyezik, és nem lehet több komponenst törölni, akkor azt mondhatjuk, hogy a sor üres.

Az alábbiakban egy olyan C nyelven írt várólista látható, amely tömböt használ:

C programozási nyelv:

Edith mack hirsch

 #define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } 

A kód kimenete a következő lesz:

Kimenet:

 10 20 30 Queue is empty-1 

Magyarázat:

1. Először három elemet 10, 20 és 30 sorba helyezünk a sorba.
2. Ezután sorba állítjuk és kinyomtatjuk a sor elülső elemét, ami 10.
3. Ezután sorba állítjuk és újra kinyomtatjuk a sor elülső elemét, ami 20.
4. Ezután sorba állítjuk, és újra kinyomtatjuk a sor elülső elemét, ami 30.
5. Végül egy üres sorból állítunk elő egy sort, amely a „Várólista üres” szöveget írja ki, és -1-et ad vissza.

Hivatkozási lista használata:

A C programozási nyelvben egy sor létrehozásának másik alternatív módja a linkelt lista használata. A várólista minden csomópontját ezzel a módszerrel fejezi ki egy csomópont, amely tartalmazza az elem értékét és egy mutatót a sor következő csomópontjára. A sor első és utolsó csomópontjának nyomon követése érdekében elülső és hátsó mutatókat használnak.

Létrehozunk egy új csomópontot az elem értékével, és a következő mutatóját NULL-ra állítjuk, hogy egy elemet adjunk a sorhoz. Az új csomóponthoz beállítjuk az elülső és a hátsó mutatót, ha a sor üres. Ha nem, frissítjük a hátsó mutatót, és beállítjuk a régi hátsó csomópont következő mutatóját, hogy az új csomópontra mutasson.

Csomópont törlésekor a sorból először az előző csomópont törlődik, majd az elülső mutató frissül a sor következő csomópontjára, végül felszabadul a memória, amelyet az eltávolított csomópont foglalt. Ha az elülső mutató NULL az eltávolítás után, akkor a sor üres.

Íme egy példa a C nyelvben megvalósított várólistákra egy linkelt lista használatával:

c logikai érték

C programozási nyelv:

 #include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } 

A kód kimenete a következő lesz:

Kimenet:

 10 20 30 Queue is empty-1 

Magyarázat:

1. Először három elemet 10, 20 és 30 sorba helyezünk a sorba.
2. Ezután sorba állítjuk és kinyomtatjuk a sor elülső elemét, ami 10.
3. Ezután sorba állítjuk és újra kinyomtatjuk a sor elülső elemét, ami 20.
4. Ezután sorba állítjuk, és újra kinyomtatjuk a sor elülső elemét, ami 30.
5. Végül az üres sorból próbálunk kilépni a sorból, amely kiírja a 'Várólista üres' üzenetet, és -1-et ad vissza.

Előnyök:

• A várólisták különösen hasznosak olyan algoritmusok megvalósításához, amelyeknél az elemeket pontos sorrendben kell feldolgozni, mint például a szélességi keresés és a feladatütemezés.
• Mivel a sorműveletek O(1) idejű összetettséggel rendelkeznek, még hatalmas sorokon is gyorsan végrehajthatók.
• A sorok különösen rugalmasak, mivel egyszerűen megvalósíthatók egy tömb vagy egy linkelt lista segítségével.

Hátrányok:

• A várólista, a veremtől eltérően, nem hozható létre egyetlen mutatóval, így a sormegvalósítás kissé jobban érintett.
• Ha a várólista tömbként van felépítve, akkor hamarosan megtelik, ha túl sok elemet ad hozzá, ami teljesítménybeli problémákhoz vagy esetleg összeomláshoz vezethet.
• Ha egy csatolt listát használ a sor megvalósításához, az egyes csomópontok memória többletterhelése jelentős lehet, különösen kis elemek esetén.

Következtetés:

A sorokat használó alkalmazások, amelyek egy kulcsfontosságú adatstruktúra, magukban foglalják az operációs rendszereket, a hálózatokat és a játékokat, hogy csak néhányat említsünk. Ideálisak olyan algoritmusokhoz, amelyeknek meghatározott sorrendben kell kezelniük az elemeket, mivel egyszerűen létrehozhatók tömb vagy linkelt lista használatával. A várólistáknak azonban vannak hátrányai, amelyeket figyelembe kell venni egy adott alkalmazás adatszerkezetének kiválasztásakor, ilyen például a memóriafelhasználás és a megvalósítás bonyolultsága.