es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • ¿Por qué mi implementación de la estructura de datos de cola con arreglo asignado dinámicamente NO se actualiza en la segunda llamada?

¿Por qué mi implementación de la estructura de datos de cola con arreglo asignado dinámicamente NO se actualiza en la segunda llamada?

17 Jul, 2023 Programación

Estoy aprendiendo Estructuras de Datos según lo requerido por mi universidad. He implementado la Estructura de Datos Cola utilizando un Array Dinámico, pero de alguna manera no funciona. Actualiza el valor en la primera llamada al método enqueue, pero a partir de la segunda llamada en adelante, no hace nada.

Mi CÓDIGO

include <iostream>
define MAXSIZE 8

class Queue
{
private:
    int *arr;
    int front;
    int rear;
    int itemsCount;

public:
    Queue()
    {
        arr = new int[MAXSIZE];
        front = -1;
        rear = -1;
        itemsCount = 0;
    }

~Queue()
{
    delete[] arr;
}

int dequeue()
{
    int x = arr[front];
    front = (front + 1) % MAXSIZE;
    itemsCount--;
    return x;
}

void enqueue(int x)
{
    if (empty())
    {
        front++;
    }

    rear = (rear + 1) % MAXSIZE;
    arr[rear] = x;
    itemsCount++;
}

bool full() const
{
    if (itemsCount == MAXSIZE)
        return true;
    return false;
}

bool empty() const
{
    if (itemsCount == 0)
        return true;
    return false;
}

};

int main(int argc, char const *argv[])
{
    Queue myQ;

myQ.enqueue(11);
myQ.enqueue(22); // Esto no actualiza el array en el índice 1
myQ.enqueue(33);
myQ.enqueue(44);
myQ.enqueue(55);
myQ.enqueue(66);
myQ.enqueue(77);
myQ.enqueue(88);

std::cout << myQ.dequeue() << std::endl;

return 0;

}

PD: Sé que la implementación está incompleta y aún no he manejado todos los casos límite. Eso se debe a que no pude hacer que el caso normal funcione.

PD2: Funciona con un Array Estático. Pero no con uno asignado dinámicamente.

Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Basado en el código proporcionado, parece que la implementación de la Cola de Arreglos Dinámicos es correcta, pero presenta un problema de desbordamiento de memoria.

    El problema está relacionado con la condición que se evalúa en el método full() – aunque asignamos dinámicamente el arreglo, aún estamos usando un valor fijo de MAXSIZE para representar la cantidad máxima de elementos que pueden ser contenidos en la cola. Cuando la cola está llena, el código continúa escribiendo en la ubicación de memoria que está fuera del espacio asignado para el arreglo, causando un comportamiento indefinido que podría llevar a un fallo inesperado.

    Para solucionar este problema, debemos asegurarnos de asignar suficiente memoria para la cola y actualizar el método full() para tomar en cuenta el número actual de elementos asignados.

    Aquí hay una forma de solucionar este problema:

    “`c++
    class Cola {
    private:
    int* arr;
    int frente;
    int trasero;
    int tamanioMaximo;
    int cantidadElementos;

    public:
    Cola(int tamanio = MAXSIZE) {
    arr = new int[tamanio];
    tamanioMaximo = tamanio;
    frente = -1;
    trasero = -1;
    cantidadElementos = 0;
    }

    ~Cola() { delete[] arr; }

    void encolar(int x) {
    if (estaLlena()) {
    std::cout << “¡La cola está llena!\n”;
    return;
    }

    if (estaVacia()) {
  frente = 0;
}

trasero = (trasero + 1) % tamanioMaximo;
arr[trasero] = x;
cantidadElementos++;

    }

    int desencolar() {
    if (estaVacia()) {
    std::cout << “¡La cola está vacía!\n”;
    return -1;
    }

    int x = arr[frente];
frente = (frente + 1) % tamanioMaximo;
cantidadElementos--;
return x;

    }

    bool estaLlena() const {
    return cantidadElementos == tamanioMaximo;
    }

    bool estaVacia() const {
    return cantidadElementos == 0;
    }
    };
    “`

    En esta implementación, hemos agregado un nuevo miembro privado tamanioMaximo para realizar un seguimiento del tamaño real de la memoria asignada. También actualizamos el constructor para recibir un parámetro de tamaño opcional que puede utilizarse para establecer el tamaño de la cola.

    Ambos métodos encolar() y desencolar() ahora verifican si la cola está llena o vacía antes de realizar cualquier operación de inserción o eliminación. El método estaLlena() simplemente verifica si la cantidad de elementos ha alcanzado tamanioMaximo, mientras que el método estaVacia() verifica si la cantidad de elementos es cero.

    Con estos cambios, la Cola de Arreglos Dinámicos debería funcionar incluso cuando se encolan más de MAXSIZE elementos. Por supuesto, aún hay muchos casos límite que no se manejan, pero esto debería ser un buen punto de partida.

Comments are closed.