Durante as entrevistas, pilhas e filas geralmente aparecem em pares para examinar. Este artigo contém o seguinte conteúdo de teste para pilha e filas:
(1) criação de pilha
(2) Criação da fila
(3) Duas pilhas implementam uma fila
(4) Duas filas implementam uma pilha
(5) Projete uma pilha com a função mínima min () e requer que a complexidade do tempo de min, push, pop e tudo seja O (1)
(6) determinar se as seqüências de push e pop da pilha são consistentes
1. Criação da pilha:
Em seguida, criamos uma pilha na forma de uma lista vinculada para facilitar a expansão.
Implementação de código:
classe pública Pilha {Public Node Head; Nó do nó = novo nó (dados); } nó público () {if (current == null) {return null; Nó está sendo colocado na pilha, o nó de retorno atual de retorno;} node {int data; }} public static void main (string [] args) {Stack Stack = new Stack (); POP (). Dados);Ao entrar na pilha, 14 ou 15 linhas de código são a chave.
Efeito de corrida:
2. Criação da fila:
Existem duas formas de criação de filas: com base na implementação da estrutura da matriz (fila sequencial) e com base na implementação da estrutura da lista vinculada (fila de cadeia).
Em seguida, criaremos uma fila na forma de uma lista vinculada, para que a fila seja mais conveniente ao expandir. Quando a fila for desqueida, comece do início da cabeça do nó.
Implementação de código:
Ao inserir a pilha, é o mesmo que adicionar nós em uma lista vinculada comum;
classe pública Fila {Public Node Head; } else {current.Next = new Node (Data); "fila está vazia"); dados; i = 0; .out.println (Queue.pop ());}}Efeito de corrida:
3. Duas pilhas implementam uma fila:
Ideias:
A pilha 1 é usada para armazenar elementos, a pilha 2 é usada para pop elementos, negativos e negativos são positivos.
Para simplificar, agora coloque os dados 1, 2 e 3 na pilha, depois saia da pilha um (3, 2, 1) e coloque -o na pilha dois, depois os dados da pilha dois (1, 2,3) Ele está em conformidade com as regras da fila, isto é, negativo e negativo são positivas.
Versão completa da implementação do código:
importar java.util.stack;/*** criado por smyhvae em 2015/9/9. Stack <Integer> Stack2 = new Stack <> (); // Stack para executar operação de dequeue // Método: Adicione uma operação de enquadre à fila public void push (int data) {Stack1.push (dados);}//método : Dê à fila uma operação de dequeue public int pop () lança exceção {if (Stack2.Empty ()) {// Antes de colocar os dados no Stack1 no Stack2, você deve garantir que o Stack2 esteja vazio (ou está vazio no começo, Os dados no Stack2 foram divulgados), caso contrário, a ordem de despedimento será confusa, o que é fácil de esquecer enquanto (! Stack1.Empty ())) {Stack2.push (Stack1.pop ()); // Abra o Dados no Stack1 e coloque -os no Stack2 [Core Code]}} if (Stack2.Empty ()) {// Quando o Stack2 está vazio, existem duas possibilidades: 1. No início, duas pilhas todos os dados estão vazios; Os dados no Stack2 são concluídos pela nova exceção ("Queu está vazio"); push (1); );Preste atenção à ordem do código na linha 22 e na linha 30, bem como aos comentários, e você precisa entender cuidadosamente seu significado.
Efeito de corrida:
4. Duas filas implementam uma pilha:
Ideias:
Coloque 1, 2 e 3 na fila 1, depois deixe o Top 3 na fila 1, coloque os 2 e 3 inferiores na fila 2 e coloque 3 da fila 1. Nesse momento, a fila está vazia e depois todos A fila 2 é deixada. . . Circular por sua vez.
Implementação de código:
importar java.util.arraydeque; importar java.util.queue;/*** criado por Smyhvae em 2015/9/9 <Teger> Queue2 = novo ArrayDeque <Teger> (); // Método: Operação de pilha public void push (int data) {Queue1.add (dados); int data; {Data = Queue1.poll (); Queue1.poll ()); = new Stack (); pilha.push (1); ));Efeito de corrida:
5. Projete uma pilha com a função mínima min () e requer que a complexidade do tempo de min, push, pop e tudo seja O (1). O objetivo do método Min é: ele pode retornar o valor mínimo na pilha. 【Perguntas da entrevista do WeChat】
Idéias comuns:
De um modo geral, podemos pensar desta maneira: usando a variável Min, toda vez que adicionamos um elemento, ela é comparada com o elemento Min, para que ele possa garantir que o valor mínimo armazenado em min possa ser garantido. Mas, neste caso, haverá um problema: se o menor elemento estiver fora da pilha, como você pode saber qual dos elementos restantes é o menor elemento?
Ideias para melhoria:
Aqui você precisa adicionar uma pilha auxiliar para trocar espaço pelo tempo. Na pilha auxiliar, a parte superior da pilha sempre economiza o menor valor na pilha atual. É específico: sempre que um novo elemento é adicionado na pilha original, é comparado com o elemento superior da pilha auxiliar O elemento é grande e copie o elemento superior da pilha auxiliar na parte superior da pilha auxiliar;
Implementação completa de código:
importar java.util.stack;/*** criado por smyhvae em 2015/9/9. New Stack <Teger> (); /No auxiliar if (Minstack.size () == 0 || Dados <Minstack.peek ()) {Minstack.push (dados); Código] O método Peek retorna o elemento na parte superior da pilha}} public int pop () lança exceção {if (Stack.size () == 0) {lança nova exceção ("vazia na pilha"); Data = Stack.pop (); Hollow ");} Return Minstack.Peek ();} public static void main (String [] args) lança exceção {Minstack Stack = new Minstack (); Stack.push (4); Stack.pus H (3); .push (5); System.out.println (Stack.min ());Efeito de corrida:
6. Determine se as seqüências de push e pop da pilha são consistentes:
Simplificando: sabe -se que um conjunto de dados 1, 2, 3, 4 e 5 são colocados na pilha em sequência, então existem muitas maneiras de divulgá -lo. ?
Por exemplo:
dados:
1, 2, 3, 4, 5
Saída 1:
5, 4, 3, 2, 1 (correto)
Saída 2:
4, 5, 3, 2, 1 (correto)
Saída 3:
4, 3, 5, 1, 2 (erro)
Código de versão completa:
importar java.util.stack;/*** criado por Smyhvae em 2015/9/9.
*/
classe pública Stacktest {
// Método: A ordem dos matrizes Data1 indica a ordem de empilhamento. Agora julgue se a ordem de empilhamento de dados2 está correta.
public estático booleano seqüenceispop (int [] data1, int [] data2) {
Pilha <Teger> pilha = nova pilha <TEGER> ();
for (int i = 0, j = 0; i <data1.length; i ++) {
Stack.push (data1 [i]);
while (Stack.size ()> 0 && Stack.peek () == Data2 [J]) {
Stack.pop ();
j ++;
}
}
return stack.size () == 0;
}
public static void main (string [] args) {
Stack <Teger> pilha = new Stack <Teger> ();
int [] data1 = {1, 2, 3, 4, 5};
int [] data2 = {4, 5, 3, 2, 1};
int [] data3 = {4, 5, 2, 3, 1};
System.out.println (sequenseispop (Data1, Data2));
System.out.println (sequenseispop (Data1, Data3));
}
}
O código é relativamente conciso, mas também é difícil de entender, então você precisa entendê -lo com cuidado.
Efeito de corrida:
Os acima são perguntas clássicas da entrevista sobre a pilha de java e as filas.