JavaRush /Blog Java /Random-ES /Pausa para el café #162. Implementación de una pila media...

Nivel 41

28 febrero 2021
43 views
0 comments

Pausa para el café #162. Implementación de una pila mediante una cola. Métodos de clase de matemáticas de Java

Implementando una pila usando una cola

Fuente: Hackernoon El contenido de este artículo está dedicado a resolver el problema de implementar una pila utilizando solo dos colas. Pausa para el café #162. Implementación de una pila mediante una cola. Métodos de clase Java Math - 1

Pausa para el café #162. Implementación de una pila mediante una cola. Métodos de clase Java Math - 1

Tenemos un problema con Leetcode :

Implemente una pila de último en entrar, primero en salir (LIFO) utilizando solo dos colas. La pila implementada debe admitir todas las funciones de una pila normal ( empujar , arriba , abrir y vaciar ).

Implemente la clase MyStack:

void push(int x) Empuja el elemento x hacia la parte superior de la pila.
int pop() Elimina el elemento en la parte superior de la pila y lo devuelve.
int top() Devuelve el elemento en la parte superior de la pila.
boolean vacío() Devuelve verdadero si la pila está vacía, falso en caso contrario .

Detalles adicionales:

Solo debe usar operaciones de cola estándar, lo que significa que solo se permiten operaciones de empujar hacia atrás , mirar/pop desde el frente , tamaño y está vacío .
Dependiendo de su lenguaje de programación, es posible que la cola no sea compatible de forma nativa. Pero puedes simular una cola usando una lista o una deque (cola doble) si solo usas operaciones de cola estándar.

Ejemplo 1:

Aporte

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

Producción

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

Explicación

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

La solución del problema

Primera opción

En la primera solución usaremos memoria adicional:

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

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

Necesitamos una cola adicional para esta solución. Empecemos con el empujón . Para una operación de inserción , simplemente agregamos un nuevo elemento a nuestra cola actual.

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

El truco principal aquí es el método pop . Aquí colocamos todos los elementos excepto el último en la cola tmp . Y ahora el último elemento de la cola se convierte en el primer 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;
}

¿ Qué pasa con el método superior ? Este método es similar al 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;
}

Y para el último método vacío , simplemente deberíamos verificar la cola actual:

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

Segunda solución

En esta opción no utilizaremos memoria adicional:

static class MyStack {

  private Queue<Integer> current;

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

La idea principal aquí es el método push . Agregamos el elemento actual y luego movemos los elementos anteriores al actual al final de la cola. Por ejemplo, si tenemos una cola con elementos [2,1], usamos push 3 - y obtenemos la cola [3,2,1], luego [1,3,2], [2,1,3] y. .. y todo.

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

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

Aquí ya tenemos el elemento correcto y el comienzo de la cola para todos los demás métodos.

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

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

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

Métodos de clase de matemáticas de Java

Fuente: Medio En esta publicación, aprenderá sobre las capacidades y el alcance de la clase Java Math. Pausa para el café #162. Implementación de una pila mediante una cola. Métodos de clase de matemáticas de Java - 2

Parte del paquete Java.lang.Math en el lenguaje Java es la clase Math . Esta clase nos proporciona algunos métodos predefinidos como min , max , sqrt y otros. A continuación se muestran ejemplos de algunos métodos de la clase de Matemáticas que podemos utilizar en nuestro trabajo diario. 1. El método max() devuelve el número mayor pasado en el parámetro:

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

2. El método sqrt() nos mostrará la raíz cuadrada del número pasado como argumento:

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

3. El método random() devuelve un número aleatorio en el rango de 0 a 1.

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

4. El método abs() devuelve el valor positivo absoluto de cualquier número negativo. Por ejemplo, si lo pasamos como 0, devolverá 0 como resultado.

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. El método Floor() devuelve un valor doble que es menor o igual que el argumento e igual al entero matemático más cercano.

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

Comentarios

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