Creando una cola en C - Para Programadores

Una cola en C es básicamente un sistema linear data structurepara almacenar y manipular los elementos de datos. Sigue el orden de Primero en entrar, primero en salir (FIFO) .

En las colas, el primer elemento ingresado en la matriz es el primer elemento que se elimina de la matriz.

Por ejemplo, consideremos el escenario de un puesto de reserva de billetes de autobús. Aquí se sigue el modelo de una cola de programación en C. Los billetes se distribuyen por orden de llegada, es decir, el primero en entrar es el primero en recibir los billetes.

Una cola está abierta en ambos extremos . Un extremo está destinado a la inserción de datos y el otro extremo a la eliminación de datos.

Una cola se puede implementar con cualquier lenguaje de programación como C, Java, Python, etc.

Operaciones asociadas a una cola en C

Una cola, al ser una estructura de datos abstracta, proporciona las siguientes operaciones para la manipulación de los elementos de datos:

isEmpty():Para comprobar si la cola está vacía
isFull():Para comprobar si la cola está llena o no
dequeue(): Elimina el elemento del lado frontal de la cola.
enqueue(): Inserta elementos al final de la cola.
Front:Elemento puntero responsable de obtener el primer elemento de la cola.
Rear:Elemento puntero responsable de recuperar el último elemento de la cola.

Funcionamiento de la estructura de datos de cola

La cola sigue el patrón “primero en entrar, primero en salir”. El primer elemento es el primero que se extrae de la lista de elementos.

Fronty Rearlos punteros mantienen el registro del primer y último elemento de la cola.
Primero, necesitamos inicializar la cola configurando Front = -1yRear = -1
Para insertar el elemento ( enqueue ), debemos verificar si la cola ya está llena, es decir, verificar la condición de Overflow . Si la cola no está llena, tendremos que incrementar el valor del índice Rear en 1 y colocar el elemento en la posición de la variable puntero Rear. Cuando lleguemos a insertar el primer elemento en la cola, debemos establecer el valor de Front en 0.
Para eliminar el elemento ( dequeue ) de la cola, debemos verificar si la cola ya está vacía, es decir, verificar la condición de Underflow . Si la cola no está vacía, tendremos que eliminar y devolver el elemento en la posición del puntero Front y luego incrementar el valor del índice Front en 1. Cuando lleguemos a eliminar el último elemento de la cola , tendremos que establecer los valores del índice Front y Rear en -1.

Implementación de Queue en C

Las colas en C se pueden implementar utilizando matrices, listas, estructuras, etc. A continuación, hemos implementado colas utilizando matrices en C.

Ejemplo:

#include stdio.h# define SIZE 100void enqueue();void dequeue();void show();int inp_arr[SIZE];int Rear = - 1;int Front = - 1;main(){    int ch;    while (1)    {        printf("1.Enqueue Operationn");        printf("2.Dequeue Operationn");        printf("3.Display the Queuen");        printf("4.Exitn");        printf("Enter your choice of operations : ");        scanf("%d", ch);        switch (ch)        {            case 1:            enqueue();            break;            case 2:            dequeue();            break;            case 3:            show();            break;            case 4:            exit(0);            default:            printf("Incorrect choice n");        }     } }  void enqueue(){    int insert_item;    if (Rear == SIZE - 1)       printf("Overflow n");    else    {        if (Front == - 1)              Front = 0;        printf("Element to be inserted in the Queuen : ");        scanf("%d", insert_item);        Rear = Rear + 1;        inp_arr[Rear] = insert_item;    }}  void dequeue(){    if (Front == - 1 || Front  Rear)    {        printf("Underflow n");        return ;    }    else    {        printf("Element deleted from the Queue: %dn", inp_arr[Front]);        Front = Front + 1;    }}  void show(){        if (Front == - 1)        printf("Empty Queue n");    else    {        printf("Queue: n");        for (int i = Front; i = Rear; i++)            printf("%d ", inp_arr[i]);        printf("n");    }}

Producción:

1.Enqueue Operation2.Dequeue Operation3.Display the Queue4.ExitEnter your choice of operations : 1Element to be inserted in the Queue: 101.Enqueue Operation2.Dequeue Operation3.Display the Queue4.ExitEnter your choice of operations : 1Element to be inserted in the Queue: 201.Enqueue Operation2.Dequeue Operation3.Display the Queue4.ExitEnter your choice of operations : 3Queue: 10 20 1.Enqueue Operation2.Dequeue Operation3.Display the Queue4.ExitEnter your choice of operations : 2Element deleted from the Queue: 101.Enqueue Operation2.Dequeue Operation3.Display the Queue4.ExitEnter your choice of operations: 3Queue: 20

Implementación de colas mediante pilas

La estructura de datos de pila se puede utilizar para implementar las operaciones de la cola. Necesitaremos dos pilas para implementar una cola que las utilice. Antes de trabajar con los ejemplos siguientes, asegúrese de comprender muy bien el funcionamiento de las pilas.

Se puede implementar una cola utilizando pilas de cualquiera de las siguientes maneras:

Hacer que la operación de poner en cola sea costosa
Hacer que la operación de desencolar sea costosa

Método 1: Hacer que la operación de poner en cola sea costosa

Supongamos dos pilas: S1 y S2 para implementar operaciones de cola utilizando la misma.

Si S1 no está vacío, empuje todos los elementos a la pila 2 (S2)
Para realizar la operación de poner en cola , asumiremos que “x” es el elemento que se va a introducir en la cola. Volveremos a colocar “x” en la pila S1 para que aparezca en la parte superior.
Además, empuja todos los elementos de la pila S2 de nuevo a la pila S1.

Nota: La complejidad temporal de la operación de puesta en cola sería O(n) .

Para realizar la operación de sacar de la cola , necesitaremos sacar un elemento de la pila S1 ya que ahora el primer elemento insertado está en la parte superior en S1 en lugar de estar en la parte inferior.

Nota: La complejidad temporal de la operación de desencolar sería O(1) .

Si analiza las complejidades temporales de las operaciones Enqueue y Dequeue usando Stack, descubrirá que la operación Enqueue es mucho más costosa que la operación Dequeue.

Por lo tanto, como se mencionó anteriormente, hacemos que el primer elemento ingresado o el más antiguo permanezca en la parte superior de la pila S1 para que se elimine cuando se invoca la operación Dequeue.

Método 2: Hacer que la operación de desencolar sea costosa

Supongamos nuevamente dos pilas: S1 y S2 para implementar operaciones de cola utilizando la misma.

Para implementar la operación de poner en cola , insertamos el elemento recién ingresado en la parte superior de la pila S1. Por lo tanto, la complejidad temporal de la operación de poner en cola utilizando pilas se convierte en O(1).
Para implementar la operación de desconexión de la cola , se verifica la condición de desbordamiento de las pilas S1 y S2. Si ambas pilas están vacías, se generará un error.
Si la pila S2 está vacía y S1 no está vacía, entonces todos los elementos de la pila S1 se mueven a la pila S2 y el elemento superior de la pila S2 se extrae y se devuelve fuera de la operación de desencolar.
Por lo tanto, la complejidad temporal de la operación de desencolar utilizando pilas se convierte en O(n) .

Aplicaciones de la estructura de datos de cola

Programación de CPU
Programación de discos
Transferencia de datos asincrónica entre procesadores como File IO, etc.
Algoritmo de búsqueda en amplitud (BFS)

Conclusión

En este artículo, comprendimos el funcionamiento de la estructura de datos de cola y también analizamos la implementación de colas utilizando la estructura de datos de pila.

Referencias

Cola en C
Cola usando pilas