data-structures
Kolejka

Wprowadzenie do kolejki

Kolejka jest strukturą danych FIFO (pierwsze wejście, pierwsze wyjście), tzn. Pierwszym elementem dodanym do kolejki będzie pierwszy usunięty element („pierwsze wyjście”).

Rozważmy przykład klientów oczekujących pomocy. Alice, Bob i Dan są w supermarkecie. Alice jest gotowa zapłacić, więc podchodzi do kasy. Alice jest teraz w kolejce. Jest jedyną osobą w kolejce, więc jest zarówno z przodu, jak iz tyłu.

Teraz kolejka wygląda następująco:

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

Teraz Bob i Dan podchodzą do kasy. Są dodawane do kolejki. Alice jest nadal z przodu, a Dan z tyłu:

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

Dodanie osoby do kolejki jest operacją kolejkowania. Alice, Bob i Dan zostali umieszczeni w kolejce. Ponieważ kasjer pomaga każdemu klientowi, zostaną one usunięte z kolejki. To jest operacja usuwania kolejki. Klienci, którzy reprezentują elementy danych w naszej kolejce, są usuwani z kolejki z przodu kolejki. Oznacza to, że pierwszy klient, który zbliżył się do kasy, był pierwszym klientem, któremu udzielono pomocy (FIFO).

Implementacja kolejki za pomocą tablicy.

Kolejka podąża za FIFO, jak wspomniano we wstępie. Pięć głównych operacji:

1. Enqueue (x): wypycha x na tył kolejki.
2. Dequeue (): wysuwa element z przodu kolejki.
3. isEmpty (): Sprawdza, czy kolejka jest pusta, czy nie.
4. isFull (): Sprawdza, czy kolejka jest pełna, czy nie.
5. frontValue (): Zwraca pierwszą wartość kolejki.

Wszystkie operacje są stałym czasem O (1).

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

Realizacja kolejki cyklicznej

Pamięć jest efektywnie zorganizowana w kolejkę kołową w porównaniu do kolejki liniowej.

W kolejce liniowej:

W kolejce cyklicznej:

Pozostałych miejsc można użyć:

Kod, aby zrobił to samo:

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

Wszystkie operacje mają złożoność czasową O (1).

Reprezentacja połączonej listy kolejki

Reprezentacja listy połączonej jest bardziej wydajna pod względem zarządzania pamięcią.

Kod pokazujący kolejkowanie i usuwanie w kolejce przy użyciu listy linków w czasie O (1).

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