data-structures
Warteschlange

Einführung in die Warteschlange

Die Warteschlange ist eine FIFO (First-In, First-Out) -Datenstruktur, dh das erste Element, das der Warteschlange hinzugefügt wird, ist das erste Element, das entfernt wird ("first out").

Betrachten wir das Beispiel von Kunden, die darauf warten, geholfen zu werden. Alice, Bob und Dan sind alle im Supermarkt. Alice ist bereit zu zahlen, also geht sie zur Kassiererin. Alice steht jetzt in der Schlange. Sie ist die einzige Person in der Schlange, also ist sie sowohl vorne als auch hinten.

Nun sieht die Warteschlange so aus:

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

Jetzt nähern sich Bob und Dan der Kassiererin. Sie werden der Warteschlange hinzugefügt. Alice ist immer noch vorne und Dan hinten:

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

Das Hinzufügen einer Person zur Warteschlange ist der Vorgang in der Warteschlange. Alice, Bob und Dan wurden in die Warteschlange gestellt. Da der Kassierer jedem Kunden hilft, werden sie aus der Warteschlange entfernt. Dies ist die Entnahmeoperation. Kunden, die die Datenelemente in unserer Warteschlange darstellen, werden an der Vorderseite der Warteschlange abgestellt. Dies bedeutet, dass der erste Kunde, der sich an die Kasse wandte, der erste Kunde war, dem geholfen wurde (FIFO).

Warteschlangenimplementierung mit Array.

Warteschlange folgt dem FIFO, wie es in der Einführung erwähnt wird. Fünf Hauptoperationen:

1. Warteschlange (x): Schiebt x an die Rückseite der Warteschlange.
2. Dequeue (): Ein Element wird vor der Warteschlange angezeigt.
3. isEmpty (): Sucht, ob die Warteschlange leer ist oder nicht.
4. isFull (): Erkennt, ob die Warteschlange voll ist oder nicht.
5. frontValue (): Gibt den vorderen Wert der Warteschlange zurück.

Alle Operationen sind konstante Zeit O (1).

Code :

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

Implementierung einer zirkularen Warteschlange

Der Speicher ist im Vergleich zur linearen Warteschlange effizient in einer kreisförmigen Warteschlange organisiert.

In der linearen Warteschlange:

In der zirkularen Warteschlange:

Restplätze können verwendet werden:

Code für dasselbe:

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

Alle Operationen haben eine O (1) -Komplexität.

Darstellung der verknüpften Liste der Warteschlange

Die Darstellung der verknüpften Liste ist im Hinblick auf das Speichermanagement effizienter.

Code zum Anzeigen von Enqueue und Deque in einer Warteschlange mithilfe der Linkliste in O (1) -Zeit.

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