data-structures
Wachtrij

Inleiding tot wachtrij

De wachtrij is een FIFO-gegevensstructuur (first-in, first-out), dat wil zeggen dat het eerste element dat aan de wachtrij wordt toegevoegd, het eerste verwijderde element is ("first out").

Laten we het voorbeeld bekijken van klanten die wachten om geholpen te worden. Alice, Bob en Dan zijn allemaal in de supermarkt. Alice is klaar om te betalen, dus ze benadert de kassier. Alice staat nu in de rij. Ze is de enige persoon in de rij, dus ze staat zowel vooraan als achteraan.

Nu ziet de wachtrij er als volgt uit:

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

Nu benaderen Bob en Dan Dan de kassier. Ze worden toegevoegd aan de wachtrij. Alice staat nog steeds vooraan en Dan achteraan:

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

Een persoon aan de wachtrij toevoegen is de enqueue-bewerking. Alice, Bob en Dan zijn enthousiast gemaakt. Omdat de kassier elke klant helpt, worden deze uit de wachtrij verwijderd. Dit is de dequeue-bewerking. Klanten, die de gegevenselementen in onze wachtrij vertegenwoordigen, worden van de voorkant van de wachtrij ontdaan. Dit betekent dat de eerste klant die de caissière benaderde, de eerste klant was die werd geholpen (FIFO).

Wachtrij-implementatie met behulp van array.

Wachtrij volg FIFO zoals in de inleiding wordt vermeld. Vijf belangrijke operaties:

1. Enqueue (x): duwt x naar de achterkant van de wachtrij.
2. Dequeue (): springt een element uit de voorkant van de wachtrij.
3. isEmpty (): Vindt of de wachtrij leeg is of niet.
4. isFull (): Vindt of de wachtrij vol is of niet.
5. frontValue (): Retourneert de frontwaarde van de wachtrij.

Alle bewerkingen zijn constante O (1) tijd.

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

Implementatie van een circulaire wachtrij

Geheugen is efficiënt georganiseerd in een cirkelvormige wachtrij in vergelijking met lineaire wachtrij.

In lineaire wachtrij:

In circulaire wachtrij:

Resterende spaties kunnen worden gebruikt:

Code ervoor hetzelfde te doen:

#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 bewerkingen hebben O (1) tijdcomplexiteit.

Gekoppelde lijstweergave van wachtrij

Weergave van gekoppelde lijsten is efficiënter in termen van geheugenbeheer.

Code om enqueue en deque in een wachtrij weer te geven met behulp van Linklist in O (1) tijd.

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