JavaRush /Java Blog /Random-IT /Pausa caffè #162. Implementazione di uno stack utilizzand...

Livello 41

28 febbraio 2021
42 views
0 comments

Pausa caffè #162. Implementazione di uno stack utilizzando una coda. Metodi della classe Java Math

Implementazione di uno stack utilizzando una coda

Fonte: Hackernoon Il contenuto di questo articolo è dedicato alla risoluzione del problema dell'implementazione di uno stack utilizzando solo due code. Pausa caffè #162. Implementazione di uno stack utilizzando una coda. Metodi della classe Java Math - 1

Abbiamo un problema con Leecode :

Implementa uno stack LIFO (last-in-first-out) utilizzando solo due code. Lo stack implementato deve supportare tutte le funzioni di uno stack normale ( push , top , pop e empty ).

Implementa la classe MyStack:

void push(int x) Spinge l'elemento x in cima allo stack.
int pop() Rimuove l'elemento in cima allo stack e lo restituisce.
int top() Restituisce l'elemento in cima allo stack.
booleano vuoto() Restituisce vero se lo stack è vuoto, falso altrimenti .

Dettagli aggiuntivi:

Dovresti utilizzare solo operazioni di coda standard, il che significa che sono consentite solo operazioni push to back , peek/pop from front , size e is empty .
A seconda del linguaggio di programmazione, la coda potrebbe non essere supportata in modo nativo. Ma puoi simulare una coda utilizzando un elenco o una deque (doppia coda) se utilizzi solo operazioni di coda standard.

Esempio 1:

Ingresso

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

Produzione

[null, null, null, 2, 2, falso]

Spiegazione

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

La soluzione del problema

Prima opzione

Nella prima soluzione utilizzeremo memoria aggiuntiva:

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

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

Abbiamo bisogno di una coda aggiuntiva per questa soluzione. Cominciamo con la spinta . Per un'operazione push , aggiungiamo semplicemente un nuovo elemento alla nostra coda corrente.

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

Il trucco principale qui è il metodo pop . Qui inseriamo tutti gli elementi tranne l'ultimo nella coda tmp . E ora l'ultimo elemento della coda diventa il primo elemento inviato.

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 il metodo principale ? Questo metodo è simile 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;
}

E per l'ultimo metodo vuoto , dovremmo semplicemente controllare la coda corrente:

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

Seconda soluzione

In questa opzione non utilizzeremo memoria aggiuntiva:

static class MyStack {

  private Queue<Integer> current;

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

L'idea principale qui è il metodo push . Aggiungiamo l'elemento corrente e quindi spostiamo gli elementi prima di quello corrente alla fine della coda. Ad esempio, se abbiamo una coda con elementi [2,1], utilizziamo push 3 - e otteniamo coda [3,2,1], quindi [1,3,2], [2,1,3] e. .. e tutto.

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

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

Qui abbiamo già l'elemento corretto e l'inizio della coda per tutti gli altri metodi.

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

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

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

Metodi della classe Java Math

Fonte: Medium In questo post imparerai le capacità e l'ambito della classe Java Math. Pausa caffè #162. Implementazione di uno stack utilizzando una coda. Metodi di lezione di matematica Java - 2

Pausa caffè #162. Implementazione di uno stack utilizzando una coda. Metodi di lezione di matematica Java - 2

Parte del pacchetto Java.lang.Math nel linguaggio Java è la classe Math . Questa classe ci fornisce alcuni metodi predefiniti come min , max , sqrt e altri. Di seguito sono riportati esempi di alcuni metodi della classe Math che possiamo utilizzare nel nostro lavoro quotidiano. 1. Il metodo max() restituisce il numero maggiore passato nel parametro:

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

2. Il metodo sqrt() ci mostrerà la radice quadrata del numero passato come argomento:

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

3. Il metodo random() restituisce un numero casuale compreso tra 0 e 1.

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

4. Il metodo abs() restituisce il valore positivo assoluto di qualsiasi numero negativo. Ad esempio, se lo passiamo come 0, restituirà 0 come risultato.

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. Il metodo floor() restituisce un valore doppio minore o uguale all'argomento e uguale all'intero matematico più vicino.

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

Commenti

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