JavaRush /Blogue Java /Random-PT /Pausa para café #162. Implementação de uma pilha usando u...

Nível 41

28 fevereiro 2021
54 views
0 comments

Pausa para café #162. Implementação de uma pilha usando uma fila. Métodos de classe Java Math

Implementando uma pilha usando uma fila

Fonte: Hackernoon O conteúdo deste artigo é dedicado a resolver o problema de implementação de uma pilha usando apenas duas filas. Pausa para café #162. Implementação de uma pilha usando uma fila. Métodos de classe Java Math - 1

Pausa para café #162. Implementação de uma pilha usando uma fila. Métodos de classe Java Math - 1

Temos um problema com Leetcode :

Implemente uma pilha LIFO (último a entrar, primeiro a sair) usando apenas duas filas. A pilha implementada deve suportar todas as funções de uma pilha regular ( push , top , pop e empty ).

Implemente a classe MyStack:

void push(int x) Empurra o elemento x para o topo da pilha.
int pop() Remove o elemento do topo da pilha e o retorna.
int top() Retorna o elemento no topo da pilha.
boolean vazio() Retorna verdadeiro se a pilha estiver vazia, caso contrário , falso .

Detalhes adicionais:

Você deve usar apenas operações de fila padrão, o que significa que apenas operações push to back , peek/pop from front , size e is empty são permitidas .
Dependendo da sua linguagem de programação, a fila pode não ter suporte nativo. Mas você pode simular uma fila usando uma lista ou um deque (fila dupla) se usar apenas operações de fila padrão.

Exemplo 1:

Entrada

["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

Saída

[nulo, nulo, nulo, 2, 2, falso]

Explicação

MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // возвращает 2
myStack.pop(); // возвращает 2
myStack.empty(); // возвращает False

A solução do problema

Primeira opção

Na primeira solução usaremos memória adicional:

static class MyStack {
  private Queue<Integer> current;
  private Queue<Integer> tmp;

  public MyStack() {
    current = new ArrayDeque<>();
    tmp = new ArrayDeque<>();
  }

Precisamos de uma fila adicional para esta solução. Vamos começar com push . Para uma operação push , simplesmente adicionamos um novo elemento à nossa fila atual.

public void push(int x) {
  current.add(x);
}

O truque principal aqui é o método pop . Aqui colocamos todos os elementos, exceto o último, na fila tmp . E agora o último elemento da fila se torna o primeiro elemento enviado.

public int pop() {
  if (current.isEmpty()){
    return -1;
  }
  int size = current.size();
  for (int i = 0; i < size - 1; i ++){
    tmp.add(current.poll());
  }
  int ret = current.poll();
  current = tmp;
  return ret;
}

E o método superior ? Este método é semelhante ao pop :

public int top() {
  if (current.isEmpty()){
    return -1;
  }
  int size = current.size();
  for (int i = 0; i < size - 1; i ++){
    tmp.add(current.poll());
  }
  int ret = current.peek();
  tmp.add(current.poll());
  current = tmp;
  return ret;
}

E para o último método vazio , devemos simplesmente verificar a fila atual:

public boolean empty() {
  return current.isEmpty();
}

Segunda solução

Nesta opção não utilizaremos memória adicional:

static class MyStack {

  private Queue<Integer> current;

  public MyStack2() {
    current = new ArrayDeque<>();
  }
}

A ideia principal aqui é o método push . Adicionamos o elemento atual e então movemos os elementos anteriores ao atual para o final da fila. Por exemplo, se tivermos uma fila com elementos [2,1], usamos push 3 - e obtemos a fila [3,2,1], depois [1,3,2], [2,1,3] e. .. e tudo.

public void push(int x) {
  current.add(x);
  int size = current.size();

  for (int i = 0; i < size-1; i ++){
    current.add(current.poll());
  }
}

Aqui já temos o elemento correto e o início da fila para todos os outros métodos.

public int pop() {
  return current.poll();
}

public int top() {
  return current.peek();
}

public boolean empty() {
  return current.isEmpty();
}

Métodos de classe Java Math

Fonte: Médio Nesta postagem, você aprenderá sobre os recursos e o escopo da classe Java Math. Pausa para café #162. Implementação de uma pilha usando uma fila. Métodos de aula de matemática Java - 2

Pausa para café #162. Implementação de uma pilha usando uma fila. Métodos de aula de matemática Java - 2

Parte do pacote Java.lang.Math na linguagem Java é a classe Math . Esta classe nos fornece alguns métodos predefinidos como min , max , sqrt e outros. Abaixo estão exemplos de alguns métodos da classe Math que podemos usar em nosso trabalho diário. 1. O método max() retorna o maior número passado no parâmetro:

System.out.println(Math.max(5,3));
OUTPUT: 5

2. O método sqrt() nos mostrará a raiz quadrada do número passado como argumento:

System.out.println(Math.sqrt(4));
OUTPUT: 2.0

3. O método random() retorna um número aleatório no intervalo de 0 a 1.

System.out.println(Math.random());
OUTPUT: 0.8685304957692445

4. O método abs() retorna o valor positivo absoluto de qualquer número negativo. Por exemplo, se passarmos como 0, o resultado será 0.

System.out.println(Math.abs(-4));
OUTPUT: 4
System.out.println(Math.abs(4));
OUTPUT: 4
System.out.println(Math.abs(0));
OUTPUT: 0

5. O método floor() retorna um valor duplo que é menor ou igual ao argumento e igual ao número inteiro matemático mais próximo.

System.out.println(Math.floor(-1.2));
OUTPUT: -2.0
System.out.println(Math.floor(1.2));
OUTPUT: 2.0

Comentários

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION