Pila y cola:
Generalmente se usa como una herramienta para que los programadores ayuden en la concepción de los algoritmos, con un breve ciclo de vida y se crea solo en tiempo de ejecución;
El acceso está restringido, y en un momento determinado, solo se pueden leer o eliminar un datos;
Es una estructura abstracta, con un mecanismo de implementación interna que es invisible para los usuarios, como el uso de matrices y listas vinculadas para implementar la pila.
Simular la estructura de la pila
Al mismo tiempo, solo se permite acceder a un datos, y la complejidad del tiempo del más tarde en la salida tanto para la pila como para la salida es o (1), es decir, no depende de la cantidad de elementos de datos en la pila. La operación es relativamente rápida, utilizando una matriz como estructura de almacenamiento de la pila
Pilas de clase pública <t> {private int max; privado t [] ary; privado int top; // puntero, subíndice al elemento superior de las pilas públicas de la pila (size int) {this.max = size; ary = (t []) nuevo objeto [max]; superior = -1; } // push public void push (t data) {if (! Isfull ()) ary [++ top] = data; } // pila public t pop () {if (isEmpty ()) {return null; } return ary [top--]; } // Ver la parte superior de la pila pública t peek () {return ary [top]; } // es la pila vacía pública boolean isEmpty () {return top == -1; } // es la pila completa pública boolean isfull () {return top == max - 1; } // size public int size () {return top + 1; } public static void main (string [] args) {pilas <integer> stack = new Stacks <integer> (3); para (int i = 0; i <5; i ++) {stack.push (i); System.out.println ("size:" + stack.size ()); } para (int i = 0; i <5; i ++) {Integer peek = stack.peek (); System.out.println ("Peek:" + Peek); System.out.println ("size:" + stack.size ()); } para (int i = 0; i <5; i ++) {Integer pop = stack.pop (); System.out.println ("Pop:" + Pop); System.out.println ("size:" + stack.size ()); } System.out.println ("----"); para (int i = 5; i> 0; i--) {stack.push (i); System.out.println ("size:" + stack.size ()); } para (int i = 5; i> 0; i--) {entero peek = stack.peek (); System.out.println ("Peek:" + Peek); System.out.println ("size:" + stack.size ()); } para (int i = 5; i> 0; i--) {Integer pop = stack.pop (); System.out.println ("Pop:" + Pop); System.out.println ("size:" + stack.size ()); }}} En el ejemplo anterior, hay una regulación máxima, porque la matriz debe ser dimensionada. Si desea no tener límite, puede usar otras estructuras para el almacenamiento y, por supuesto, también puede nuevo una variedad de nueva longitud.
Ejemplo, use el almacenamiento de LinkedList para implementar la pila
Public Class Stackss <t> {DataS de LinkedList <T> privado; public stackss () {datas = new LinkedList <T> (); } // Ponga la pila public void push (t data) {dataS.addlast (datos); } // Ponga la pila public t pop () {return dataS.removelast (); } // Verifique la parte superior de la pila public t pisek () {return dataS.getLast (); } // si la pila es pública vacía boolean isEmpty () {return dataS.isEmpty (); } // size public int size () {return dataS.size (); } public static void main (string [] args) {pilas <integer> stack = new Stacks <integer> (3); para (int i = 0; i <5; i ++) {stack.push (i); System.out.println ("size:" + stack.size ()); } para (int i = 0; i <5; i ++) {Integer peek = stack.peek (); System.out.println ("Peek:" + Peek); System.out.println ("size:" + stack.size ()); } para (int i = 0; i <5; i ++) {Integer pop = stack.pop (); System.out.println ("Pop:" + Pop); System.out.println ("size:" + stack.size ()); } System.out.println ("----"); para (int i = 5; i> 0; i--) {stack.push (i); System.out.println ("size:" + stack.size ()); } para (int i = 5; i> 0; i--) {stack.push (i); System.out.println ("size:" + stack.size ()); } para (int i = 5; i> 0; i--) {entero peek = stack.peek (); System.out.println ("Peek:" + Peek); System.out.println ("size:" + stack.size ()); } para (int i = 5; i> 0; i--) {Integer pop = stack.pop (); System.out.println ("Pop:" + Pop); System.out.println ("size:" + stack.size ()); }}}Ejemplo, palabra inversa de palabras, utilizando la estructura STATCK
public class WordReverse {public static void main (string [] args) {reverse ("co., ltd."); } static void reverse (word de cadena) {if (word == null) return; Stackss <caracter> stack = new stackss <caracter> (); char [] chararray = word.toCarArray (); int Len = CharArray.length; para (int i = 0; i <len; i ++) {stack.push (chararray [i]); } StringBuilder sb = new StringBuilder (); while (! stack.isempty ()) {sb.append (stack.pop ()); } System.out.println ("después de la inversión:" + sb.toString ()); }}Imprimir:
Después de la inversión: estilo social
Cola de simulación (cola general, cola de doble extremo, cola prioritaria)
cola:
Primero en primera salida, lidiar con los problemas de cola. Primera cola, primer proceso, primera fila, segunda fila, etc. El proceso anterior se completa, y la complejidad del tiempo de las operaciones de inserción y eliminación es O (1). Inserte desde la parte posterior y retire la cola de doble extremo desde el frente:
Es decir, puede insertar y eliminar en ambos extremos de la cola: InsertLeft, InserTright, RemoVeleft, Removeright
Funciones que contienen pila y colas. Si elimina InsertLeft y RemoVeleft, será lo mismo que la pila; Si elimina InsertLeft y Removeright, será lo mismo que la cola. En general, la frecuencia de uso es baja y la complejidad del tiempo o (1)
Cola prioritaria:
Mantenga una secuencia interna ordenada por prioridad. Al insertar, debe comparar y encontrar la posición de inserción, complejidad de tiempo o (n), eliminar o (1)
/** Cola primero en primera salida, un puntero indica la posición de inserción, y un puntero indica la posición del elemento de datos que se está sacando*/ public class queueq <t> {private int max; privado t [] ary; privado int front; // El jefe del equipo indica la posición del elemento de datos que se saca privado int // La cola del equipo indica la posición del elemento de datos que se inserta los int nitems privados; // El número real de elementos de datos public queueq (int tamaño) {this.max = size; ary = (t []) nuevo objeto [max]; Frente = 0; trasero = -1; nitems = 0; } // Inserte la cola de la cola pública void insert (t t) {if (trasera == max - 1) {// ha alcanzado el extremo de la cola real, comienza desde el principio, trasero = -1; } ary [++ trasero] = t; nitems ++; } // Retire la cabeza del equipo public t remove () {t temp = ary [front ++]; if (front == max) {// La cola ha llegado al final, comience desde el principio, comience desde el principio, comience desde el principio, comience desde el principio, 0; } nitems--; regresar temp; } // Ver el jefe del equipo public t peek () {return ary [front]; } public boolean isEtimty () {return nitems == 0; } public boolean isfull () {return nitems == max; } public int size () {return nitems; } public static void main (string [] args) {queueq <integer> queue = new Queueq <integer> (3); para (int i = 0; i <5; i ++) {queue.insert (i); System.out.println ("size:" + queue.size ()); } para (int i = 0; i <5; i ++) {integer peek = queue.peek (); System.out.println ("Peek:" + Peek); System.out.println ("size:" + queue.size ()); } para (int i = 0; i <5; i ++) {integer remove = queue.remove (); System.out.println ("eliminar:" + eliminar); System.out.println ("size:" + queue.size ()); } System.out.println ("----"); para (int i = 5; i> 0; i--) {queue.insert (i); System.out.println ("size:" + queue.size ()); } para (int i = 5; i> 0; i--) {entero peek = queue.peek (); System.out.println ("Peek:" + Peek); System.out.println ("size:" + queue.size ()); } para (int i = 5; i> 0; i--) {Integer Remete = queue.remove (); System.out.println ("eliminar:" + eliminar); System.out.println ("size:" + queue.size ()); }}} /** Cola de doble extremo <span style = "White-Space: pre"> </span> Insertar y eliminar en ambos extremos*/public class Queueqt <t> {private LinkedList <T> list; public queueqt () {list = new LinkedList <T> (); } // inserta el cabezal de cola public void insertleft (t t) {list.addfirst (t); } // Inserte la cola cola public void insertright (t t) {list.addlast (t); } // Eliminar el cabezal de cola public t removeleft () {return list.removeFirst (); } // eliminar el final del equipo público t removeright () {return list.removelast (); } // Ver el jefe del equipo público t peekleft () {return list.getFirst (); } // Ver el final del equipo público t peekright () {return list.getLast (); } public boolean isEtimty () {return list.isEmpty (); } public int size () {return list.size (); }} /** La cola de prioridad se clasifica por prioridad, y es una cola ordenada*/ public class queueqp {private int max; privado int [] ary; Private int nitems; // El número real de elementos de datos public queueqp (int size) {this.max = size; ary = new int [max]; nitems = 0; } // inserta el final de la cola public void insert (int t) {int j; if (nitems == 0) {ary [nitems ++] = t; } else {for (j = nitems-1; j> = 0; j--) {if (t> ary [j]) {ary [j + 1] = ary [j]; // Asignar el anterior al siguiente es equivalente a usar la clasificación de inserción. La secuencia dada se ordena originalmente, por lo que la eficiencia o (n)} else {break; }} ary [j + 1] = t; nitems ++; } System.out.println (arrays.toString (ary)); } // retira el jefe del equipo public int remove () {return ary [-nitems]; // Eliminar la pequeña prioridad} // Ver la prioridad más baja del equipo public int Peekmin () {return ary [nitems - 1]; } public boolean isEtimty () {return nitems == 0; } public boolean isfull () {return nitems == max; } public int size () {return nitems; } public static void main (string [] args) {queueqp queue = new Queueqp (3); cola.insert (1); cola.insert (2); cola.insert (3); int eliminar = queue.remove (); System.out.println ("eliminar:" + eliminar); }}