Pilha e fila:
É geralmente usado como uma ferramenta para os programadores ajudarem na concepção de algoritmos, com um curto ciclo de vida e é criado apenas em tempo de execução;
O acesso é restrito e, em um determinado momento, apenas um dados pode ser lido ou excluído;
É uma estrutura abstrata, com um mecanismo de implementação interna que é invisível para os usuários, como usar matrizes e listas vinculadas para implementar a pilha.
Simular estrutura de pilha
Ao mesmo tempo, apenas um dados pode ser acessado, e a complexidade do tempo da saída mais tarde para a estilhaça é O (1), ou seja, não depende do número de itens de dados na pilha. A operação é relativamente rápida, usando uma matriz como estrutura de armazenamento da pilha
classe pública Stacks <t> {private int max; privado t [] ary; private int top; // ponteiro, subscrito para o elemento superior das pilhas de pilha (size int size) {this.max = size; ary = (t []) novo objeto [max]; top = -1; } // Stack public void push (t data) {if (! Isfull ()) ary [++ top] = data; } // pilha public t Pop () {if (isEmpty ()) {return null; } retornar ary [top--]; } // Veja a parte superior da pilha pública t peek () {return ary [top]; } // é a pilha vazia pública booleana isEmpty () {return top == -1; } // é a pilha pública completa booleana isfull () {return top == max - 1; } // tamanho public int size () {return top + 1; } public static void main (string [] args) {Stacks <Teger> Stack = new Stacks <Teger> (3); for (int i = 0; i <5; i ++) {staCK.push (i); System.out.println ("size:" + stack.size ()); } para (int i = 0; i <5; i ++) {integer peek = pilha.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--) {integer 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 ()); }}} No exemplo acima, há uma regulamentação do MaxSize, porque a matriz deve ser dimensionada. Se você deseja não ter limite, pode usar outras estruturas para armazenamento e, é claro, também pode ser uma nova variedade de comprimentos.
Exemplo, use o LinkedList Storage para implementar a pilha
classe pública Stackss <t> {private LinkedList <T> dados; public Stackss () {DataS = new LinkedList <T> (); } // Coloque o push public void de pilha (dados t) {datas.addlast (dados); } // Coloque a pilha public t POP () {return datas.removelt (); } // Verifique a parte superior da pilha public t peek () {return datas.getLast (); } // se a pilha está vazia pública booleana isEmpty () {return datas.isempty (); } // tamanho public int size () {return datas.size (); } public static void main (string [] args) {Stacks <Teger> Stack = new Stacks <Teger> (3); for (int i = 0; i <5; i ++) {staCK.push (i); System.out.println ("size:" + stack.size ()); } para (int i = 0; i <5; i ++) {integer peek = pilha.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--) {staack.push (i); System.out.println ("size:" + stack.size ()); } para (int i = 5; i> 0; i--) {integer 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 ()); }}}Exemplo, ordem reversa de palavras, usando a estrutura Statck
classe pública wordReverse {public static void main (string [] args) {reverse ("co., Ltd."); } estático void reverse (string word) {if (word == null) return; Stackss <Acfaracter> Stack = new Stackss <Acfaracter> (); char [] CharArray = word.toCharArray (); int len = chararray.length; for (int i = 0; i <len; i ++) {staack.push (CharArray [i]); } Stringbuilder sb = new stringbuilder (); while (! Stack.isEmpty ()) {sb.append (Stack.pop ()); } System.out.println ("Após a inversão:" + sb.toString ()); }}Imprimir:
Após a reversão: estilo social
Fila de simulação (fila geral, fila de ponta dupla, fila de prioridade)
fila:
Primeiro, lide com problemas de fila. Primeira fila, primeiro processo, primeira linha, segunda linha, etc. O processo anterior é concluído e a complexidade do tempo das operações de inserção e remoção é O (1). Insira na parte traseira e remova a fila de ponta dupla da frente:
Isto é, você pode inserir e remover nas duas extremidades da fila: inserirft, insertright, removeleft, removeir
Funções contendo pilha e filas. Se você remover o insertleft e o removeleft, será o mesmo que a pilha; Se você remover o Insertleft e o Removeright, será o mesmo que a fila. Geralmente, a frequência de uso é baixa e a complexidade do tempo o (1)
Fila prioritária:
Mantenha uma sequência interna classificada pela prioridade. Ao inserir, você precisa comparar e encontrar a posição de inserção, complexidade do tempo o (n), excluir o (1)
/** Fila primeiro na primeira saída, um ponteiro indica a posição de inserção e um ponteiro indica a posição do item de dados que está sendo retirado*/ public classe Queueq <T> {private int max; privado t [] ary; Frente privada int; // O chefe da equipe indica a posição do item de dados que está sendo retirado privado int traseiro; // A cauda da equipe indica a posição do item de dados que está sendo inserido private INT nitems; // o número real de itens de dados public fileueq (int size) {this.max = size; ary = (t []) novo objeto [max]; front = 0; traseiro = -1; nitems = 0; } // Insira a cauda da fila public void insert (t t) {if (traseiro == max - 1) {// Ele chegou ao final da fila real, comece do início, traseiro = -1; } ary [++ traseiro] = t; nitems ++; } // Remova a cabeça da equipe pública t remover () {t temp = ary [front ++]; if (front == max) {// A fila atingiu o final, comece desde o início, comece a partir do início, comece a partir do início, comece do início, 0; } nitems--; retornar temp; } // Veja o chefe da equipe public t peek () {return ary [front]; } public boolean isEmpty () {return nitems == 0; } public boolean isfull () {return nitems == max; } public int size () {return nitems; } public static void main (string [] args) {Queueq <Teger> fileue = new Queueq <Teger> (3); for (int i = 0; i <5; i ++) {Queue.insert (i); System.out.println ("size:" + fileue.size ()); } para (int i = 0; i <5; i ++) {integer peek = fileue.peek (); System.out.println ("Peek:" + Peek); System.out.println ("size:" + fileue.size ()); } para (int i = 0; i <5; i ++) {integer remove = fileue.remove (); System.out.println ("remover:" + remover); System.out.println ("size:" + fileue.size ()); } System.out.println ("----"); para (int i = 5; i> 0; i--) {fileue.insert (i); System.out.println ("size:" + fileue.size ()); } para (int i = 5; i> 0; i--) {integer peek = fileue.peek (); System.out.println ("Peek:" + Peek); System.out.println ("size:" + fileue.size ()); } para (int i = 5; i> 0; i--) {integer remove = fileue.remove (); System.out.println ("remover:" + remover); System.out.println ("size:" + fileue.size ()); }}} /** Fila de ponta dupla <span style = "space branco: pré"> </span> insira e exclua nas duas extremidades*/public classe Queueqt <t> {private LinkedList <t> lista; public queueqt () {list = new LinkedList <T> (); } // Insira o cabeçote da fila public void insertleft (t t) {list.addfirst (t); } // Insira a cauda da fila public void insertright (t t) {list.addlast (t); } // Remova a cabeça da fila public t removeleft () {return list.removefirst (); } // Remova o final da equipe public t removeright () {return list.RemovelSt (); } // Veja o chefe da equipe public t peekleft () {return list.getfirst (); } // Veja o final da equipe public t peekright () {return list.getLast (); } public boolean isEmpty () {return list.isempty (); } public int size () {return list.size (); }} /** A fila de prioridade é classificada por prioridade e é uma fila ordenada*/ classe pública queueqp {private int max; private int [] ary; private int nitems; // O número real de itens de dados public fileueqp (int size) {this.max = size; ary = new int [max]; nitems = 0; } // Insira o final da fila 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]; // Atribua o anterior ao próximo é equivalente ao uso de classificação de inserção. A sequência fornecida é originalmente ordenada, portanto, eficiência o (n)} else {break; }} ary [j + 1] = t; nitems ++; } System.out.println (Arrays.toString (ARY)); } // Remova a cabeça da equipe public int REMOT () {return ary [-nitems]; // Remova a pequena prioridade} // Veja a menor prioridade da equipe pública int peekmin () {return ary [nitems - 1]; } public boolean isEmpty () {return nitems == 0; } public boolean isfull () {return nitems == max; } public int size () {return nitems; } public static void main (string [] args) {Queueqp fila = new Queueqp (3); Queue.Insert (1); Queue.insert (2); Queue.insert (3); int remover = fileue.remove (); System.out.println ("remover:" + remover); }}