Hemos estado expuestos a varias estructuras de datos antes, incluidas matrices, listas vinculadas, tablas hash y árboles rojos y negros (árboles de consulta binaria). Hoy, veamos otra estructura de datos: pila.
¿Qué es una pila? Veamos primero un ejemplo: una pila es equivalente a un barril de madera muy estrecho. Cuando ponemos las cosas en el barril de madera y sacamos las cosas, encontraremos que lo que ponemos en la parte inferior al principio, y lo primero que sacamos fue el que acabamos de poner. Por lo tanto, la pila es un contenedor que primero entró y sale (FirstInlasteut, o más tarde y primero en salir). Tiene solo una boca, coloca elementos en esta boca y también saca elementos en esta boca. Luego aprendamos la pila en JDK a continuación.
1. Introducción y uso básico de Vector & Stack
Primero veamos la definición de JDK:
Public Class Stack <E> extiende Vector <E> {De lo anterior, podemos ver que la pila se hereda del vector, por lo que también debemos tener una cierta comprensión del vector.
Vector: matrices dinámicas seguras de hilo
Pila: Hereding Vector, una pila segura de hilo implementada basada en matrices dinámicas;
1. Características del vector y la pila:
Vector y ArrayList son básicamente los mismos. La diferencia es que el vector es seguro de subprocesos y agregará la palabra clave sincronizada antes de los posibles métodos seguros de hilo;
Vector: velocidad de acceso aleatorio rápida, mala inserción y rendimiento de eliminación (características de la matriz); admite elementos nulos; tiene orden; se pueden repetir elementos; Safe de hilo;
Pila: After-in, First-Out, implementa algunos métodos básicos de operaciones de pila (de hecho, no solo es después, primero, porque heredado de Vector, puede haber muchas operaciones, y en cierto sentido, no es una pila);
2. Estructura de vector y pila:
Clase vectorial
Básicamente es lo mismo que ArrayList, y las diferencias principales restantes son las siguientes:
1. El vector es seguro de hilo
2. El crecimiento de la lista de matrices es inconsistente con el crecimiento vectorial
Otros, si los métodos de construcción son inconsistentes, el vector puede inicializar la capacidad de incremento a través del método de construcción, y existen otros métodos, como el método indexOf. Vector admite búsqueda y búsqueda desde la ubicación especificada; Además, Vector también tiene algunos métodos redundantes con funciones duplicadas, como el método AddElement y SetElementat. La razón de esto se debe a razones históricas. Por ejemplo, el método de adición se queda atrás antes. Cuando se introdujo el marco de la colección, Vector se unió a la familia Collection y cambió para implementar la interfaz de la lista. Se deben implementar algunos métodos definidos en la interfaz de la lista. Sin embargo, por razones de compatibilidad, los métodos antiguos no se pueden eliminar, por lo que aparecieron algunos métodos antiguos con redundancia. Ahora ha sido reemplazado por ArrayList y básicamente se usa raramente, así que solo comprende.
Clase de pila
Se realiza el funcionamiento básico de la pila. El método es el siguiente:
pila pública ();
Crea una pila vacía
público sincronizado e peek ();
Devuelve el valor en la parte superior de la pila;
Public E Push (E item);
Operación de pila;
público sincronizado e pop ();
Operación de apilamiento;
público booleano vacío ();
Determinar si la pila está vacía;
Public Syncronized int. (Objeto O);
Devuelve la posición del objeto en la pila;
Para la pila anterior, básicamente solo usaremos el método anterior con frecuencia. Aunque hereda el vector y tiene muchos métodos, básicamente no se usará, pero se trata como una pila.
3. Uso básico
Algunos métodos en Vector se utilizan de la siguiente manera. Además, el método transversal del vector es el mismo que el de ArrayList. Puede usar foreach, iterator y para traversal de bucle;
import java.util.arrays; import java.util.iterator; import java.util.list; import java.util.listiterator; import java.util.vector; public class test {public static void main (string [] string) {vector <integer> vector = nuevo vector <intregero> (); para (int i = 0; i <10; i ++) {vector.add (i); } // imprime sistema.out.println (vector.toString ()); // size () system.out.println (vector.size ()); // contiene system.out.println (vector.contains (2)); // iterador iterador <integer> iterator = vector.iterator (); while (iterator.hasnext ()) {System.out.print (iterator.next () + ""); } // objeto toArray [] objarr = vector.toarray (); System.out.println ("/nobJarr:" + arrays.aslist (objarr)); Entero [] intarr = vector.toarray (nuevo entero [vector.size ()]); System.out.println ("intarr:" + arrays.aslist (intarr)); // Agregar vector.add (5); // eliminar vector.remove (5); System.out.println (vector); // contiene todo sistema.out.println (vector.containsall (arrays.aslist (5,6))); // addall vector.addall (arrays.aslist (555,666)); System.out.println (vector); // removeall vector.removeall (arrays.aslist (555,666)); System.out.println (vector); // Addall Method Vector.addall (5, Arrays.aslist (666,666, 6)); System.out.println (vector); // Get Method System.out.println (vector.get (5)); // establecer el método vector.set (5, 55); System.out.println (vector.get (5)); // Agregar método vector.add (0, 555); System.out.println (vector); // eliminar el método vector.remove (0); System.out.println (vector); // IndexOf Method System.out.println (vector.indexof (6)); // LastIndexof Method System.out.println (vector.lastindexof (6)); // Método ListIterator Listiterator <Steger> listIterator = vector.listiterator (); System.out.println (listIterator.Hasprevious ()); // listIterator (índice) Método listIterator <integer> ilistiterator = vector.listiterator (5); System.out.println (ilistiterator.previous ()); // Método Sublist System.out.println (Vector.Sublist (5, 7)); // claro vector.clear (); System.out.println (vector); }}Algunos métodos en la pila se utilizan de la siguiente manera. Debido a que la pila hereda el vector, la pila también puede usar métodos que Vector puede usar. Los siguientes enumeran algunos ejemplos de los métodos únicos de Stack. Es muy simple, que son algunas operaciones básicas de la pila. Además de varios métodos de recorrido de Vector, la pila también tiene sus propios métodos de recorrido únicos (utilizando el método vacío y el método POP para lograr el recorrido de la parte superior a la parte inferior de la pila):
import java.util.stack; prueba de clase pública {public static void main (string [] args) {stack <integer> stack = new Stack <Integer> (); para (int i = 0; i <10; i ++) {stack.add (i); } System.out.println (pila); System.out.println (stack.peek ()); stack.push (555); System.out.println (pila); System.out.println (stack.pop ()); System.out.println (pila); System.out.println (stack.empty ()); System.out.println (stack.search (6)); System.out.println ("pila traversal:"); while (! stack.empty ()) {system.out.print (stack.pop () + ""); }}}Subsección:
Vector es seguro de hilo, pero tiene un bajo rendimiento. En general, se usa ArrayList a menos que haya requisitos especiales;
Si planea usar la pila como pila, debe seguir honesta y estrictamente las diversas operaciones de la pila. De lo contrario, sería significativo usar pila, y sería mejor usar Vector;
2. Estructura de vector y Stacke y almacenamiento subyacente
Public Class Vector <E> extiende la lista de implementos de Abstract <E> Lista de implementos <E>, RandomAccess, Clonable, Java.io.Serializable
Vector es una clase de implementación de la lista. De hecho, Vector también es un contenedor de lista basado en la implementación de la matriz. Sus funciones y código de implementación son básicamente las mismas que ArrayList. Entonces, ¿qué es diferente? Una es que cuando la matriz se expande, el vector es *2 y la ArrayList es *1.5+1; La otra es que el vector es seguro de hilo, mientras que ArrayList no lo es. El enfoque seguro de hilo de Vector es agregar una palabra clave sincronizada a cada método para garantizarla. Pero aquí, Vector ya no es oficialmente (reconocido por todos) y no se recomienda. Se debe oficialmente a que su método de seguridad de subprocesos es bloquear todo el método, lo que conduce a una baja eficiencia. Entonces, ¿hay una mejor solución? De hecho, no se puede decir que hay uno, pero realmente hay uno, colección.synchronizedList ()
Dado que la pila está heredada y se basa en Vector, echemos un vistazo a algunas definiciones y códigos fuente de métodos de Vector:
// La capa subyacente usa una matriz para almacenar el objeto protegido de datos [] elementData; // El número de elementos protegidos int elementCount; // Personalizar la expansión del contenedor y el tamaño de incremento protegido con capacidad de capacidad; Public Vector (int InitialCapacity, Int CapacityIncrement) {super (); // Compruebe de límites de salida si (InicialCapacity <0) arroja nueva IllegalArgumentException ("Capacidad ilegal:" + InicialCapacity); // Inicializar la matriz this.ElementData = New Object [InitialCapacity]; this.capacityIncrement = CapacityIncrement; } // Use el método de bloqueo de palabras clave sincronizado para asegurarse de que solo un hilo pueda manipular el método al mismo tiempo, público booleano sincronizado public add (e e) {modcount ++; // verificación de ampliación EnsurecapacityHelper (elementCount + 1); elementData [elementCount ++] = e; devolver verdadero; } private void asurecapacityHelper (int mincapacity) {// número actual de elementos int // es necesario expandir la capacidad if (mincapacity> OldCapacity) {object [] oldData = elementData; // Si la expansión del contenedor está personalizada, expanda la capacidad de acuerdo con CapacityIncrement, de lo contrario expandir la capacidad en dos veces (*2) int NewCapacity = (CapacityIncrement> 0)? (OldCapacity + CapacityIncrement): (OldCapacity * 2); if (newCapacity <mincapacity) {newCapacity = mincapacity; } // matriz copy elementData = arrays.copyOf (elementData, newCapacity); }}Vector simplemente vea esto. Si no se llama al otro método de pila, no se analizará. Si no comprende, puede verificar el análisis del código fuente de ArrayList.
3. Análisis de los métodos principales
1.peek () - Obtenga el objeto en la parte superior de la pila
/ ** * Obtenga el objeto en la parte superior de la pila, pero no elimine */ public Synchronized E Peek () {// El número actual de elementos contenedores int Len = size (); // Si no hay elemento, arroje una excepción directamente si (Len == 0) tire nuevo vacíostacKexception (); // Llame al método Elementat para recuperar el último elemento de la matriz (el último elemento está en la parte superior de la pila) Elemento de retorno (len - 1); } / *** Obtenga el elemento en esta posición de acuerdo con el índice del índice, este método está en vector* / public sincronizado e elementat (int index) {// sale de los límites if (index> = elementCount) {tire nuevo arrayintexoUtofBoundseException (index + "> =" + elementCount); } // Obtener el elemento return (e) elementData [índice]; }2.pop (): establezca la pila (fuera de la pila), obtenga el objeto en la parte superior de la pila y elimine el objeto del contenedor
/ *** Bumble la pila, obtenga y elimine el objeto en la parte superior de la pila*/ public Synchronized e pop () {// Grabe el objeto en la parte superior de la pila e obj; // El número actual de elementos contenedores int len = size (); // obtener el objeto en la parte superior de la pila obj a través del método peek () obj = peek (); // Llame al método RemoLElement para eliminar el objeto en la parte superior de la pila RemoLeLementat (len - 1); // Vuelve al objeto en la parte superior de la pila return OBJ; } / *** Elimine el elemento de acuerdo con el índice Índice* / public sincronizado void remoidElementat (int index) {modcount ++; // Límites de salida if (index> = elementCount) {Throw New ArrayInDexOutofBoundSexception (index + "> =" + elementCount); } else if (índice <0) {tire nuevo ArrayInDexuToFboundSexception (índice); } // Calcule el número de elementos de matriz que se moverán int j = elementCount - índice - 1; if (j> 0) {// Mueve la matriz, elimine una en el medio, así que mueva el elemento posterior hacia adelante (mover aquí sobrescribe directamente el elemento de posición de índice, que es equivalente a la eliminación) del sistema. ArrayCopy (ElementData, índice + 1, elementData, índice, j); } // menos 1 ElementCount--; // Establezca el último elemento del contenedor en vacío (porque se eliminó un elemento, y los elementos detrás del índice se movieron hacia adelante, por lo que el último fue inútil) ElementData [elementCount] = null; / * para que GC haga su trabajo */}3.push (elemento e): presione (en la pila), agregue el objeto al contenedor y devuélvelo
/ ** * Agregue el objeto al contenedor y return */ public e push (e elemento) {// llame a addelement a addElement (elemento); // devuelve el elemento de retorno del elemento; } /*** Agregue el elemento al contenedor. Este método está en Vector*/ public sincronizado Void Addelement (E obj) {modcount ++; // verificación de ampliación EnsurecapacityHelper (elementCount + 1); // colocar el objeto en la matriz, el número de elementos +1 elementData [elementCount ++] = obj; }4.Search (objeto O): devuelve la posición del objeto en el contenedor, la parte superior de la pila es 1
/ ** * Devuelve la posición del objeto en el contenedor, la parte superior de la pila es 1 */ public sincronizado int. // Debido a que la parte superior de la pila cuenta 1, debe usar size () - i para calcular si (i> = 0) {return size () - i; } return -1; }5.empty () - ¿Está vacío el contenedor?
/ *** Verifique si el contenedor está vacío*/ public boolean vacía () {return size () == 0; }Subsección:
En este punto, se analiza el método de pila. Dado que la pila se basa en última instancia en matrices, todavía es fácil de entender (porque se basa en ArrayList).
Aunque se ha analizado el código fuente de la pila en JDK, es necesario discutirlo aquí. No sé si descubrí que la pila aquí es muy extraña.
(1) ¿Por qué se implementa Stack en función de las matrices?
Todos conocemos las características de las matrices: son convenientes para consultar según los subíndices (acceso aleatorio), pero la memoria es fija y la eficiencia de expansión de la capacidad es baja. Es fácil pensar en lo más adecuado para que Stack use listas vinculadas.
(2) ¿Por qué la pila hereda el vector?
La herencia significa que la pila hereda el método vectorial, lo que hace que la pila se sienta un poco inapropiada, tanto una lista como una pila. ¿Cuál debería ser un enfoque razonable si tiene que heredar el vector?
La única explicación es que la pila fue creada por JDK1.0. En ese momento, los contenedores en JDK no tenían solo vectores, como ArrayList, LinkedList, etc., y dado que ya tienen vector y pueden implementar funciones de pila, entonces hágalo. . . Dado que es ideal para implementar pila con listas vinculadas, intentémosla:
import java.util.linkedlist; clase pública LinkedStack <E> {private LinkedList <E> Linked; public LinkedStack () {this.linked = new LinkedList <E> (); } public e push (e item) {this.linked .addfirst (item); artículo de devolución; } public e pop () {if (this.linked.isEmpty ()) {return null; } return this.linked.removeFirst (); } public e peek () {if (this.linked.isEmpty ()) {return null; } return this.linked.getFirst (); } public int Search (e item) {int i = this.linked.indexof (item); regresar i + 1; } public boolean vacía () {return this.linked.isEmpty (); }}La pila implementada por LinkedList se usa aquí. Recuerde, como se menciona en LinkedList, LinkedList implementa la interfaz Deque para que pueda usarse como una pila (primero dentro y fuera) y una cola (primero dentro y fuera).
4. La diferencia entre Vector y ArrayList
Hay tres clases de implementación en la interfaz de la lista, a saber, ArrayList, Vector y LinkedList. La lista se utiliza para almacenar múltiples elementos, puede mantener el orden de los elementos y permite la repetición de elementos.
Las diferencias relevantes entre las tres clases de implementación específicas son las siguientes:
1. ArrayList es la clase de implementación de listas más utilizada, implementada internamente a través de matrices, lo que permite un acceso aleatorio rápido a elementos. La desventaja de las matrices es que no puede haber espaciados entre cada elemento. Cuando no se cumple el tamaño de la matriz, la capacidad de almacenamiento debe aumentar. Es necesario decir que los datos de la matriz ya se copian al nuevo espacio de almacenamiento. Al insertar o eliminar elementos de la posición media de la lista de matrices, la matriz debe copiarse, moverse y el costo es relativamente alto. Por lo tanto, es adecuado para búsquedas y traversales aleatorios, no para inserción y eliminación.
2. El vector también se implementa a través de matrices, la diferencia es que admite la sincronización de subprocesos, es decir, en un momento determinado, solo un hilo puede escribir un vector para evitar la inconsistencia causada por la escritura de múltiples hilos al mismo tiempo, pero cuesta mucho implementar la sincronización, por lo que acceder a él es más lento que el acceso a ArrayList.
3. LinkedList utiliza una estructura de lista vinculada para almacenar datos, que es muy adecuado para la inserción y eliminación dinámica de los datos, y las velocidades de acceso aleatorio y transversal son relativamente lentos. Además, también proporciona métodos que no se definen en la interfaz de la lista, que se utilizan específicamente para operar el encabezado de la tabla y los elementos de cola, y pueden usarse como pilas, colas y colas bidireccionales.
5. Una breve comprensión de la cola de cola, cola de doble extremo deque
1. Cola
Se ha agregado una nueva interfaz java.util.queue a Java5 para admitir operaciones comunes de cola. Esta interfaz extiende la interfaz java.util.collection.
La cola de interfaz pública <E> extiende la colección <E>
Además de las operaciones básicas de recolección, las colas proporcionan otras operaciones de inserción, extracto y verificación.
Cada método tiene dos formularios: uno lanza una excepción (cuando una operación falla), y el otro devuelve un valor especial (nulo o falso, dependiendo de la operación).
Las colas generalmente (pero no necesariamente) clasifican elementos individuales en un FIFO (primero en primera salida). Sin embargo, la cola prioritaria y la cola LIFO (o pila) son excepciones. El primero clasifica los elementos de acuerdo con el orden natural del comparador o elementos proporcionados, y el segundo clasifica los elementos en LIFO (lo último en primera vez).
En la cola FIFO, todos los elementos nuevos se insertan al final de la cola, y el elemento de extracción se elimina del encabezado de la cola.
Cuando use la cola, intente evitar los métodos add () y eliminar () de colección, pero use Oferta () para agregar elementos y use Poll () para obtener y eliminar elementos. Su ventaja es que pueden determinar si el éxito se logra devolviendo el valor, y los métodos agregar () y eliminar () lanzarán excepciones cuando fallan. Si desea usar la parte delantera sin quitar el elemento, use el método Element () o Peek ().
El método de oferta puede insertar un elemento, de lo contrario devuelve falso. Esto es diferente del método Collection.Add, que solo puede dejar de agregar elementos lanzando una excepción sin control.
Los métodos Remout () y Poll () eliminan y devuelven el encabezado de la cola. El elemento se elimina de la cola es la función de la política de clasificación de la cola, que es diferente en diversas implementaciones. Los métodos RemoLE () y Poll () se comportan de manera diferente solo cuando la cola está vacía: el método remove () arroja una excepción, mientras que el método Poll () regresa nulo.
Element () y Peek () return, pero no elimine, el encabezado de cola.
Las implementaciones de la cola generalmente no permiten la inserción de elementos nulos, aunque algunas implementaciones (como LinkedList) no prohíben la inserción de NULLS. Incluso en implementaciones que permiten nulas, no se debe insertar en la cola, porque NULL también se usa como un valor de retorno especial para el método de la encuesta, lo que indica que la cola no contiene elementos.
Vale la pena señalar que la clase LinkedList implementa la interfaz de la cola, por lo que podemos usar LinkedList como cola.
import java.util.queue; import java.util.linkedlist; Public Class testQueue {public static void main (string [] args) {queue <string> queue = new LinkedList <String> (); Queue.offer ("hola"); cola.offer ("¡Mundo!"); Queue.offer ("¡Hola!"); System.out.println (queue.size ()); Cuerda str; while ((str = queue.poll ())! = null) {system.out.print (str); } System.out.println (); System.out.println (queue.size ()); }}2. Deque
La interfaz pública deque <e> extiende la cola <E>
Una colección lineal que admite la inserción y la eliminación de elementos en ambos extremos.
El nombre Deque es la abreviatura de "cola de doble final" y generalmente se lee como "mazo".
La mayoría de las implementaciones de Deque no tienen un límite fijo en la cantidad de elementos que pueden contener, pero esta interfaz admite colas limitadas de capacidad y colas de doble extremo sin límites de tamaño fijo.
Esta interfaz define un método para acceder a elementos en ambos extremos de una cola de doble extremo. Proporciona métodos para insertar, eliminar e inspeccionar elementos. Debido a que esta interfaz hereda la cola de la interfaz de la cola, hay dos formas para cada uno de sus métodos: uno arroja una excepción cuando la operación falla y la otra devuelve un valor especial (nulo o falso, dependiendo de la operación).
a. Cuando use una cola de doble extremo como cola, obtendrá el comportamiento FIFO (primera entrada, primera vez). Agregue un elemento al final de la cola de doble extremo y retire el elemento desde el comienzo de la cola de doble extremo. Los métodos heredados de la interfaz de la cola son completamente equivalentes al método deque, como se muestra en la siguiente tabla:
b. Usado como Lifo (último en primer lugar) pila. Esta interfaz debe usarse primero en lugar de clases de pila heredada. Cuando se usa una cola de doble extremo como pila, el elemento se empuja al comienzo de la cola de doble extremo y aparece desde el comienzo de la cola de doble extremo. El método de la pila es completamente equivalente al método deque, como se muestra en la siguiente tabla: