data-structures
Kö

Introduktion till kö

Kön är en FIFO (first-in, first-out) datastruktur, dvs det första elementet som läggs till i kön är det första elementet som tas bort ("first out").

Låt oss betrakta exemplet på kunder som väntar på att få hjälp. Alice, Bob och Dan är alla i stormarknaden. Alice är redo att betala, så hon närmar sig kassan. Alice är nu i kö. Hon är den enda personen i kön, så hon är både framme och bak.

Nu ser kön så ut:

              |-------|
              | Alice | cashier
              |-------|
                ▲   ▲
back of queue ──┘   └── front of queue

Nu närmar sig Bob och sedan Dan kassören. De läggs till i kön. Alice är fortfarande framtill och Dan är bakom:

              |-------||-------||-------|
              |  Dan  ||  Bob  || Alice | cashier
              |-------||-------||-------|
                ▲                     ▲
back of queue ──┘                     └── front of queue

Att lägga till en person i kön är enque-operationen. Alice, Bob och Dan har blivit förtryckta. När kassören hjälper varje kund kommer de att tas bort från kön. Detta är avvecklingsoperationen. Kunder, som representerar dataelementen i vår kö, avlägsnas från fronten på kön. Detta innebär att den första kunden som närmade sig kassören var den första kunden som fick hjälp (FIFO).

Köimplementering med hjälp av matris.

Kö följer FIFO som det nämns i inledningen. Fem stora operationer:

1. Enqueue (x): skjuter x till baksidan av kön.
2. Dequeue (): visar ett element framför kön.
3. isEmpty (): Finns om kön är tom eller inte.
4. isFull (): Finns om kön är full eller inte.
5. frontValue (): Returnerar det främre värdet för köen.

Alla operationer är konstant O (1) tid.

Kod :

#include<stdio.h>

#define MAX 4

int front = -1;
int rear = -1;
int a[MAX];

bool isFull() {
  if(rear == MAX-1)
    return true;
  else
    return false;    
}

bool isEmpty() {
  if(rear == -1 && front==-1)
    return true;
  else
    return false;    
}

void enqueue(int data) {
  if (isFull()){
    printf("Queue is full\n");
    return;
  } else if(isEmpty()) {
    front = rear =0;
  } else {
    rear = rear + 1;
    a[rear] = data;      
  }
}
    
void deque(){
  if(isEmpty()){
    printf("Queue is empty\n");
    return;
  } else if(front == rear) {
    front =-1;
    rear =-1;
  } else {
    front = front + 1;
  }
}
    
void print(){
  printf("Elements in Queue are\n");  
  for(int i = front;i<=rear;i++){
    printf("%d ",a[i]);
  }
  printf("\n");
}

int frontValue(){  
  printf("The front element after set of enqueue and dequeue is %d\n", a[front]);
}

int main(){
  deque();     // Queue is empty message will be thrown
  enqueue(10);
  print();
  enqueue(20);
  print();
  enqueue(30);
  print();
  enqueue(40);
  frontValue();
  print();
  enqueue(50);
  frontValue();
  deque();
  deque();
  enqueue(50);
  frontValue();
  print();                    
  return 0;
}

Implementering av en cirkulär kö

Minne är effektivt organiserat i en cirkulär kö jämfört med linjär kö.

I linjär kö:

I cirkulär kö:

Återstående utrymmen kan användas:

Kod för att göra samma sak:

#include<stdio.h>
#define MAX 10000
int front = -1;
int rear = -1;
int a[MAX]; 


bool isFull() {
  if((rear+1) % MAX == front)
    return true;
  else
    return false;    
}

bool isEmpty() {
  if(rear == -1 && front==-1)
    return true;
  else
    return false;    
}

void enqueue(int data) {
  if (isFull()){
    printf("Queue is full\n");
    return;
  } else if(isEmpty()) {
    front = rear = 0;
  } else {
    rear = (rear+1) % MAX;
    a[rear] = data;
  }
}

void deque() {
  if(isEmpty()){
    printf("Queue is empty\n");
    return;
  } else if(front == rear) {
    front =-1;
    rear =-1;
  } else {
    front = (front+1) % MAX;
  }
}

int frontValue() {
  return(a[front]);
}

int main() {   
  deque(); 
  enqueue(10);
  enqueue(20);
  enqueue(30);       
  enqueue(40);
  enqueue(50);
  frontValue();
  return 0;
}

Alla operationer har O (1) tidskomplexitet.

Länkad lista av kö

Länkad listrepresentation är effektivare när det gäller minneshantering.

Kod för att visa enqueue och deque i en kö med länklista i O (1) tid.

#include<stdio.h>
#include<malloc.h>

struct node{
    int data;
    node* next;
};

node* front = NULL;
node* rear = NULL;

void enqueue(int data){      //adds element to end
    
    struct node* temp = (struct node*)malloc(sizeof(struct node*));
    temp->data = data;
    temp->next =NULL;
    
    if(front== NULL && rear == NULL){
        front = rear = temp;
        return;
    }
    rear->next = temp;
    rear= temp;
}

void deque(){     //removes element from front
    node* temp = front;
    
    if(front== NULL && rear == NULL){
        return;
    }
    else if (front==rear){
        front =rear = NULL;
    }
    else
    front= front ->next;
    
    free(temp);
}

void print(){
    node* temp = front;
    
    for(; temp != rear; temp=temp->next){
        printf("%d ",temp->data);
    }
    //for printing the rear element
    
        printf("%d ",temp->data);
    printf("\n");
}



int main(){
    
    enqueue(20);
    enqueue(50);
        enqueue(70);
        printf("After set of enques\n");
        print();
        
        deque();
        printf("After 1 deque\n");    
        print();
        
        return 0;    
    
    
}