기사
시작
학습 시작
JavaRush /Java Blog /Random-KO /커피 브레이크 #162. 큐를 이용한 스택 구현. Java 수학 클래스 메소드
Эллеонора Керри
레벨 41

커피 브레이크 #162. 큐를 이용한 스택 구현. Java 수학 클래스 메소드

Random-KO 그룹에 게시되었습니다

큐를 사용하여 스택 구현

출처: Hackernoon 이 기사의 내용은 두 개의 큐만 사용하여 스택을 구현하는 문제를 해결하는 데 전념합니다. Leetcode에 문제가커피 브레이크 #162. 큐를 이용한 스택 구현. Java Math 클래스 메소드 - 1 있습니다 .

두 개의 대기열만 사용하여 LIFO(후입선출) 스택을 구현합니다. 구현된 스택은 일반 스택의 모든 기능( push , top , pop 및 empty )을 지원해야 합니다.

MyStack 클래스를 구현합니다.

  • void push(int x) 요소 x를 스택의 맨 위로 밀어 넣습니다.

  • int pop() 스택의 맨 위에 있는 요소를 제거하고 반환합니다.

  • int top() 스택의 맨 위에 있는 요소를 반환합니다.

  • booleanempty() 스택이 비어 있으면 true를 반환하고 , 그렇지 않으면 false를 반환합니다 .

추가 세부 사항:

  • 표준 대기열 작업만 사용해야 합니다. 즉, push to back , peek/pop from front , size 및 isempt 작업만 허용됩니다 .

  • 프로그래밍 언어에 따라 대기열이 기본적으로 지원되지 않을 수 있습니다. 그러나 표준 대기열 작업만 사용하는 경우 목록이나 deque(이중 대기열)를 사용하여 대기열을 시뮬레이션할 수 있습니다.

예시 1:

입력

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

산출

[널, 널, 널, 2, 2, 거짓]

설명

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

문제의 해결

첫 번째 옵션

첫 번째 솔루션에서는 추가 메모리를 사용합니다. 
static class MyStack {
  private Queue<Integer> current;
  private Queue<Integer> tmp;

  public MyStack() {
    current = new ArrayDeque<>();
    tmp = new ArrayDeque<>();
  }
이 솔루션에는 추가 대기열이 필요합니다. 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;
}
최고의 방법은 어떻습니까 ? 이 방법은 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;
}
그리고 마지막 빈 메소드에 대해서는 간단히 현재 큐를 확인해야 합니다. 
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 수학 클래스 메소드

출처: Medium 이 게시물에서는 Java Math 클래스의 기능과 범위에 대해 알아봅니다. Java 언어의 Java.lang.Math커피 브레이크 #162. 큐를 이용한 스택 구현. Java 수학 클래스 메소드 - 2 패키지 의 일부는 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() 메서드는 인수보다 작거나 같고 가장 가까운 수학 정수와 같은 double 값을 반환합니다. 
System.out.println(Math.floor(-1.2));
OUTPUT: -2.0
System.out.println(Math.floor(1.2));
OUTPUT: 2.0
코멘트
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION