Buscar..


Introducción a la cola

La cola es una estructura de datos FIFO (primero en entrar, primero en salir), es decir, el primer elemento agregado a la cola será el primer elemento eliminado ("primero en salir").

Consideremos el ejemplo de clientes que esperan ser atendidos. Alice, Bob y Dan están todos en el supermercado. Alice está lista para pagar, así que se acerca al cajero. Alice está ahora en la cola. Ella es la única persona en la cola, por lo que está tanto al frente como en la parte posterior.

Ahora, la cola se ve así:

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

Ahora Bob y luego Dan se acercan al cajero. Se agregan a la cola. Alice todavía está en la parte delantera, y Dan está en la parte posterior:

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

Agregar una persona a la cola es la operación de puesta en cola. Alice, Bob y Dan han sido puestos en cola. A medida que el cajero ayude a cada cliente, se eliminarán de la cola. Esta es la operación de salida. Los clientes, que representan los elementos de datos en nuestra cola, se retiran de la cola de la cola. Esto significa que el primer cliente que se acercó al cajero fue el primer cliente que recibió ayuda (FIFO).

Implementación de la cola mediante el uso de matriz.

La cola sigue a FIFO como se menciona en la introducción. Cinco operaciones principales:

  1. Encolar (x): empuja x a la parte posterior de la cola.
  2. Dequeue (): muestra un elemento del frente de la cola.
  3. isEmpty (): encuentra si la cola está vacía o no.
  4. isFull (): encuentra si la cola está llena o no.
  5. frontValue (): devuelve el valor frontal de la cola.

Todas las operaciones son constantes de tiempo O (1).

Código :

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

Implementación de una cola circular.

La memoria se organiza de manera eficiente en una cola circular en comparación con la cola lineal.

En cola lineal:

introduzca la descripción de la imagen aquí

En cola circular:

introduzca la descripción de la imagen aquí

Los espacios restantes pueden ser utilizados:

Código para que haga lo mismo:

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

Todas las operaciones tienen O (1) complejidad de tiempo.

Representación de lista enlazada de la cola

La representación de listas vinculadas es más eficiente en términos de gestión de memoria.

Código para mostrar encoue y deque en una cola usando la lista de enlaces en 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;    
    
    
}


Modified text is an extract of the original Stack Overflow Documentation
Licenciado bajo CC BY-SA 3.0
No afiliado a Stack Overflow