JavaRush /Java блог /Random UA /Кава-брейк #162. Реалізація стека з використанням черги. ...

41 рівень

28 лютого 2021
50 views
0 comments

Кава-брейк #162. Реалізація стека з використанням черги. Методи класу Java Math

Реалізація стека з використанням черги

Джерело: Hackernoon Зміст цієї статті присвячено вирішенню завдання щодо реалізації стека з використанням лише двох черг. Кава-брейк #162. Реалізація стека з використанням черги. Методи класу Java Math - 1

Перед нами завдання з Leetcode :

Реалізуйте стек “останній прийшов – перший пішов” (last-in-first-out, LIFO), використовуючи лише дві черги. Реалізований стек повинен підтримувати всі функції звичайного стека ( push , top , pop та empty ).

Реалізуйте клас MyStack:

void push(int x) Поміщає елемент x на вершину стека.
int pop() Видаляє елемент на вершині стека та повертає його.
int top() Повертає елемент на вершині стека.
boolean empty() Повертає true , якщо стек порожній, інакше false .

Додаткові деталі:

Ви повинні використовувати лише стандартні операції черги, що означає допустимість тільки таких операцій, як push to back , peek/pop from front , size та is empty .
Залежно від вашої мови програмування, черга може не підтримуватися спочатку. Але ви можете імітувати чергу, використовуючи список або двосторонню чергу (подвійна черга), якщо ви використовуєте лише стандартні операції черги.

Приклад 1:

Input

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

Output

[null, null, null, 2, 2, false]

Explanation

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

Рішення завдання

Перший варіант

У першому варіанті рішення будемо використовувати додаткову пам'ять:

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

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

Нам потрібна додаткова черга для цього рішення. Почнемо з push . Для операції push ми просто додаємо новий елемент до нашої поточної черги.

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

Головний трюк тут полягає в методі pop . Тут ми поміщаємо всі елементи, крім останнього , в чергу tmp . І тепер останній елемент у черзі стає першим відправленим елементом.

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;
}

А що щодо методу top ? Цей метод схожий на 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;
}

І для останнього методу empty ми повинні просто перевірити поточну чергу:

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

Другий варіант вирішення

У цьому варіанті ми не будемо використовувати додаткову пам'ять:

static class MyStack {

  private Queue<Integer> current;

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

Основна ідея тут полягає в методі push . Ми додаємо поточний елемент, а потім переміщуємо елементи перед поточним на кінець черги. Наприклад, якщо у нас є черга з елементами [2,1], ми застосовуємо push 3 - і отримуємо чергу [3,2,1], потім [1,3,2], [2,1,3] та… і Усе.

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

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

Тут ми вже є правильний елемент і початок черги всім інших методів.

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

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

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

Методи класу Java Math

Джерело: Medium Завдяки цій публікації ви дізнаєтесь про можливості та сферу застосування класу Java Math. Кава-брейк #162. Реалізація стека з використанням черги. Методи класу Java Math - 2

Складовою частиною пакета Java.lang.Math у мові Java є клас Math . Цей клас надає нам деякі зумовлені методи, такі як min , max , sqrt та інші. Нижче наведено приклади деяких методів з класу Math , які ми можемо використовувати у повсякденній роботі. 1. Метод max() повертає більше, передане в параметрі:

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

2. Метод sqrt() покаже нам квадратний корінь із числа, переданого як аргумент:

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

3. Метод random() повертає довільне число в діапазоні від 0 до 1.

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

4. Метод abs() повертає абсолютне позитивне значення будь-якого негативного числа. Наприклад, якщо ми передаємо його як 0, то він поверне 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. Метод floor() повертає подвійне значення, яке менше або дорівнює аргументу і дорівнює найближчому математичному цілому числу.

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

Коментарі

ЩОБ ПОДИВИТИСЯ ВСІ КОМЕНТАРІ АБО ЗАЛИШИТИ КОМЕНТАР,
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ