Inden for datalogi er en kø en lineær datastruktur, hvor komponenterne sættes ind i den ene ende og fjernes fra den anden ende efter 'first-in, first-out' (FIFO) princippet. Denne datastruktur kan bruges til at styre en handlingssekvens eller gemme data. C er et computersprog med køkapacitet indbygget i form af arrays eller sammenkædede lister.

Egenskaber:

• En kø er en type lineær datastruktur, der kan konstrueres med et array eller en sammenkædet liste.
• Elementer flyttes bagerst i køen, mens de fjernes forfra.
• Enqueue (tilføj et element til bagsiden) og dequeue (fjern et element fra forsiden) er to køoperationer.
• Når elementer tilføjes og fjernes ofte, kan en kø bygges som en cirkulær kø for at forhindre spild af hukommelse.

Brug af Array:

For at implementere en kø i C ved hjælp af et array skal du først definere køens maksimale størrelse og erklære et array af den størrelse. De forreste og bageste heltal blev henholdsvis sat til 1. Den forreste variabel repræsenterer det forreste element i køen, og den bagerste variable repræsenterer det bagerste element.

Før vi skubber det nye element til den endelige position i køen, skal vi øge den tilbage variable med 1. Køen er nu fuld, og der kan ikke tilføjes andre ekstra elementer, når den bagerste position når køens maksimale kapacitet. Vi tilføjer et element foran i køen og øger frontvariablen med én kun for at fjerne et element fra køen. Hvis de forreste og bageste positioner er ens, og der ikke kan slettes flere komponenter, kan vi derfor sige, at køen er tom.

Nedenfor er et eksempel på en kø skrevet i C, der gør brug af et array:

C programmeringssprog:

 #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; } 

Udgangen af ​​koden vil være:

hvor stor er min skærm

Produktion:

 10 20 30 Queue is empty-1 

Forklaring:

1. Først sætter vi tre elementer 10, 20 og 30 i køen.
2. Derefter sætter vi køen ud af køen og udskriver det forreste element i køen, som er 10.
3. Dernæst sætter vi køen ud og udskriver det forreste element i køen igen, som er 20.
4. Derefter sætter vi køen ud af køen og udskriver det forreste element i køen igen, hvilket er 30.
5. Til sidst laver vi en dekø fra en tom kø, der udsender 'Kø er tom' og returnerer -1.

Brug af linket liste:

En anden alternativ tilgang til at konstruere en kø i programmeringssproget C er at bruge en sammenkædet liste. Hver af knudepunkterne i køen udtrykkes ved hjælp af denne metode af en knude, som indeholder elementværdien og en pointer til den følgende knude i køen. For at holde styr på første og sidste knudepunkt i køen, bruges henholdsvis front- og bagerviser.

Vi etablerer en ny node med elementværdien og sætter dens næste pointer til NULL for at tilføje et element til køen. Til den nye node sætter vi de forreste og bagerste pointere, hvis køen er tom. Hvis ikke, opdaterer vi den bagerste pointer og indstiller den gamle bagerste nodes næste pointer til at pege på den nye node.

Når du sletter en node fra en kø, slettes den foregående node først, derefter opdateres frontpointeren til den efterfølgende node i køen, og til sidst frigives hukommelsen, som den fjernede node optog. Hvis frontmarkøren er NULL efter fjernelse, er køen tom.

Her er et eksempel på en kø implementeret i C ved hjælp af en linket liste:

C programmeringssprog:

 #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; } 

Udgangen af ​​koden vil være:

Produktion:

 10 20 30 Queue is empty-1 

Forklaring:

1. Først sætter vi tre elementer 10, 20 og 30 i køen.
2. Derefter sætter vi køen ud af køen og udskriver det forreste element i køen, som er 10.
3. Dernæst sætter vi køen ud og udskriver det forreste element i køen igen, som er 20.
4. Derefter sætter vi køen ud af køen og udskriver det forreste element i køen igen, hvilket er 30.
5. Til sidst forsøger vi at dekø fra den tomme kø, som udskriver beskeden 'Kø er tom' og returnerer -1.

Fordele:

• Køer er især nyttige til implementering af algoritmer, der kræver, at elementer behandles i en præcis rækkefølge, såsom bredde-først-søgning og opgaveplanlægning.
• Fordi køoperationer har en O(1) tidskompleksitet, kan de udføres hurtigt selv på enorme køer.
• Køer er særligt fleksible, da de ganske enkelt kan implementeres ved hjælp af et array eller en sammenkædet liste.

Ulemper:

• En kø, i modsætning til en stak, kan ikke konstrueres med en enkelt pointer, hvilket gør køimplementeringen lidt mere involveret.
• Hvis køen er konstrueret som et array, kan den snart fyldes op, hvis der tilføjes for mange elementer, hvilket resulterer i præstationsbekymringer eller muligvis et nedbrud.
• Når du bruger en sammenkædet liste til at implementere køen, kan hukommelsesoverhead for hver node være betydelig, især for små elementer.

Konklusion:

Applikationer, der bruger køer, en afgørende datastruktur, omfatter operativsystemer, netværk og spil, for blot at nævne nogle få. De er ideelle til algoritmer, der skal håndtere elementer i en bestemt rækkefølge, da de er nemme at oprette ved hjælp af et array eller linket liste. Køer har dog ulemper, som skal overvejes, når man vælger en datastruktur til en bestemt applikation, såsom hukommelsesforbrug og implementeringskompleksitet.