Algoritmos de Estructuras de Datos: Operaciones con Colas Circulares y Pilas

Planteamiento del Problema

COLA es un arreglo con capacidad para NC enteros, y PILA es un arreglo con capacidad para NP enteros. En el arreglo COLA reside una cola circular con índices FRENTE y FINAL cuyos valores no conocemos (es decir, no sabemos si la cola está vacía, media o llena). En el arreglo PILA reside una pila con índice TOPE, cuyo valor tampoco conocemos (es decir, no sabemos si la pila está vacía, media o llena).

Escribe el pseudocódigo de un algoritmo que realice las siguientes acciones:

• a) Extraiga uno a uno los elementos que pudiesen existir en esa cola y meta en la pila solo aquellos que sean de valor par. Este proceso se debe detener en cuanto la cola quede vacía o en cuanto la pila se llene.
• b) Terminado ese proceso, debe sacar uno a uno los elementos desde la pila para agregarlos a la cola. Este proceso se debe detener en cuanto la cola se llene o en cuanto la pila quede vacía.

En tu algoritmo, usa los mismos nombres de variables indicados en el planteamiento (es decir: COLA, FRENTE, FINAL, NC, PILA, NP y TOPE).

Solución del Algoritmo

Parte a) Extracción de elementos de la Cola hacia la Pila

Para extraer datos, la cola debe tener datos, es decir, FRENTE debe ser mayor que cero. Pero, de acuerdo al planteamiento, esta acción debe detenerse si la cola queda vacía (obvio) o si la pila queda llena (¿para qué seguir extrayendo datos desde la cola si no se van a poder meter en la pila?).

Mientras FRENTE > 0 y TOPE < NP repita
    FFRENTE ← 1 + resto de (FRENTE - 1) / NC
    Dato ← COLA(FFRENTE)
    TOPE ← TOPE + 1
    PILA(TOPE) ← Dato
    FRENTE ← FRENTE + 1
    Si FRENTE > FINAL entonces
        FRENTE ← 0
        FINAL ← 0
    Fin Si
Fin Mientras

Parte b) Retorno de elementos desde la Pila hacia la Cola

Para sacar datos desde la pila, esta debe tener datos, es decir, TOPE debe ser mayor que cero. Pero, de acuerdo al planteamiento, esta acción debe detenerse si la pila queda vacía (obvio) o si la cola queda llena (¿para qué seguir sacando datos desde la pila si no se van a poder agregar a la cola?).

Mientras TOPE > 0 y (FINAL - FRENTE + 1) < NC repita
    Dato ← PILA(TOPE)
    TOPE ← TOPE - 1
    FINAL ← FINAL + 1
    FFINAL ← 1 + resto de (FINAL - 1) / NC
    COLA(FFINAL) ← Dato
    Si FRENTE es 0 entonces
        FRENTE ← 1
    Fin Si
Fin Mientras