Bài báo
Bắt đầu
Bắt đầu học
JavaRush /Blog Java /Random-VI /Nghỉ giải lao #162. Triển khai ngăn xếp bằng cách sử dụng...
Эллеонора Керри
Mức độ

Nghỉ giải lao #162. Triển khai ngăn xếp bằng cách sử dụng hàng đợi. Các phương thức lớp Toán Java

Xuất bản trong nhóm

Triển khai ngăn xếp bằng hàng đợi

Nguồn: Hackernoon Nội dung của bài viết này được dành để giải quyết vấn đề triển khai một ngăn xếp chỉ sử dụng hai hàng đợi. Nghỉ giải lao #162. Triển khai ngăn xếp bằng cách sử dụng hàng đợi. Các phương thức lớp Toán Java - 1Chúng tôi gặp sự cố với Leetcode :

Triển khai ngăn xếp vào trước ra trước (LIFO) chỉ bằng hai hàng đợi. Ngăn xếp được triển khai phải hỗ trợ tất cả các chức năng của ngăn xếp thông thường ( push , top , pop vàempty ).

Triển khai lớp MyStack:

  • void push(int x) Đẩy phần tử x lên đầu ngăn xếp.

  • int pop() Xóa phần tử ở đầu ngăn xếp và trả về phần tử đó.

  • int top() Trả về phần tử ở đầu ngăn xếp.

  • boolean trống() Trả về true nếu ngăn xếp trống, ngược lại là false .

Chi tiết bổ sung:

  • Bạn chỉ nên sử dụng các hoạt động hàng đợi tiêu chuẩn, có nghĩa là chỉ cho phép các hoạt động đẩy về phía sau , nhìn trộm/bật từ phía trước , kích thước và là trống .

  • Tùy thuộc vào ngôn ngữ lập trình của bạn, hàng đợi có thể không được hỗ trợ nguyên bản. Nhưng bạn có thể mô phỏng hàng đợi bằng cách sử dụng danh sách hoặc deque (hàng đợi kép) nếu bạn chỉ sử dụng các thao tác hàng đợi tiêu chuẩn.

Ví dụ 1:

Đầu vào

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

đầu ra

[không, không, không, 2, 2, sai]

Giải trình

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

Giải pháp của vấn đề

Lựa chọn đầu tiên

Trong giải pháp đầu tiên, chúng tôi sẽ sử dụng bộ nhớ bổ sung: 
static class MyStack {
  private Queue<Integer> current;
  private Queue<Integer> tmp;

  public MyStack() {
    current = new ArrayDeque<>();
    tmp = new ArrayDeque<>();
  }
Chúng tôi cần một hàng đợi bổ sung cho giải pháp này. Hãy bắt đầu với đẩy . Đối với thao tác đẩy , chúng ta chỉ cần thêm một phần tử mới vào hàng đợi hiện tại. 
public void push(int x) {
  current.add(x);
}
Bí quyết chính ở đây là phương pháp pop . Ở đây chúng tôi đặt tất cả các phần tử ngoại trừ phần tử cuối cùng vào hàng đợi tmp . Và bây giờ phần tử cuối cùng trong hàng đợi sẽ trở thành phần tử đầu tiên được gửi. 
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;
}
Còn phương pháp hàng đầu thì sao ? Phương pháp này tương tự như 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;
}
Và đối với phương thức trống cuối cùng , chúng ta chỉ cần kiểm tra hàng đợi hiện tại: 
public boolean empty() {
  return current.isEmpty();
}

Giải pháp thứ hai

Trong tùy chọn này, chúng tôi sẽ không sử dụng bộ nhớ bổ sung: 
static class MyStack {

  private Queue<Integer> current;

  public MyStack2() {
    current = new ArrayDeque<>();
  }
}
Ý tưởng chính ở đây là phương pháp đẩy . Chúng ta thêm phần tử hiện tại và sau đó di chuyển các phần tử trước phần tử hiện tại đến cuối hàng đợi. Ví dụ: nếu chúng ta có một hàng đợi có các phần tử [2,1], chúng ta sử dụng push 3 - và nhận hàng đợi [3,2,1], sau đó là [1,3,2], [2,1,3] và. .. và tất cả. 
public void push(int x) {
  current.add(x);
  int size = current.size();

  for (int i = 0; i < size-1; i ++){
    current.add(current.poll());
  }
}
Ở đây chúng ta đã có phần tử chính xác và phần đầu của hàng đợi cho tất cả các phương thức khác. 
public int pop() {
  return current.poll();
}

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

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

Các phương thức lớp Toán Java

Nguồn: Medium Trong bài đăng này, bạn sẽ tìm hiểu về các khả năng và phạm vi của lớp Java Math. Nghỉ giải lao #162. Triển khai ngăn xếp bằng cách sử dụng hàng đợi. Các phương thức lớp toán học Java - 2Một phần của gói Java.lang.Math trong ngôn ngữ Java là lớp Math . Lớp này cung cấp cho chúng ta một số phương thức được xác định trước như min , max , sqrt và các phương thức khác. Dưới đây là ví dụ về một số phương pháp của lớp Toán mà chúng ta có thể sử dụng trong công việc hàng ngày. 1. Phương thức max() trả về số lớn hơn được truyền trong tham số: 
System.out.println(Math.max(5,3));
OUTPUT: 5
2. Phương thức sqrt() sẽ hiển thị cho chúng ta căn bậc hai của số được truyền dưới dạng đối số: 
System.out.println(Math.sqrt(4));
OUTPUT: 2.0
3. Phương thức Random() trả về một số ngẫu nhiên trong phạm vi từ 0 đến 1. 
System.out.println(Math.random());
OUTPUT: 0.8685304957692445
4. Phương thức abs() trả về giá trị dương tuyệt đối của bất kỳ số âm nào. Ví dụ: nếu chúng ta chuyển nó là 0 thì kết quả là nó sẽ trả về 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. Phương thức Floor() trả về một giá trị kép nhỏ hơn hoặc bằng đối số và bằng số nguyên toán học gần nhất. 
System.out.println(Math.floor(-1.2));
OUTPUT: -2.0
System.out.println(Math.floor(1.2));
OUTPUT: 2.0
Bình luận
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION