Principio de implementación de la cola de Java
La palabra "cola" es lo que los británicos llaman "cola". "Techo en línea" en el Reino Unido significa estar en una fila. En la informática, una cola es una estructura de datos, que es un poco como una pila, excepto que el primer elemento de datos insertado en la cola se eliminará primero, y en la pila, el último elemento de datos insertado se elimina primero. La cola funciona como las filas de personas que se encuentran frente al cine: la primera persona que ingrese a los afiliados llegará al jefe del equipo para comprar boletos. La última persona que hace cola puede comprar boletos.
Las colas también se utilizan como herramientas para programadores, como las pilas. También se puede utilizar para simular entornos del mundo real, como simular a las personas que esperan en un banco, aviones que esperan despegar o los paquetes en Internet están esperando ser transmitidos.
En el sistema operativo de la computadora, varias colas están funcionando en silencio. El trabajo de impresión está esperando la impresión en la cola de impresión. Al escribir en el teclado, también hay una cola que almacena la escritura. Del mismo modo, si se aprovecha una llave usando un procesador de textos y la computadora tiene que hacer otra cosa temporalmente, el contenido tocado no se perderá, y esperará en la cola hasta que el procesador de textos tenga tiempo de leerlo. La cola se usa para garantizar que el orden de escribir no se cambie cuando se procesa.
Operaciones básicas de colas
Las dos operaciones básicas de una cola están insertando (insertar) un elemento de datos, es decir, colocar un elemento de datos en la cola de la cola, y el otro está eliminando (eliminando) un elemento de datos, es decir, eliminar el elemento de datos a la cabeza del equipo. Esto es similar a los amantes del cine en cola hasta el final de la línea cuando hacen cola para comprar boletos, luego llegan a la cabeza de la línea y luego dejan la cola.
El nombramiento de métodos para insertar y eliminar elementos de datos en la pila es muy estándar, llamado Push and POP. El método de cola no se ha nombrado estandarizado hasta ahora. "Insertar" se puede llamar put, agregar o enque, mientras que "eliminar" se puede llamar eliminar, obtener o deque. El final del elemento de datos de inserción también se puede llamar de nuevo, cola o final. El jefe del equipo que elimina el elemento de datos también puede llamarse cabezal. Insertar, quitar, delantero y trasero se utilizarán a continuación.
Inserte inserte el valor en la cola de la cola, y la cola de la flecha de la cola se agrega para apuntar al nuevo elemento de datos.
Después de eliminar el elemento de datos, el jefe del equipo es agregado por uno. Por lo general, al implementar una cola, el elemento de datos eliminado se guardará en la memoria, pero no se puede acceder porque el jefe de la cola se ha movido a su siguiente posición.
A diferencia del caso en la pila, los elementos de datos en la cola no siempre comienzan en el subíndice 0 de la matriz. Después de eliminar algunos elementos de datos, el puntero del encabezado apunta a una posición de subíndice más alta.
La operación de vista devuelve el valor del elemento de datos del encabezado, pero no elimina el elemento de datos del equipo.
Si desea eliminar un elemento de datos de una cola vacía o insertar un elemento de datos en una cola completa, la aplicación solicitará un mensaje de error.
Cola de bucle
Cuando se inserta un nuevo elemento de datos en la cola, la flecha trasera al cabezal del equipo se mueve hacia arriba hacia la gran posición del subíndice de la matriz. Al quitar los elementos de datos, la cola del puntero delantero de la cola también se mueve hacia arriba. Este diseño puede ser contrario a la observación directa de las personas, porque cuando las personas hacen cola para boletos de cine, la cola siempre avanza, y después de que la persona frente a ellos compra el boleto y deja la cola, los otros avanzan. Después de eliminar un elemento de datos en la cola en la computadora, también puede hacer avanzar todos los demás elementos de datos, pero esto es muy eficiente. En cambio, mantenemos todos los elementos de datos en la posición de la misma a través del movimiento de los punteros de la cabeza y la cola de la cola.
El problema con este diseño es que el puntero de la cola se moverá rápidamente al final de la matriz. Aunque hay una unidad de elemento de datos vacía al comienzo de la matriz, que es la ubicación del elemento de datos eliminado, pero dado que el puntero de la cola ya no puede moverse hacia atrás, no se pueden insertar nuevos elementos de datos. ¿Qué tengo que hacer?
Tratamiento de conclusión
Para evitar que el problema de la cola esté insatisfecho pero no poder insertar nuevos elementos de datos, los punteros de cabeza y cola se pueden volver al comienzo de la matriz. Esta es la cola de bucle (a veces también llamada "anillo de búfer").
El proceso de envoltura de puntero: inserte suficientes elementos de datos en la cola para hacer que el puntero de la cola apunte al extremo tardío de la matriz. Elimine algunos elementos de datos más en la parte delantera de la matriz. Ahora inserte un nuevo elemento de datos. Verá que el puntero de la cola se invertirá desde el final hasta la posición inicial. Se insertarán nuevos elementos de datos en esta ubicación.
Inserte más elementos de datos. El puntero de la cola se mueve hacia arriba como se esperaba. Tenga en cuenta que después de que el puntero de la cola está rebobinando, ahora está debajo del puntero de la cabeza, lo que invierte la posición inicial. Esto se puede llamar una "secuencia rota": los elementos de datos en la cola están presentes en dos secuencias diferentes en la matriz.
Después de eliminar suficientes elementos de datos, el jefe del equipo también se concluye. En este momento, el puntero de la cola vuelve al estado de posición en el tiempo de ejecución inicial, y el puntero de la cabeza está debajo del puntero de la cola. Los elementos de datos también se restauran a una sola secuencia continua.
Código Java para colas
El programa Queue.java crea una clase de cola, que tiene métodos insert (), remove (), peek (), isEmpty () y size ().
pila de paquetes y cola;
class cola {private int maxSize; privado largo [] quearray; privado int front; privado int trasero; Private int nitems; Public Queue (int s) {maxsize = s; quearray = new Long [maxSize]; Frente = 0; trasero = -1; nitems = 0; } Public void Insert (long j) {if (trasero == maxsize-1) trasero = -1; quearray [++ trasero] = j; nitems ++; } public Long Remete () {long temp = quearray [front ++]; if (front == maxsize) front = 0; nítems--; regresar temp; } public Long Peekfront () {return quearray [front]; } public boolean isEtimty () {return (nitems == 0); } public boolean iffull () {return (nitems == maxSize); } public int size () {return nitems; }}La clase de cola implementada por el programa no solo tiene campos delanteros (cabeza) y trasero (cabeza del equipo), sino también el número de elementos de datos actuales en la cola: nítems.
El requisito previo para la operación del método Insert () es que la cola no está satisfecha. Este método no se muestra en Main (), pero el método Insert () generalmente debe llamarse primero y luego el método ISFULL () debe llamarse después de devolver falso. (Un enfoque más general es agregar un juicio al método Insert () para verificar si la cola está llena. Si se inserta un elemento de datos en la cola completa, se lanzará una excepción).
En términos generales, la operación de inserción es agregar una parte trasera (puntero de cola del equipo) e insertar nuevos datos en la posición señalada por el puntero de la cola. Sin embargo, cuando el puntero trasero apunta a la parte superior de la matriz, es decir, la posición MaxSize-1, debe estar regresada a la parte inferior de la matriz antes de insertar el elemento de datos. La operación de devanado establece la parte trasera en -1, por lo que cuando se agrega la parte trasera 1, es igual a 0, que es el valor del subíndice en la parte inferior de la matriz, y finalmente se agrega NITEM.
El requisito previo para la operación del método remove () es que la cola no está vacía. Antes de llamar a este método, debe llamar al método isEmpty () para asegurarse de que la cola no esté vacía, o agregar este mecanismo de verificación de errores al método remove ().
La operación de eliminación siempre obtiene el valor del elemento de datos del encabezado del puntero delantero, y luego agrega el delantero. Sin embargo, si lo hace que el valor del frente excede la parte superior de la matriz, el frente debe volver a la posición donde el subíndice de la matriz es 0. Mientras realiza esta prueba, el valor de retorno se almacena temporalmente. Finalmente, Nitem se reduce por uno.
El método Peek () es simple y fácil de entender: devuelve el valor del elemento de datos señalado por el puntero delantero. Algunas implementaciones de la cola también permiten ver el valor del elemento de datos de extremo de cola; Por ejemplo, estos métodos se pueden llamar Peekfront (), PeekRear () o simplemente delantero () y trasero ().
La implementación de los métodos isEtimty (), isfull () y size () se basa en el campo NITEMS, que devuelve si NITEMS es igual a 0, ya sea igual a MaxSize o devuelve su propio valor.
La inclusión de los campos de conteo de elementos de datos nítidos en la clase de cola agregará un poco de operación adicional a los métodos insert () y eliminar (), porque los métodos insert () y eliminar () deben aumentar y disminuir el valor de esta variable respectivamente. Puede que no sea una sobrecarga adicional, pero si se ocupa de muchas operaciones de insertar y eliminar, esto puede afectar el rendimiento.
Porque, algunas implementaciones de la cola no usan los campos del contado de elementos de datos, pero usan delante y trasero para calcular si la cola está vacía o completa y la cantidad de elementos de datos. Si hace esto, las rutinas isEmpty (), iffull () y size () serán bastante complicadas porque, como se mencionó anteriormente, la secuencia de elementos de datos se colapsan en dos segmentos o un segmento continuo.
Y surgió un problema extraño. Cuando la cola está llena, los punteros delanteros y traseros toman una determinada posición, pero cuando la cola está vacía, también puede aparecer la misma relación de posición. Entonces, al mismo tiempo, la cola puede parecer estar llena o vacía. La solución a este problema es: hacer que la capacidad de la matriz sea una más que el número máximo de elementos de datos de cola.
Gracias por leer, espero que pueda ayudarte. ¡Gracias por su apoyo para este sitio!