Fomos expostos a várias estruturas de dados antes, incluindo matrizes, listas vinculadas, tabelas de hash e árvores vermelhas e negras (árvores de consulta binária). Hoje, vejamos outra estrutura de dados: pilha.
O que é uma pilha? Vamos primeiro olhar para um exemplo: uma pilha é equivalente a um barril de madeira muito estreito. Quando colocamos as coisas no cano de madeira e retiramos as coisas, descobriremos que a coisa que colocamos no fundo no início e a primeira coisa que tiramos foi a que acabamos de colocar. Portanto, a pilha é um recipiente que entra e sai (FirstInLastout, ou mais tarde, primeiro a sair). Ele tem apenas uma boca, coloca elementos nesta boca e também retira elementos nesta boca. Então vamos aprender a pilha no JDK a seguir.
1. Introdução básica e uso de vetor e pilha
Vamos primeiro olhar para a definição de JDK:
classe pública Stack <e> estende o vetor <e> {Do exposto, podemos ver que a pilha é herdada do vetor, por isso devemos também ter um certo entendimento do vetor.
Vetor: matrizes dinâmicas seguras de tópicos
Pilha: herdando o vetor, uma pilha segura por thread implementada com base em matrizes dinâmicas;
1. Recursos de vetor e pilha:
Vector e Arraylist são basicamente os mesmos. A diferença é que o vetor é seguro e adicionará a palavra-chave sincronizada antes dos possíveis métodos seguros de encadeamento;
Vetor: velocidade rápida de acesso aleatório, inserção baixa e desempenho de remoção (características da matriz); suporta elementos nulos; tem ordem; Os elementos podem ser repetidos; seguro de tópico;
Pilha: After-in, primeiro-saída, implementa alguns métodos básicos de operações de pilha (na verdade, não é apenas pós-entrada, primeiro saída, porque herdado do vetor, pode haver muitas operações e, em certo sentido, não é uma pilha);
2. Estrutura do vetor e da pilha:
Classe vetorial
É basicamente o mesmo que o ArrayList, e as principais diferenças restantes são as seguintes:
1. O vetor é seguro para fios
2. O crescimento da Arraylist é inconsistente com o crescimento do vetor
Outros, se os métodos de construção forem inconsistentes, o vetor poderá inicializar a capacidade de incremento através do método de construção e existem outros métodos, como o método índiceof. O vetor suporta a pesquisa e a pesquisa no local especificado; Além disso, o Vector também possui alguns métodos redundantes com funções duplicadas, como o método AddElement e setElementat. A razão para isso se deve a razões históricas. Por exemplo, o método do addElement foi deixado para trás antes. Quando a estrutura da coleção foi introduzida, o Vector ingressou na família da coleção e mudou para implementar a interface da lista. Alguns métodos definidos na interface da lista precisam ser implementados. No entanto, por razões de compatibilidade, os métodos antigos não podem ser excluídos; portanto, alguns métodos antigos com redundância apareceram. Agora ele foi substituído pelo ArrayList e é basicamente raramente usado, então apenas entenda.
Classe de pilha
A operação básica da pilha é realizada. O método é o seguinte:
pilha pública ();
Crie uma pilha vazia
E Peek () público sincronizado;
Retorna o valor na parte superior da pilha;
public e push (e item);
Operação de pilha;
público sincronizado e pop ();
Operação fora da pilha;
public boolean vazio ();
Determine se a pilha está vazia;
Public Sincronized Int Search (Objeto O);
Retorna a posição do objeto na pilha;
Para a pilha acima, basicamente usaremos apenas o método acima. Embora herde o vetor e tenha muitos métodos, ele basicamente não será usado, mas é apenas tratado como uma pilha.
3. Uso básico
Alguns métodos no vetor são usados da seguinte maneira. Além disso, o método de vetor de travessia é o mesmo do Arraylist. Você pode usar foreach, iterator e para travessia de loop;
importar java.util.arrays; importar java.util.iterator; importar java.util.list; importar java.util.ListIterator; importar java.util.vector; public class Test {public static void main (string [] argus) {vector <pregger> vetor = new Vector <intereger> () (args) {vector <pregger> vetor = new Vector <veger> for (int i = 0; i <10; i ++) {vector.add (i); } // print system.out.println (Vector.toString ()); // size () system.out.println (vetor.size ()); // Contans System.out.println (Vector.Contains (2)); // iterator iterator <Teger> iterator = vetor.iterator (); while (iterator.hasnext ()) {System.out.print (iterator.Next () + ""); } // objeto de ToArray [] objarr = vetor.toarray (); System.out.println ("/nobjarr:" + Arrays.asList (objarr)); Integer [] INTARR = Vector.ToArray (novo Integer [Vector.size ()]); System.out.println ("INTARR:" + Arrays.asList (INTARR)); // Adicione Vector.Add (5); // Remover Vector.Remove (5); System.out.println (vetor); // containsall System.out.println (Vector.containsall (Arrays.asList (5,6))); // addall vector.addall (Arrays.aslist (555.666)); System.out.println (vetor); // removeall Vector.Removeall (Arrays.asList (555.666)); System.out.println (vetor); // Addall Method Vector.addall (5, Arrays.asList (666.666, 6)); System.out.println (vetor); // Get Method System.out.println (Vector.get (5)); // Definir método vetor.set (5, 55); System.out.println (Vector.get (5)); // Adicionar método vetor.add (0, 555); System.out.println (vetor); // remove o método vetor.remove (0); System.out.println (vetor); // indexOf Method System.out.println (Vector.IndexOF (6)); // LastIndexOf Method System.out.println (Vector.LastIndexOf (6)); // Método Listiterator listiterator <Teger> listIterator = vetor.ListIterator (); System.out.println (listiterator.hasprevious ()); // listiterator (índice) Método Listiterator <Teger> ilistIterator = Vector.ListIterator (5); System.out.println (ilistIterator.previous ()); // SUBlist Method System.out.println (Vector.sublist (5, 7)); // Clear Vector.clear (); System.out.println (vetor); }}Alguns métodos na pilha são usados da seguinte maneira. Como a pilha herda o vetor, a pilha também pode usar métodos que o vetor pode usar. O seguinte lista alguns exemplos dos métodos exclusivos da pilha. É muito simples, que são algumas operações básicas da pilha. Além de vários métodos de travessia de vetor, a Stack também possui seus próprios métodos de traversal exclusivos (usando o método vazio e o método pop para obter travessia de cima para a parte inferior da pilha):
importar java.util.stack; public class Test {public static void main (string [] args) {Stack <Teger> Stack = new Stack <Teger> (); for (int i = 0; i <10; i ++) {staack.add (i); } System.out.println (pilha); System.out.println (Stack.peek ()); Stack.push (555); System.out.println (pilha); System.out.println (Stack.pop ()); System.out.println (pilha); System.out.println (Stack.empty ()); System.out.println (Stack.search (6)); System.out.println ("pilha travessal:"); while (! Stack.Empty ()) {System.out.print (Stack.pop () + ""); }}}Subseção:
O vetor é seguro para fios, mas tem mau desempenho. Geralmente, o ArrayList é usado, a menos que haja requisitos especiais;
Se você planeja usar a pilha como pilha, deve seguir honestamente e estritamente as várias operações da pilha. Caso contrário, seria significativo usar a pilha e seria melhor usar o vetor;
2. Estrutura de vetor e Stacke e armazenamento subjacente
Vector de classe pública <e> estende a Lista de implementos abstrataList <E>
O vetor é uma classe de implementação de lista. De fato, o Vector também é um contêiner de lista com base na implementação da matriz. Suas funções e código de implementação são basicamente os mesmos que o ArrayList. Então, o que é diferente? Uma é que, quando a matriz é expandida, o vetor é *2 e o Arraylist é *1,5+1; O outro é que o vetor é seguro para roscas, enquanto o Arraylist não é. A abordagem segura por thread do vetor é adicionar uma palavra-chave sincronizada a cada método para garantir. Mas aqui, o vetor não é mais oficialmente (reconhecido por todos) e não é recomendado. É oficialmente porque seu método de segurança de threads é bloquear todo o método, o que leva a baixa eficiência. Então, existe uma solução melhor? De fato, não se pode dizer que existe um, mas há realmente uma, coleções.SynchronizedList ()
Como a pilha é herdada e baseada no vetor, vamos dar uma olhada em algumas definições e códigos de origem de método do vetor:
// A camada subjacente usa uma matriz para armazenar objeto protegido por dados [] elementData; // o número de elementos protegidos int elementCount; // Personalize a expansão do contêiner e o tamanho da capacidade protegida do tamanho protegido; Public Vector (int InitialCapacity, int CapacateIncrement) {super (); // limites de saída Verifique se (InitialCapacidade <0) lançar nova ilegalArgumentException ("Capacidade ilegal:" + InitialCapacidade); // inicialize a matriz this.ElementData = novo objeto [InitialCapacity]; this.CapacityIncrement = CapacleIncrement; } // Use o método de bloqueio de palavra -chave sincronizado para garantir que apenas um thread possa manipular o método ao mesmo tempo em que o booleano sincronizado público add (e e) {modCount ++; // Verificação de aumento de EnsureCapacityHelper (ElementCount + 1); ElementData [ElementCount ++] = e; retornar true; } vazio privado EnsureCapacityHelper (int mincapacity) {// Número atual de elementos int OldCapacity = ElementData .Length; // é necessário expandir a capacidade se (Mincapacity> OldCapacity) {objeto [] OldData = elementData; // Se a expansão do contêiner for personalizada, expanda a capacidade de acordo com a capacitação, expandindo a capacidade de duas vezes (*2) int newCapacity = (CapacateIncrement> 0)? (OldCapacity + CapacateIncrement): (OldCapacity * 2); if (newCapacity <mincapacity) {newCapacity = mincapacity; } // Array Copy elementData = Arrays.copyof (ElementData, NewCapacity); }}Vetor simplesmente veja isso. Se o outro método de pilha não for chamado, ele não será analisado. Se você não entende, pode verificar a análise do código -fonte do Arraylist.
3. Análise dos principais métodos
1.Peek () - Obtenha o objeto na parte superior da pilha
/ ** * Obtenha o objeto na parte superior da pilha, mas não exclua */ public sincronizado e peek () {// o número atual de elementos de contêiner int len = size (); // Se não houver elemento, jogue uma exceção diretamente se (len == 0) lança new emptystackSception (); // CHAME Método Elementat para recuperar o último elemento da matriz (o último elemento está na parte superior da pilha) Retornar Elementat (Len - 1); } / *** Obtenha o elemento nesta posição de acordo com o índice, este método está no vetor* / public sincronizado e elementat (int index) {// saia dos limites if (index> = elementCount) {lança new ArrayIndexoutOfBoundSception (index + "> =" + elementCount); } // obtenha o elemento retornar (e) elementData [index]; }2.pop () - coloque a pilha (fora da pilha), pegue o objeto na parte superior da pilha e exclua o objeto do contêiner
/ *** Bumble a pilha, obtenha e exclua o objeto na parte superior da pilha*/ público sincronizado e pop () {// grava o objeto na parte superior da pilha e obj; // o número atual de elementos de contêiner int len = size (); // Obtenha o objeto na parte superior da pilha obj através do método peek () obj = peek (); // Ligue para o método RemoverElement para excluir o objeto na parte superior da pilha RemoverElementat (Len - 1); // retorna ao objeto na parte superior da pilha retorna obj; } / *** Exclua o elemento de acordo com o índice* / public sincronizado void removelementat (int index) {modCount ++; // Os limites de saída if (index> = elementCount) {lança novos ArrayIndexoutOfBoundSexception (index + "> =" + elementCount); } else if (índice <0) {lança novo ArrayIndexoutOfBoundSexception (index); } // Calcule o número de elementos de matriz a serem movidos int j = elementCount - Index - 1; if (j> 0) {// mova a matriz, exclua um no meio, então mova o elemento subsequente para a frente (movendo aqui substitua diretamente o sistema de posição do índice, que é equivalente à exclusão). Arraycopy (ElementData, Index + 1, ElementData, Index, J); } // menos 1 ElementCount--; // Defina o último elemento do contêiner para esvaziar (porque um elemento foi excluído e os elementos por trás do índice foram movidos para a frente, então o último foi inútil) ElementData [ElementCount] = nulo; / * Para deixar o GC fazer seu trabalho */}3.push (e item) - empurre (na pilha), adicione o objeto no contêiner e devolva -o
/ ** * Adicione o objeto ao contêiner e retorne */ public e push (e item) {// Ligue para o addElement ao addElement (item); // retorna o item de retorno do elemento; } /*** Adicione o elemento ao contêiner. Este método está no vetor*/ public sincronizado void addElement (e obj) {modCount ++; // Verificação de aumento de EnsureCapacityHelper (ElementCount + 1); // Coloque o objeto na matriz, o número de elementos +1 elementData [elementCount ++] = obj; }4.search (objeto o) - retorna a posição do objeto no recipiente, o topo da pilha é 1
/ ** * Retorne a posição do objeto no contêiner, a parte superior da pilha é 1 */ public sincronizado Int Search (objeto o) {// Encontre o elemento da matriz, a partir da última ocorrência de int i = lastIndexof (o); // porque a parte superior da pilha conta 1, você precisa usar tamanho () - i para calcular se (i> = 0) {return size () - i; } retornar -1; }5.Empty () - é o contêiner vazio
/ *** Verifique se o contêiner está vazio*/ public boolean vazio () {return size () == 0; }Subseção:
Neste ponto, o método da pilha é analisado. Como a pilha é baseada em matrizes, ainda é fácil de entender (porque é baseado no ArrayList).
Embora o código -fonte da pilha no JDK tenha sido analisado, é necessário discuti -lo aqui. Não sei se achei que a pilha aqui é muito estranha.
(1) Por que a pilha é implementada com base em matrizes?
Todos conhecemos as características das matrizes: elas são convenientes para consulta com base em subscritos (acesso aleatório), mas a memória é fixa e a eficiência da expansão da capacidade é baixa. É fácil pensar na coisa mais adequada para a pilha usar listas vinculadas.
(2) Por que a pilha herda o vetor?
A herança significa que a pilha herda o método vetorial, o que faz com que a pilha pareça um pouco inadequada, tanto uma lista quanto uma pilha. Qual deve ser uma abordagem razoável se você precisar herdar o vetor: a pilha não herdar o vetor, mas apenas tem uma referência ao próprio vetor, a agregação está certa?
A única explicação é que a pilha foi criada pelo JDK1.0. Naquela época, os contêineres no JDK não tinham apenas vetores, como ArrayList, LinkedList etc., e como já possuem vetor e podem implementar funções de pilha e depois fazê -lo. . . Como é ideal para implementar pilha com listas vinculadas, vamos tentar:
importar java.util.LinkedList; classe pública LinkedStack <E> {private LinkedList <E> Linked; public LinkedStack () {this.Linked = new LinkedList <E> (); } public e push (e item) {this.linked .addfirst (item); item de retorno; } 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 pesquisa (e item) {int i = this.linked.indexof (item); retornar i + 1; } public boolean empty () {return this.linked.isEmpty (); }}A pilha implementada pela LinkedList é usada aqui. Lembre -se, como mencionado no LinkedList, o LinkedList implementa a interface DEQUE para que ela possa ser usada como uma pilha (primeiro dentro e fora) e uma fila (primeiro dentro e fora).
4. A diferença entre Vector e Arraylist
Existem três classes de implementação na interface da lista, nomeadamente ArrayList, Vector e LinkedList. A lista é usada para armazenar vários elementos, pode manter a ordem dos elementos e permite a repetição de elementos.
As diferenças relevantes entre as três classes de implementação específicas são as seguintes:
1. Arraylist é a classe de implementação da lista mais usada, implementada internamente através de matrizes, o que permite acesso aleatório rápido aos elementos. A desvantagem das matrizes é que não pode ser espaçado entre cada elemento. Quando o tamanho da matriz não é satisfeito, a capacidade de armazenamento precisa ser aumentada. É necessário dizer que os dados da matriz já são copiados para o novo espaço de armazenamento. Ao inserir ou excluir elementos da posição intermediária do Arraylist, a matriz precisa ser copiada, movida e o custo é relativamente alto. Portanto, é adequado para pesquisas e travessias aleatórias, não para inserção e exclusão.
2. O vetor também é implementado por meio de matrizes, a diferença é que ele suporta a sincronização do encadeamento, ou seja, em um determinado momento, apenas um thread pode escrever um vetor para evitar inconsistência causada por vários threads que escrevem ao mesmo tempo, mas custa muito para implementar a sincronização, portanto, o acesso é mais lento do que o acesso à ArrayList.
3. O LinkedList usa uma estrutura de lista vinculada para armazenar dados, que é muito adequada para inserção e exclusão dinâmica de dados, e o acesso aleatório e as velocidades de traversal são relativamente lentas. Além disso, ele também fornece métodos que não são definidos na interface da lista, que são usados especificamente para operar elementos de cabeçalho e cauda da tabela e podem ser usados como pilhas, filas e filas bidirecionais.
5. Uma breve compreensão da fila da fila, deque de ponta dupla
1. Fila
Uma nova interface java.util.queue foi adicionada ao Java5 para oferecer suporte a operações de fila comuns. Esta interface estende a interface java.util.Collection.
Fila de interface pública <e> estende a coleção <E>
Além das operações básicas de coleta, as filas fornecem outras operações de inserção, extração e verificação.
Cada método possui dois formulários: um lança uma exceção (quando uma operação falha) e o outro retorna um valor especial (nulo ou falso, dependendo da operação).
As filas geralmente (mas não necessariamente) classificam elementos individuais em um FIFO (primeiro a primeiro a sair). No entanto, a fila de prioridade e a fila LIFO (ou pilha) são exceções. O primeiro classifica os elementos de acordo com a ordem natural do comparador ou elementos fornecidos, e o último classifica os elementos no LIFO (mais recente na primeira saída).
Na fila FIFO, todos os novos elementos são inseridos no final da fila e o elemento de remoção é removido do cabeçalho da fila.
Ao usar a fila, tente evitar os métodos add () e remover () () de coleta, mas use oferta () para adicionar elementos e usar a Poll () para obter e remover elementos. Sua vantagem é que eles podem determinar se o sucesso é alcançado retornando o valor e os métodos add () e remover () lançarão exceções quando falharem. Se você deseja usar o front -end sem remover o elemento, use o método Element () ou Peek ().
O método de oferta pode inserir um elemento, caso contrário, retorna falsa. Isso é diferente do método da coleção.Add, que só pode deixar de adicionar elementos lançando uma exceção sem controle.
Os métodos Remone () e Poll () removem e retornam o cabeçalho da fila. Qual elemento é removido da fila é a função da política de classificação da fila, que é diferente em várias implementações. Os métodos Remone () e Poll () se comportam de maneira diferente apenas quando a fila está vazia: o método Remover () lança uma exceção, enquanto o método Poll () retorna nulo.
elemento () e Peek () retornam, mas não removem, o cabeçalho da fila.
As implementações da fila geralmente não permitem a inserção de elementos nulos, embora algumas implementações (como o LinkedList) não proíbam a inserção de nulos. Mesmo nas implementações que permitem nulo, o nulo não deve ser inserido na fila, porque o NULL também é usado como um valor de retorno especial para o método da pesquisa, indicando que a fila não contém elementos.
Vale ressaltar que a classe LinkedList implementa a interface da fila, para que possamos usar o LinkedList como uma fila.
importar java.util.queue; importar java.util.LinkedList; classe pública testQueue {public static void main (string [] args) {fileue <string> fileeue = new LinkedList <string> (); fila.offer ("hello"); fila.offer ("mundo!"); fila.offer ("Olá!"); System.out.println (Queue.size ()); String str; while ((str = fileue.poll ())! = null) {System.out.print (str); } System.out.println (); System.out.println (Queue.size ()); }}2. Deque
interface pública deque <e> estende a fila <E>
Uma coleção linear que suporta inserção e remoção de elementos nas duas extremidades.
O nome Deque é a abreviação de "fila de ponta dupla" e geralmente é lida como "deck".
A maioria das implementações deque não tem limite fixo para o número de elementos que eles podem conter, mas essa interface suporta filas limitadas pela capacidade e filas de dupla ponta sem limites de tamanho fixo.
Esta interface define um método para acessar elementos nas duas extremidades de uma fila de ponta dupla. Fornece métodos para inserir, remover e inspecionar elementos. Como essa interface herda a fila da interface da fila, existem duas formas para cada um de seus métodos: um lança uma exceção quando a operação falha e o outro retorna um valor especial (nulo ou falso, dependendo da operação).
um. Ao usar uma fila de ponta dupla como uma fila, você terá um comportamento FIFO (primeiro entrada, primeiro a sair). Adicione um elemento à extremidade da fila de ponta dupla e remova o elemento do início da fila de ponta dupla. Os métodos herdados da interface da fila são completamente equivalentes ao método DEQUE, conforme mostrado na tabela a seguir:
b. Usado como LIFO (última a partir da primeira saída). Essa interface deve ser usada primeiro, em vez das classes de pilha herdada. Ao usar uma fila de ponta dupla como pilha, o elemento é empurrado para o início da fila de ponta dupla e aparece desde o início da fila de ponta dupla. O método da pilha é completamente equivalente ao método DEQUE, como mostrado na tabela a seguir: