Artykuł
Rozpocznij
Rozpocznij naukę
JavaRush /Blog Java /Random-PL /Przerwa kawowa #162. Implementacja stosu przy użyciu kole...
Эллеонора Керри
Poziom 41

Przerwa kawowa #162. Implementacja stosu przy użyciu kolejki. Metody klas Java Math

Opublikowano w grupie Random-PL

Implementacja stosu przy użyciu kolejki

Źródło: Hackernoon Treść artykułu poświęcona jest rozwiązaniu problemu implementacji stosu przy użyciu tylko dwóch kolejek. Przerwa kawowa #162. Implementacja stosu przy użyciu kolejki. Metody klasy Java Math - 1Mamy problem z Leetcode :

Zaimplementuj stos „ostatnie weszło, pierwsze wyszło” (LIFO) przy użyciu tylko dwóch kolejek. Zaimplementowany stos musi obsługiwać wszystkie funkcje zwykłego stosu ( push , top , pop i pusty ).

Zaimplementuj klasę MyStack:

  • void push(int x) Wysuń element x na szczyt stosu.

  • int pop() Usuwa element ze szczytu stosu i zwraca go.

  • int top() Zwraca element na szczycie stosu.

  • boolean pusty() Zwraca wartość true , jeśli stos jest pusty, w przeciwnym razie wartość false .

Dodatkowe Szczegóły:

  • Powinieneś używać tylko standardowych operacji kolejkowych, co oznacza, że ​​dozwolone są tylko operacje push to back , peek/pop od przodu , size i is pusty .

  • W zależności od języka programowania kolejka może nie być obsługiwana natywnie. Ale możesz symulować kolejkę za pomocą listy lub deque (podwójnej kolejki), jeśli używasz tylko standardowych operacji na kolejkach.

Przykład 1:

Wejście

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

Wyjście

[null, null, null, 2, 2, fałsz]

Wyjaśnienie

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

Rozwiązanie problemu

Pierwsza opcja

W pierwszym rozwiązaniu wykorzystamy dodatkową pamięć: 
static class MyStack {
  private Queue<Integer> current;
  private Queue<Integer> tmp;

  public MyStack() {
    current = new ArrayDeque<>();
    tmp = new ArrayDeque<>();
  }
Do tego rozwiązania potrzebujemy dodatkowej kolejki. Zacznijmy od pchnięcia . W przypadku operacji wypychania po prostu dodajemy nowy element do naszej bieżącej kolejki. 
public void push(int x) {
  current.add(x);
}
Główną sztuczką jest metoda pop . Tutaj umieszczamy wszystkie elementy oprócz ostatniego w kolejce tmp . I teraz ostatni element w kolejce staje się pierwszym wysłanym elementem. 
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;
}
A co z najlepszą metodą ? Ta metoda jest podobna do metody 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;
}
A w przypadku ostatniej pustej metody powinniśmy po prostu sprawdzić bieżącą kolejkę: 
public boolean empty() {
  return current.isEmpty();
}

Drugie rozwiązanie

W tej opcji nie będziemy używać dodatkowej pamięci: 
static class MyStack {

  private Queue<Integer> current;

  public MyStack2() {
    current = new ArrayDeque<>();
  }
}
Główną ideą jest tutaj metoda push . Dodajemy bieżący element, a następnie przesuwamy elementy poprzedzające bieżący na koniec kolejki. Przykładowo jeśli mamy kolejkę z elementami [2,1] to używamy push 3 - i pobieramy kolejkę [3,2,1], następnie [1,3,2], [2,1,3] i. .. i wszystkich. 
public void push(int x) {
  current.add(x);
  int size = current.size();

  for (int i = 0; i < size-1; i ++){
    current.add(current.poll());
  }
}
Tutaj mamy już poprawny element i początek kolejki dla wszystkich pozostałych metod. 
public int pop() {
  return current.poll();
}

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

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

Metody klas Java Math

Źródło: Medium W tym poście poznasz możliwości i zakres klasy Java Math. Przerwa kawowa #162. Implementacja stosu przy użyciu kolejki. Metody zajęć matematycznych w języku Java — 2Częścią pakietu Java.lang.Math w języku Java jest klasa Math . Ta klasa udostępnia nam kilka predefiniowanych metod, takich jak min , max , sqrt i inne. Poniżej znajdują się przykłady niektórych metod z klasy Math , które możemy wykorzystać w naszej codziennej pracy. 1. Metoda max() zwraca większą liczbę przekazaną w parametrze: 
System.out.println(Math.max(5,3));
OUTPUT: 5
2. Metoda sqrt() pokaże nam pierwiastek kwadratowy z liczby przekazanej jako argument: 
System.out.println(Math.sqrt(4));
OUTPUT: 2.0
3. Metoda random() zwraca liczbę losową z zakresu od 0 do 1. 
System.out.println(Math.random());
OUTPUT: 0.8685304957692445
4. Metoda abs() zwraca bezwzględną wartość dodatnią dowolnej liczby ujemnej. Na przykład, jeśli przekażemy ją jako 0, w rezultacie zwróci 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. Metoda Floor() zwraca wartość typu double, która jest mniejsza lub równa argumentowi i równa najbliższej matematycznej liczbie całkowitej. 
System.out.println(Math.floor(-1.2));
OUTPUT: -2.0
System.out.println(Math.floor(1.2));
OUTPUT: 2.0
Komentarze
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION