KØ I C

I informatikk er en kø en lineær datastruktur der komponentene settes inn i den ene enden og fjernes fra den andre enden i henhold til 'først inn, først ut' (FIFO)-prinsippet. Denne datastrukturen kan brukes til å kontrollere en handlingssekvens eller lagre data. C er et dataspråk med køkapasitet innlemmet i form av arrays eller koblede lister.

Kjennetegn:

En kø er en type lineær datastruktur som kan konstrueres med en matrise eller en koblet liste.
Elementer flyttes bakerst i køen mens de fjernes fra forsiden.
Enqueue (legg til et element på baksiden) og dequeue (fjern et element fra forsiden) er to køoperasjoner.
Når elementer legges til og fjernes ofte, kan en kø bygges som en sirkulær kø for å forhindre sløsing med minne.

Bruke Array:

For å implementere en kø i C ved å bruke en matrise, definerer du først køens maksimale størrelse og erklærer en matrise med den størrelsen. Heltallet foran og bak ble henholdsvis satt til 1. Den fremre variabelen representerer det fremre elementet i køen, og den bakre variabelen representerer det bakre elementet.

Før vi skyver det nye elementet til den endelige posisjonen i køen, må vi øke tilbake variabelen med 1. Køen er nå full og ingen andre tilleggselementer kan legges til når bakposisjonen når køens maksimale kapasitet. Vi legger til et element foran i køen og øker frontvariabelen med én bare for å fjerne et element fra køen. Hvis front- og bakposisjonen er like og ingen flere komponenter kan slettes, kan vi derfor si at køen er tom.

Nedenfor er en forekomst av en kø skrevet i C som gjør bruk av en matrise:

C programmeringsspråk:

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

Utgangen av koden vil være:

hvordan konvertere streng til int i java

Produksjon:

 10 20 30 Queue is empty-1

Forklaring:

Først setter vi tre elementer 10, 20 og 30 inn i køen.
Deretter legger vi ut køen og skriver ut det fremre elementet i køen, som er 10.
Deretter legger vi ut køen og skriver ut frontelementet i køen igjen, som er 20.
Deretter legger vi ut køen og skriver ut frontelementet i køen igjen, som er 30.
Til slutt lager vi en dekø fra en tom kø som gir ut 'Kø er tom' og returnerer -1.

Bruke koblet liste:

En annen alternativ tilnærming til å konstruere en kø i programmeringsspråket C er å bruke en koblet liste. Hver av nodene i køen uttrykkes ved hjelp av denne metoden av en node som inneholder elementverdien og en peker til følgende node i køen. For å holde styr på den første og siste noden i køen, brukes henholdsvis front- og bakpekere.

Vi etablerer en ny node med elementverdien og setter den neste pekeren til NULL for å legge til et element i køen. Til den nye noden setter vi fremre og bakre pekere hvis køen er tom. Hvis ikke, oppdaterer vi den bakre pekeren og setter den gamle bakre nodens neste peker til å peke til den nye noden.

Når du sletter en node fra en kø, slettes den foregående noden først, deretter oppdateres frontpekeren til den påfølgende noden i køen, og til slutt frigjøres minnet som den fjernede noden okkuperte. Hvis frontpekeren er NULL etter fjerning, er køen tom.

Her er et eksempel på en kø implementert i C ved hjelp av en koblet liste:

C programmeringsspråk:

 #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-&gt;data = element; new_node-&gt;next = NULL; if (front == NULL &amp;&amp; rear == NULL) { front = rear = new_node; return; } rear-&gt;next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf(&apos;Queue is empty&apos;); return -1; } struct Node* temp = front; int element = temp-&gt;data; if (front == rear) { front = rear = NULL; } else { front = front-&gt;next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf(&apos;%d &apos;, dequeue()); printf(&apos;%d &apos;, dequeue()); printf(&apos;%d &apos;, dequeue()); printf(&apos;%d &apos;, dequeue()); return 0; }

Utgangen av koden vil være:

Produksjon:

 10 20 30 Queue is empty-1

Forklaring:

Først setter vi tre elementer 10, 20 og 30 inn i køen.
Deretter legger vi ut køen og skriver ut det fremre elementet i køen, som er 10.
Deretter legger vi ut køen og skriver ut frontelementet i køen igjen, som er 20.
Deretter legger vi ut køen og skriver ut frontelementet i køen igjen, som er 30.
Til slutt prøver vi å dekø fra den tomme køen, som skriver ut meldingen 'Køen er tom' og returnerer -1.

Fordeler:

Køer er spesielt nyttige for å implementere algoritmer som krever at elementer behandles i en presis sekvens, for eksempel bredde-først søk og oppgaveplanlegging.
Fordi køoperasjoner har en O(1)-tidskompleksitet, kan de utføres raskt selv på enorme køer.
Køer er spesielt fleksible siden de enkelt kan implementeres ved hjelp av en matrise eller en koblet liste.

Ulemper:

En kø, i motsetning til en stabel, kan ikke konstrueres med en enkelt peker, noe som gjør køimplementeringen litt mer involvert.
Hvis køen er konstruert som en matrise, kan den snart fylles opp hvis for mange elementer legges til, noe som resulterer i ytelsesbekymringer eller muligens krasj.
Når du bruker en koblet liste for å implementere køen, kan minneoverheaden til hver node være betydelig, spesielt for små elementer.

Konklusjon:

Applikasjoner som bruker køer, en avgjørende datastruktur, inkluderer operativsystemer, nettverk og spill, for bare å nevne noen. De er ideelle for algoritmer som må håndtere elementer i en bestemt rekkefølge siden de er enkle å lage ved hjelp av en matrise eller koblet liste. Køer har imidlertid ulemper som må vurderes når man velger en datastruktur for en bestemt applikasjon, for eksempel minneforbruk og implementeringskompleksitet.

TechCodeview