Krijimi i një radhe në C

Një radhë në C është në thelb një strukturë lineare të dhënash për të ruajtur dhe manipuluar elementët e të dhënave. Ai ndjek rendin e First In First Out (FIFO).

Në radhë, elementi i parë i futur në grup është elementi i parë që hiqet nga grupi.

Për shembull, le të shqyrtojmë skenarin e një tezge të rezervimit të biletave të autobusit. Këtu ndiqet moda e një radhe programimi C. Biletat shpërndahen në bazë të shërbim i pari vjen i pari d.m.th. i pari që hyn është i pari që shërbehet me biletat.

Një radhë është e hapur në të dy skajet. Një fund është parashikuar për futjen e të dhënave dhe skaji tjetër për fshirjen e të dhënave.

Një radhë mund të zbatohet me çdo gjuhë programimi si C, Java, Python, etj.

Operacionet e lidhura me një radhë në C

Një radhë që është një Strukturë Abstrakte e të Dhënave ofron operacionet e mëposhtme për manipulim me elementët e të dhënave:

isEmpty(): Për të kontrolluar nëse radha është bosh
isFull(): Për të kontrolluar nëse radha është plot apo jo
dequeue(): Heq elementin nga ana ballore e radhës
enqueue(): Fut elemente në fund të radhës
Front: Elementi i treguesit përgjegjës për marrjen e elementit të parë nga radha
Prapa: Elementi i treguesit përgjegjës për marrjen e elementit të fundit nga radha

Punimi i strukturës së të dhënave në radhë

Radha ndjek modelin First-In-First-Out. Elementi i parë është i pari që nxirret nga lista e elementeve.

Përpara dhe Prapa mbajnë regjistrimin e elementit të parë dhe të fundit në radhë.
Në fillim, duhet të inicializojmë radhën duke vendosur Front=-1 dhe Rear=-1
Për të futur elementin (radhë), duhet të kontrollojmë nëse radha është tashmë e plotë, d.m.th. kontrolloni kushtin për Overflow. Nëse radha nuk është e plotë, do të duhet të rrisim vlerën e indeksit të pasmë me 1 dhe ta vendosim elementin në pozicionin e ndryshores së treguesit të pasmë. Kur arrijmë të fusim elementin e parë në radhë, duhet të vendosim vlerën e Frontit në 0.
Për të hequr elementin (dequeue) nga radha, duhet të kontrollojmë nëse radha është tashmë bosh, p.sh. kontrolloni kushtin për Underflow. Nëse radha nuk është bosh, do të duhet ta heqim dhe ta kthejmë elementin në pozicionin e treguesit të përparmë dhe më pas të rrisim vlerën e indeksit të përparmë me 1. Kur marrim të heqim elementin e fundit nga radha<, do të duhet të caktojmë vlerat e indeksit të përparmë dhe të pasmë në -1.

Zbatimi i Radhës në C

Radhët në C mund të zbatohen duke përdorur vargje, lista, struktura, etj. Më poshtë kemi implementuar radhët duke përdorur vargje në C.

Shembull:

#include <stdio.h>
# define SIZE 100
void enqueue();
void dequeue();
void show();
int inp_arr[SIZE];
int Rear = - 1;
int Front = - 1;
main()
{
    int ch;
    while (1)
    {
        printf("1.Enqueue Operation\n");
        printf("2.Dequeue Operation\n");
        printf("3.Display the Queue\n");
        printf("4.Exit\n");
        printf("Enter your choice of operations : ");
        scanf("%d", &ch);
        switch (ch)
        {
            case 1:
            enqueue();
            break;
            case 2:
            dequeue();
            break;
            case 3:
            show();
            break;
            case 4:
            exit(0);
            default:
            printf("Incorrect choice \n");
        } 
    } 
} 
 
void enqueue()
{
    int insert_item;
    if (Rear == SIZE - 1)
       printf("Overflow \n");
    else
    {
        if (Front == - 1)
      
        Front = 0;
        printf("Element to be inserted in the Queue\n : ");
        scanf("%d", &insert_item);
        Rear = Rear + 1;
        inp_arr[Rear] = insert_item;
    }
} 
 
void dequeue()
{
    if (Front == - 1 || Front > Rear)
    {
        printf("Underflow \n");
        return ;
    }
    else
    {
        printf("Element deleted from the Queue: %d\n", inp_arr[Front]);
        Front = Front + 1;
    }
} 
 
void show()
{
    
    if (Front == - 1)
        printf("Empty Queue \n");
    else
    {
        printf("Queue: \n");
        for (int i = Front; i <= Rear; i++)
            printf("%d ", inp_arr[i]);
        printf("\n");
    }
}

Dalja:

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 10

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 20

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 3
Queue: 
10 20 

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 2
Element deleted from the Queue: 10

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations: 3
Queue: 
20

Zbatimi i Radhës duke përdorur Stacks

Stack Data Structure mund të përdoret për të zbatuar operacionet e radhës. Do të na duhen dy rafte për të zbatuar një radhë duke i përdorur ato. Përpara se të punoni me shembujt e mëposhtëm, sigurohuni që e kuptoni shumë mirë funksionimin e pirgjeve.

Një radhë mund të zbatohet duke përdorur Stacks në njërën nga mënyrat e mëposhtme:

Të kushtosh operacionin e radhës
Të bësh të kushtueshëm operacionin e shtrimit

Metoda 1: Bërja e operacionit në radhë të kushtueshme

Le të supozojmë dy rafte: S1 dhe S2 për të zbatuar operacionet e radhës duke përdorur të njëjtën gjë.

Nëse S1 nuk është bosh, shtyni të gjithë elementët në stivën 2 (S2)
Për të kryer operacionin e radhës, do të supozojmë se 'x' është elementi që do të futet në radhë. Ne do të shtyjmë 'x' përsëri në Stack S1 që të dalë në krye.
Më tej, shtyni të gjithë elementët e pirgut S2 përsëri në Stack S1

Shënim: Kompleksiteti kohor i operacionit në radhë do të ishte O(n).

Për të kryer operacionin dequeue, do të na duhet të nxjerrim një artikull nga Stack S1 pasi tani elementi i parë i futur është në krye në S1 në vend që të jetë në fund. li>

Shënim: Kompleksiteti kohor i operacionit në radhë do të ishte O(1).

Nëse analizoni kompleksitetin kohor të operacioneve Enqueue dhe Dequeue duke përdorur Stack, do të zbuloni se operacioni Enqueue është shumë më i kushtueshëm se operacioni Dequeue.

Kështu, siç u përmend më lart, ne bëjmë që elementi i parë i futur ose më i vjetër i futur të mbetet në krye të Stack S1 në mënyrë që të hiqet kur të thirret operacioni Dequeue.

Metoda 2: Bërja e operacionit Dequeue të kushtueshme

Le të supozojmë përsëri dy Stacks: S1 dhe S2 për të zbatuar operacionet e radhës duke përdorur të njëjtën gjë.

Për të zbatuar operacionin në radhë, ne fusim elementin e sapofutur në krye të Stack S1. Kështu, kompleksiteti kohor i operacionit Enqueue duke përdorur Stacks bëhet O(1).
Për zbatimin e operacionit në radhë, ai kontrollon për gjendjen e rrjedhës së poshtme të Stack S1 dhe S2. Nëse të dyja Stacks janë bosh, do të shfaqet një gabim.
Nëse Stack S2 është bosh dhe S1 nuk është bosh, atëherë të gjithë elementët nga Stack S1 zhvendosen në Stack S2 dhe elementi i sipërm i Stack S2 del jashtë dhe kthehet jashtë operacionit Dequeue.
Kështu, kompleksiteti kohor i operacionit të rradhës duke përdorur Stacks bëhet O(n).

Aplikimet e strukturës së të dhënave në radhë

Planifikimi i CPU-së
Planifikimi i diskut
Transferimi asinkron i të dhënave ndërmjet procesorëve si p.sh. File IO, etj.
Algoritmi i kërkimit në gjerësi të parë (BFS)

konkluzioni

Në këtë artikull, ne kemi kuptuar funksionimin e strukturës së të dhënave të radhës dhe gjithashtu kemi vënë në hije zbatimin e radhëve duke përdorur strukturën e të dhënave të rafte.

Referencat

Radhë në C
Radhë duke përdorur Stacks