Tecnología

Cómo implementar una clase de cola con prioridad usando un vector

Escrito por greg livingston | Traducido por beatriz sánchez
Cómo implementar una clase de cola con prioridad usando un vector

Los objetos se sacan de la parte frontal de la cola uno por uno, como en una línea de espera.

Digital Vision./Photodisc/Getty Images

Una cola almacena los datos en una secuencia y contiene dos funciones: sacar y meter. Meter coloca un elemento al final de la cola y sacar saca un elemento de la parte frontal y lo devuelve. Una cola de prioridad se comporta de forma parecida, con una diferencia: meter añade los elementos a la cola en un orden determinado. Los vectores no son ideales para una cola de prioridad. Les falta flexibilidad, haciendo que sea complicado ordenar la cola. Pero son útiles para aprender el concepto.

Nivel de dificultad:
Moderadamente fácil

Otras personas están leyendo

Instrucciones

  1. 1

    Elige el tipo de datos que tendrá tu cola de prioridad. Si es la primera vez que vas a escribir una cola de prioridad, elige algo sencillo, como un entero.

  2. 2

    Crea un vector que sirva como cola. Si tu tipo de datos es un entero, y quieres almacenar 10 elementos, tu vector se creará usando código como este: int[] arr = new int[10]; Ten en cuenta que 0 es el primer índice del vector. Para acceder al primer índice del vector, harás referencia a él como arr[0], y arr[9] accedería al último índice del vector. En este caso, arr[10] daría un error.

  3. 3

    Determina la función de ordenación. La usarás más tarde para meter los elementos en el orden correcto. Esta función toma dos entradas, y luego las compara. Si la primera entrada tiene un valor mayor, la función devuelve 1. Si tienen el mismo valor, devuelve 0. Si la primera entrada tiene un valor menor, devuelve -1. Si es la primera vez que escribes una función de ordenación, y tu tipo de datos escogido es el vector, deberías empezar con un orden numérico, en el que los números menores tienen un valor menor. Ordenando el valor numérico, el código será: if (first > second) return 1; if (first == second) return 0; if (first < second) return -1; Esto también funciona para otros tipos de datos numéricos, como los flotantes y los de doble precisión. Si usas cadenas, podrías ordenar alfabéticamente.

  4. 4

    Inicia la función de meter. Esto toma una entrada, el elemento que hay que meter en la cola, y no saca nada. En Java, si tu tipo de datos es entero, tu código tendría este aspecto: public void push(int in) Tu código tendrá un aspecto parecido en la mayoría de los lenguajes de programación, incluyendo C y C++. "Void" significa que la función no saca nada.

  5. 5

    Crea un vector del mismo tamaño que el vector que usas para la cola. Si tu vector actual puede almacenar 10 enteros, crearás un vector así: int[] secondArray = new int[10]; Este segundo vector se convertirá después en tu cola. Si la última entrada en tu vector está llena, esto significa que has usado todas las entradas del vector, y deberías crear un vector que tenga más entradas.

  6. 6

    Compara la entrada de cada elemento en tu vector, empezando por el primero, usando la función de ordenación. Coloca siempre como primer elemento en la función del ordenación la entrada a meter. Para comparar la entrada a meter y el primer elemento del vector, tu código sería: sort(in, arr[0]); Aquí, "in" es el nombre de la variable de entrada del paso 4. Si esto devuelve -1, coloca la entrada de meter en el segundo vector: secondArray[0] = in; De lo contrario, copia el elemento del primer al segundo vector: secondArray[0] = arr[0]; Después comparar la entrada a meter con el siguiente elemento del primer vector: sort(in, arr[1]); Sigue haciendo esto hasta que la entrada a meter se inserte en el segundo vector o hasta que no haya más elementos en el primer vector. En el último caso, coloca la entrada a meter como el siguiente elemento del segundo vector.

  7. 7

    Copia el resto de los elementos del primer vector en el segundo. Ahora que la entrada a meter ha sido colocada en el segundo vector, no es necesaria la función de ordenación. De ahora en adelante, usa el segundo vector en lugar del primero. El primer vector está ahora desactualizado. Con esto, la función meter está completa.

  8. 8

    Escribe la función para sacar. Esto no toma entradas, pero hay un elemento como salida de la cola. Si tu tipo de datos es el entero, tu código sería: public int pop() La segunda palabra, "int", significa que esta función sacará un entero.

  9. 9

    Crea un segundo vector del mismo tamaño que el actual. Después, copia el segundo elemento del primer vector en la primera entrada del segundo vector, el tercer elemento en la segunda entrada del segundo vector, y así sucesivamente, hasta que ya no hayan más entradas. No copies el primer elemento del primer vector. Si tu vector tiene 4 elementos, tu código sería: secondArray[0] = arr[1]; secondArray[1] = arr[2]; secondArray[2] = arr[3]; Recuerda que el primer índice de un vector es 0. Esto significa que secondArray[0] es el primer elemento de secondArray, y que arr[1] es el segundo elemento de arr.

  10. 10

    Devuelve el primer elemento del primer vector. Tu código sería: return arr[0]; Como con la función de meter, el segundo vector es ahora tu cola. La función de sacar está ahora terminada.

Más galerías de fotos

comentarios

Filtrar por:
  • Mostrar todos
  • Artículos
  • Galerías de fotos
  • Videos
Ordenar:
  • Más relevante
  • Más popular
  • Más reciente

No se encuentran artículos disponibles

No se encuentran slideshows disponibles

No se encuentran videos disponibles

Copyright © 1999-2014 Demand Media, Inc. Acerca de

El uso de este sitio constituye la aceptación de los términos y política de privacidad de eHow. Ad Choices es-US

Demand Media