data-structures
Cola
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:
- Encolar (x): empuja x a la parte posterior de la cola.
- Dequeue (): muestra un elemento del frente de la cola.
- isEmpty (): encuentra si la cola está vacía o no.
- isFull (): encuentra si la cola está llena o no.
- 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:
En cola circular:
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;
}