data-structures
पंक्ति

कतार में परिचय

कतार एक FIFO (पहली-पहली, पहली-आउट) डेटा-संरचना है, अर्थात कतार में जोड़ा गया पहला तत्व हटा दिया गया पहला तत्व होगा ("पहला आउट")।

आइए हम मदद करने के लिए इंतजार कर रहे ग्राहकों के उदाहरण पर विचार करें। एलिस, बॉब और डैन सभी सुपरमार्केट में हैं। ऐलिस भुगतान करने के लिए तैयार है, इसलिए वह कैशियर के पास जाती है। एलिस अब कतार में है। वह कतार में एकमात्र व्यक्ति है, इसलिए वह आगे और पीछे दोनों जगह है।

अब, कतार इस तरह दिखती है:

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

अब बॉब और फिर दान कैशियर के पास पहुंचे। उन्हें कतार में जोड़ा जाता है। ऐलिस अभी भी सामने है, और डैन सबसे पीछे है:

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

किसी व्यक्ति को कतार में जोड़ना एन्केयू ऑपरेशन है। ऐलिस, बॉब और डैन की कल्पना की गई है। जैसा कि कैशियर प्रत्येक ग्राहक की मदद करता है, उन्हें कतार से हटा दिया जाएगा। यह एक dequeue ऑपरेशन है। ग्राहक, जो हमारी कतार में डेटा तत्वों का प्रतिनिधित्व करते हैं, उन्हें कतार के सामने से हटा दिया जाता है। इसका मतलब यह है कि कैशियर के पास पहुंचने वाला पहला ग्राहक मदद करने वाला पहला ग्राहक था (एफआईएफओ)।

सरणी का उपयोग करके कतार कार्यान्वयन।

परिचय में उल्लिखित कतार का अनुसरण करें। पांच प्रमुख ऑपरेशन:

1. Enqueue (x): x को कतार के पीछे धकेलता है।
2. Dequeue (): कतार के सामने से एक तत्व पॉप करता है।
3. isEmpty (): ढूँढता है कि कतार खाली है या नहीं।
4. isFull (): ढूँढता है कि कतार भरी हुई है या नहीं।
5. frontValue (): कतार का अगला मान लौटाता है।

सभी ऑपरेशन निरंतर ओ (1) समय हैं।

कोड :

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

एक परिपत्र कतार का कार्यान्वयन

लीनियर कतार की तुलना में मेमोरी को एक गोलाकार कतार में कुशलतापूर्वक व्यवस्थित किया जाता है।

रैखिक कतार में:

परिपत्र कतार में:

शेष रिक्त स्थान का उपयोग किया जा सकता है:

कोड ऐसा करने के लिए:

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

सभी ऑपरेशनों में O (1) समय जटिलता है।

लिंक्ड कतार की प्रतिनिधित्व सूची

मेमोरी मैनेजर के संदर्भ में लिंक्ड सूची प्रतिनिधित्व अधिक कुशल है।

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