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](https://cdn.javarush.com/images/article/7c3a816d-de0f-44eb-8e8a-095243494705/800.jpeg)
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:
Detalles adicionales:
Ejemplo 1: Aporte
Producción
[nulo, nulo, nulo, 2, 2, falso]
Explicación
|
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](https://cdn.javarush.com/images/article/1a49ba9b-30ad-400f-ab4f-265e5ff1ef1d/800.jpeg)
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
GO TO FULL VERSION