Cola circular en C: ¿Cómo implementar?
Publicado: 2020-10-23Los datos se organizan en una cola circular en un patrón circular donde el último elemento está conectado al primer elemento. A diferencia de la cola lineal donde las tareas se ejecutan en FIFO (primero en entrar, primero en salir), el orden de la cola circular de ejecución de tareas puede cambiar. Las operaciones de inserción y eliminación se pueden realizar en cualquier posición.
La cola circular es más eficiente que la cola lineal. En la representación gráfica de una cola circular, se puede observar que las posiciones delantera y trasera están conectadas, formando un círculo en el que las operaciones siempre se ejecutan en FIFO. Cada nuevo elemento se agrega en la parte trasera y se elimina de la parte delantera. Una cola circular tiene una mejor utilización y tiene una complejidad de tiempo de O(1).
Fuente
Tabla de contenido
Aplicaciones de una cola circular
- Programación de la CPU: las colas circulares utilizan los espacios de memoria vacíos que se encuentran en las colas lineales.
- Sistema de tráfico: en el sistema de tráfico, con la ayuda de las colas circulares, los semáforos funcionan en el intervalo de tiempo establecido.
- Gestión de memoria: Los sistemas operativos frecuentemente mantienen una línea de procesos que están preparados para ejecutar o que están esperando que ocurra un evento específico.
Aprender: Programa C para la clasificación de burbujas: Clasificación de burbujas en C
Código de muestra con explicación
Línea 1: // (1) Preprocesadores
Línea 2: // Establecer el límite de cola en 5 elementos
Línea 3: #include<stdio.h>
Línea 4: #define LIM 5
Línea 5: // (2) Declaraciones de tipo de datos de cola
Línea 6: // los datos contienen datos; delPos, posición a borrar; longitud, n. de
Línea 7: // elementos actualmente presentes en la cola
Línea 8: typedef struct cola {
Línea 9: int data[LIM], delPos, longitud;
Línea 10: } Q;
Línea 11: // (3) Declaraciones Globales
Línea 12: // Funciones y variable global q del tipo de cola de estructura
Línea 13: Qq;
Línea 14: void ui_Q_Ops(), insertQel(), deleteQel(), displayQels(), initQ();
Línea 15: // (4) Llama a la función UI después de la inicialización
Línea 16: int main()
Línea 17: {
Línea 18: initQ();
Línea 19: ui_Q_Ops();
Línea 20: devuelve 0;
Línea 21: }
Línea 22: // (5) Inicializar cola
Línea 23: void initQ()
Línea 24: {
Línea 25: q.longitud = 0;
Línea 26: q.delPos = 0;
Línea 27: }
Línea 28: // (6) Menu Driven Loop llama a las funciones correctas
Línea 29: anular ui_Q_Ops()
Línea 30: {
Línea 31: elección int=0;
Línea 32: entrada de caracteres [16];
Línea 33: while(elección!=4){
Línea 34: printf(” \n ———————-\n “);
Línea 35: printf(” 1. Insertar en la cola \n “);
Línea 36: printf(" 2. Eliminar de la cola \n ");
Línea 37: printf(” 3. Mostrar elementos de la cola \n “);
Línea 38: printf(” 4. Salir del programa \n “);
Línea 39: printf(” Ingrese la opción: “);
Línea 40: if (fgets(input, 15, stdin) != NULL){
Línea 41: if (sscanf(input, “%d”, &choice) == 1){
Línea 42: switch(elección){
Línea 43: caso 1: insertQel();
Línea 44: descanso;
Línea 45: caso 2: deleteQel();
Línea 46: descanso;
Línea 47: caso 3: displayQels();
Línea 48: descanso;
Línea 49: caso 4: devolución;
Línea 50: predeterminado: printf(“Opción no válida\n “);
Línea 51: continuar;
Línea 52: }
Línea 53: } más
Línea 54: printf(” Opción no válida \n “);
Línea 55: }
Línea 56: }
Línea 57: }
Línea 58: // (7) Insertar en cola
Línea 59: // Si la longitud es la misma que el límite MAX, la cola está llena; de lo contrario, inserte
Línea 60: // logrado circularmente con suma de longitud y módulo delPos por MAX Limit
Línea 61: // y longitud de incremento
Línea 62: anular insertQel()
Línea 63: {
Línea 64: int el, inspos;
Línea 65: entrada de caracteres [16];
Línea 66: if (q.longitud == LIM){
Línea 67: printf(” La cola está llena \n “);
Línea 68: retorno;
Línea 69: }
Línea 70: inspos = (q.delPos + q.longitud) % LIM;
Línea 71: printf(” Ingrese el elemento a insertar: “);
Línea 72: if (fgets(input, 15, stdin) != NULL){
Línea 73: if (sscanf(input, “%d”, &el)){
Línea 74: q.data[inspos] = el;
Línea 75: q.longitud++;
Línea 76: } más
Línea 77: printf(” Entrada inválida \n “);
Línea 78: }
Línea 79: }
Línea 80: // (8) Eliminar de la cola
Línea 81: // Si Longitud es 0, la cola está vacía; de lo contrario, elimínelo en delPos
Línea 82: // y longitud decreciente
Línea 83: anular eliminarQel()
Línea 84: {
Línea 85: if (q.longitud == 0){
Línea 86: printf(” La cola está vacía \n “);
Línea 87: } más {
Línea 88: printf(” Elemento eliminado %d \n “, q.data[q.delPos]);
Línea 89: q.delPos = (q.delPos + 1) % LIM;
Línea 90: q.longitud–;
Línea 91: }
Línea 92: }
Línea 93: // (9) Mostrar elementos de cola
Línea 94: // Muestra de manera circular ejecutando un bucle que comienza en delPos
Línea 95: // y agregando iterador y módulo por Max Limit
Línea 96: anular displayQels()
Línea 97: {
Línea 98: int yo;
Línea 99: if (q.longitud == 0){
Línea 100: printf(” La cola está vacía \n “);
Línea 101: } más {
Línea 102: printf(” Los elementos de la cola son: “);
Línea 103: for(i = 0; i < q.longitud; i++){
Línea 104: printf(“%d “, q.data[(q.delPos+i)%LIM]);
Línea 105: }
Línea 106: imprimirf(” \n “);
Línea 107: }
Línea 108: }
Línea 109:
Salidas:
Operaciones en una cola circular
1. insertQel() – Insertar un elemento en la cola circular
En una cola circular, la función enQueue() se usa para insertar un elemento en la cola circular. En una cola circular, la nueva función siempre se inserta en la posición trasera. La función enQueue() toma un valor entero como parámetro y lo inserta en la cola circular. Los siguientes pasos se implementan para insertar un elemento en la cola circular:
Paso 1: compruebe si la longitud es la misma que la del límite MAX. Si es verdadero, significa que la cola está LLENA. Si está LLENO, muestra "La cola está llena" y finaliza la función.
Paso 2: si NO está LLENO, inserte el valor que se logra circularmente con la longitud de la suma y el módulo delPos por el límite MAX y la longitud del incremento
2. deleteQel() – Eliminar un elemento de la cola circular
En una cola circular, deQueue() es una función que se usa para eliminar un elemento de la cola circular. En una cola circular, el elemento siempre se elimina desde la posición frontal. La función deQueue() no toma ningún valor como parámetro. Los siguientes pasos se implementan para eliminar un elemento de la cola circular...
Paso 1: compruebe si la cola está VACÍA. (delantero == -1 && trasero == -1)
Paso 2: si está VACÍO, muestra "La cola está vacía" y finaliza la función.
Paso 3: si NO ESTÁ VACÍO, muestra los elementos eliminados según las posiciones. Después de agregar cada elemento, avance al siguiente límite de cola de modulación de posición.
3. displayQels(): muestra los elementos de cola que están presentes en la cola circular. Los siguientes pasos se implementan para mostrar los elementos de una cola circular:
Paso 1: compruebe si la cola está VACÍA.
Paso 2: si la longitud es 0, está VACÍO, luego muestra "La cola está vacía" y finaliza la función.
Paso 3: si NO ESTÁ VACÍO, defina una variable entera 'i.'
Paso 4: establezca i en 0.
Paso 5: nuevamente, muestre los elementos según la posición e incremente el valor en uno (i ++). Repita lo mismo hasta que 'i <q.length' se convierta en FALSO.
Circular Queue también se puede implementar utilizando la lista enlazada. Los siguientes son los algoritmos:
- Algoritmo para poner en cola:
if (FRONT == NULL) // Insertar en una cola vacía
DELANTERO = TRASERO = nuevoNodo
terminara si
demás
REAR -> next = newNode // Insertando después del último elemento
TRASERO = nuevoNodo
terminar más
TRASERO -> siguiente = DELANTERO
Fin de poner en cola
- Algoritmo para Dequeue:
if(FRONT == NULL) // Condición para subdesbordamiento
Imprimir "desbordamiento de la cola"
terminar Dequeue
terminara si
else if(FRONT == REAR) // La cola contiene solo un nodo
temp = FRENTE -> datos
gratis (temporal)
FRENTE = FRENTE -> siguiente
TRASERO -> siguiente = DELANTERO
terminara si
else if (FRONT == N – 1) // Si FRONT es el último nodo
front = 0 // Hacer FRONT como el primer nodo
terminara si
terminar Dequeue
Lea también: Python Vs C: comparación completa lado a lado
Conclusión
Las estructuras de datos y los algoritmos son de gran importancia y no solo en la programación en C sino también en otros lenguajes. Su valor no tiene precedentes y, para temas de tanta importancia, es mejor invertir en cursos diseñados y asesorados por expertos, que proporcionarán un excelente valor agregado a su cartera. upGrad ofrece una amplia gama de cursos llenos de energía que no solo mejoran sus habilidades, sino que construyen pilares sólidos de conceptos básicos.
Está diseñado por el IIIT-B de gran reputación, donde no solo brindan contenido de primera calidad, sino que también lo hacen parte de una red sólida donde se conectará con personas que están evolucionando en la misma carrera profesional, así como los expertos de la industria que resolver tus dudas y apoyarte en todo momento.
Conocer su mentalidad y proceso de pensamiento te ayudaría. Y una de las cosas únicas que obtiene en upGrad es que puede optar por las opciones de EMI y cuidar sus bolsillos.
Esperamos que tenga una excelente oportunidad de aprendizaje en la ejecución de estos proyectos C. Si está interesado en obtener más información y necesita la tutoría de expertos de la industria, consulte el Diploma PG de upGrad & IIIT Banglore en desarrollo de software de pila completa .