JavaRush /Java Blog /Random EN /Coffee break #162. Implementation of a stack using a queu...

Level 41

28 February 2021
46 views
0 comments

Coffee break #162. Implementation of a stack using a queue. Java Math class methods

Implementing a stack using a queue

Source: Hackernoon The content of this article is devoted to solving the problem of implementing a stack using only two queues. Coffee break #162. Implementation of a stack using a queue. Java Math class methods - 1

Coffee break #162. Implementation of a stack using a queue. Java Math class methods - 1

We have a problem with Leetcode :

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack must support all the functions of a regular stack ( push , top , pop , and empty ).

Implement the MyStack class:

void push(int x) Push element x to the top of the stack.
int pop() Removes the element at the top of the stack and returns it.
int top() Returns the element at the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise .

Additional details:

You should only use standard queue operations, which means only push to back , peek/pop from front , size , and is empty operations are allowed .
Depending on your programming language, the queue may not be supported natively. But you can simulate a queue using a list or a deque (double queue) if you only use standard queue operations.

Example 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

The solution of the problem

First option

In the first solution we will use additional memory:

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

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

We need an additional queue for this solution. Let's start with push . For a push operation , we simply add a new element to our current queue.

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

The main trick here is the pop method . Here we put all elements except the last one into the tmp queue . And now the last element in the queue becomes the first element sent.

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

What about the top method ? This method is similar to 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;
}

And for the last empty method , we should simply check the current queue:

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

Second solution

In this option we will not use additional memory:

static class MyStack {

  private Queue<Integer> current;

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

The main idea here is the push method . We add the current element and then move the elements before the current one to the end of the queue. For example, if we have a queue with elements [2,1], we use push 3 - and get queue [3,2,1], then [1,3,2], [2,1,3] and... and All.

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

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

Here we already have the correct element and the beginning of the queue for all other methods.

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

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

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

Java Math class methods

Source: Medium In this post, you will learn about the capabilities and scope of the Java Math class. Coffee break #162. Implementation of a stack using a queue. Java Math Class Methods - 2

Part of the Java.lang.Math package in the Java language is the Math class . This class provides us with some predefined methods like min , max , sqrt and others. Below are examples of some methods from the Math class that we can use in our daily work. 1. The max() method returns the larger number passed in the parameter:

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

2. The sqrt() method will show us the square root of the number passed as an argument:

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

3. The random() method returns a random number in the range from 0 to 1.

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

4. The abs() method returns the absolute positive value of any negative number. For example, if we pass it as 0, it will return 0 as a result.

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. The floor() method returns a double value that is less than or equal to the argument and equal to the nearest mathematical integer.

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

Comments

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