Inom datavetenskap är en kö en linjär datastruktur där komponenterna sätts in i ena änden och tas bort från den andra änden enligt 'först-in, först ut'-principen (FIFO). Denna datastruktur kan användas för att styra en åtgärdssekvens eller lagra data. C är ett datorspråk med kökapacitet inkorporerad i form av arrayer eller länkade listor.
Egenskaper:
- En kö är en typ av linjär datastruktur som kan konstrueras med en array eller en länkad lista.
- Element flyttas till baksidan av kön medan de tas bort från framsidan.
- Enqueue (lägg till ett element på baksidan) och dequeue (ta bort ett element från framsidan) är två köoperationer.
- När element läggs till och tas bort ofta kan en kö byggas som en cirkulär kö för att förhindra minnesslöseri.
Använda Array:
För att implementera en kö i C med hjälp av en array, definiera först köns maximala storlek och deklarera en array av den storleken. De främre och bakre heltal sattes till 1. Den främre variabeln representerar det främre elementet i kön och den bakre variabeln representerar det bakre elementet.
Innan vi skjuter det nya elementet till den slutliga positionen i kön måste vi öka backvariabeln med 1. Kön är nu full och inga andra ytterligare element kan läggas till när bakpositionen når köns maximala kapacitet. Vi lägger till ett element längst fram i kön och ökar den främre variabeln med en bara för att ta bort ett element från kön. Om de främre och bakre positionerna är lika och inga fler komponenter kan raderas, så kan vi säga att kön är tom.
alfabetet av siffror
Nedan är en instans av en kö skriven i C som använder en array:
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('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; } Utdata från koden kommer att vara:
Produktion:
dateformat.format java
10 20 30 Queue is empty-1
Förklaring:
- Först köar vi tre element 10, 20 och 30 i kön.
- Sedan tar vi ur kö och skriver ut det främre elementet i kön, vilket är 10.
- Därefter tar vi ur kö och skriver ut det främre elementet i kön igen, vilket är 20.
- Sedan tar vi ur kö och skriver ut det främre elementet i kön igen, vilket är 30.
- Slutligen gör vi en avkö från en tom kö som matar ut 'Kö är tom' och returnerar -1.
Använda länkad lista:
Ett annat alternativt tillvägagångssätt för att konstruera en kö i programmeringsspråket C är att använda en länkad lista. Var och en av noderna i kön uttrycks med denna metod av en nod som innehåller elementvärdet och en pekare till följande nod i kön. För att hålla reda på den första och sista noden i kön används främre respektive bakre pekare.
Vi etablerar en ny nod med elementvärdet och sätter dess nästa pekare till NULL för att lägga till ett element i kön. Till den nya noden ställer vi in främre och bakre pekare om kön är tom. Om inte, uppdaterar vi den bakre pekaren och ställer in den gamla bakre nodens nästa pekare att peka på den nya noden.
När en nod tas bort från en kö, raderas den föregående noden först, sedan uppdateras frontpekaren till den efterföljande noden i kön, och slutligen frigörs minnet som den borttagna noden ockuperade. Om frontpekaren är NULL efter borttagning är kön tom.
svävar i css
Här är ett exempel på en kö implementerad i C med hjälp av en länkad lista:
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->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; } Utdata från koden kommer att vara:
Produktion:
10 20 30 Queue is empty-1
Förklaring:
- Först köar vi tre element 10, 20 och 30 i kön.
- Sedan tar vi ur kö och skriver ut det främre elementet i kön, vilket är 10.
- Därefter tar vi ur kö och skriver ut det främre elementet i kön igen, vilket är 20.
- Sedan tar vi ur kö och skriver ut det främre elementet i kön igen, vilket är 30.
- Slutligen försöker vi ställa oss i kö från den tomma kön, vilket skriver ut meddelandet 'Kön är tom' och returnerar -1.
Fördelar:
- Köer är särskilt användbara för att implementera algoritmer som kräver att element bearbetas i en exakt sekvens, såsom bredd-först-sökning och uppgiftsschemaläggning.
- Eftersom köoperationer har en O(1) tidskomplexitet, kan de exekveras snabbt även på enorma köer.
- Köer är särskilt flexibla eftersom de enkelt kan implementeras med hjälp av en array eller en länkad lista.
Nackdelar:
- En kö, till skillnad från en stack, kan inte konstrueras med en enda pekare, vilket gör köimplementeringen något mer involverad.
- Om kön är konstruerad som en array kan den snart fyllas om för många element läggs till, vilket resulterar i prestandaproblem eller möjligen en krasch.
- När man använder en länkad lista för att implementera kön kan minnesoverheaden för varje nod vara betydande, speciellt för små element.
Slutsats:
Applikationer som använder köer, en avgörande datastruktur, inkluderar operativsystem, nätverk och spel, för att bara nämna några. De är idealiska för algoritmer som måste hantera element i en viss ordning eftersom de är enkla att skapa med hjälp av en array eller länkad lista. Köer har dock nackdelar som måste beaktas när man väljer en datastruktur för en viss applikation, såsom minnesförbrukning och implementeringskomplexitet.