data-structures
Очередь

Введение в очередь

Очередь представляет собой структуру данных FIFO (first-in, first-out), то есть первый элемент, добавленный в очередь, будет первым удаленным элементом («first out»).

Давайте рассмотрим пример клиентов, ожидающих помощи. Алиса, Боб и Дэн все в супермаркете. Алиса готова заплатить, поэтому она подходит к кассиру. Алиса сейчас в очереди. Она - единственный человек в очереди, поэтому она как спереди, так и сзади.

Теперь очередь выглядит так:

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

Теперь Боб, а затем Дэн приближаются к кассиру. Они добавляются в очередь. Алиса все еще впереди, а Дэн сзади:

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

Добавление человека в очередь - операция очереди. Алиса, Боб и Дэн были выставлены в очередь. Поскольку кассир помогает каждому клиенту, они будут удалены из очереди. Это операция dequeue. Клиенты, которые представляют элементы данных в нашей очереди, выгружаются из передней части очереди. Это означает, что первым клиентом, который подошел к кассиру, был первый клиент, которому помогли (FIFO).

Реализация очереди с использованием массива.

Очередь следует за FIFO, как указано во введении. Пять основных операций:

1. Enqueue (x): толкает x в обратную сторону очереди.
2. Dequeue (): выдает элемент из передней части очереди.
3. isEmpty (): Определяет, является ли очередь пустой или нет.
4. isFull (): Определяет, заполнена ли очередь или нет.
5. frontValue (): возвращает переднее значение очереди.

Все операции - это постоянное время 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) временную сложность.

Представление очереди очередей

Представление объединенного списка более эффективно с точки зрения управления памятью.

Код для отображения очереди и дека в очереди с использованием Linklist в 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;    
    
    
}