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

41 уровень

27 сентября 2022
2798 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

Комментарии

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ