Реализация стека с использованием очереди

Источник: 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
Python-университет

Решение задачи

Первый вариант

В первом варианте решения будем использовать дополнительную память: 

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() возвращает большее число, переданное в параметре:
Telegram 

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