data-structures
キュー

キューイントロ

キューはFIFO（先入れ先出し）データ構造です。つまり、キューに追加された最初の要素は、最初に削除された要素（「最初に出ます」）になります。

助けられるのを待っている顧客の例を考えてみましょう。アリス、ボブ、ダンはすべてスーパーにいる。アリスは支払う準備ができているので、彼女は出納係に近づきます。アリスは現在待ち行列に入っています。彼女は列の唯一の人なので、彼女は前と後ろの両方にいる。

キューは次のようになります。

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

今度はボブとダンが店員に近づく。それらはキューに追加されます。アリスはまだ正面にいて、ダンは後ろにいる：

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

人をキューに追加することは、エンキュー操作です。アリス、ボブ、ダンが待ち行列に入りました。キャッシャーは各顧客を支援するので、キューから取り除かれます。これは、デキュー操作です。キュー内のデータ要素を表す顧客は、キューの先頭からデキューされます。これは、レジ係に近づいた最初の顧客が最初に助けられる顧客（FIFO）であったことを意味します。

アレイを使用したキューの実装

序論で述べたように、キューフォローFIFO。 5つの主要業務：

1. エンキュー（x）：xをキューの後ろにプッシュします。
2. Dequeue（）：キューの先頭から要素をポップします。
3. isEmpty（）：キューが空であるかどうかを調べます。
4. isFull（）：キューがいっぱいかどうかを調べます。
5. frontValue（）：Queueのフロント値を返します。

すべての操作は定数O（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）時間にLinklistを使用して待ち行列にエンキューとデキューを表示するコード。

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