[Java] Ngăn xếp và Hàng đợi

1. Định nghĩa một nút
Để đơn giản, ta chỉ định nghĩa một nút có giá trị kiểu int:

//Chương trình 1a
public class Node{
 private int value;
 /* Các phương thức khởi dựng */
 public Node(){
  value = 0;
 }
 public Node(int value){
  this.value = value;
 }
 /* Phương thức truy nhập thuộc tính value */
 public int getValue(){
  return value;
 }
 public void setValue(int value){
  this.value = value;
 }
}

2. Ngăn xếp
Ngăn xếp (stack) có các thuộc tính cục bộ:
•  Mảng lưu các nút của ngăn xếp
Các thao tác đối với ngăn xếp:
•  Thêm vào một nút
•  Lấy ra một nút
Cài đặt ngăn xếp
•  Ta coi đỉnh ngăn xếp là cuối mảng lưu giữ các nút. Do đó, các thao tác thêm vào và lấy ra sẽ thêm vào cuối mảng hoặc lấy nút ở cuối mảng ra.
•  Mảng các giá trị được khai báo động để tiết kiệm bộ nhớ.

//Chương trình 1b
public class MyStack{
 private Node[] values;
 /* Các phương thức khởi dựng */
 public MyStack(){}
 public MyStack(Node[] values){
  this.values = values;
 }
 /* Phương thức lấy ra một node từstack */
 public Node pop(){
  Node result = null;
  if ((values != null) && (values.length > 0)){
   result = values[values.length - 1];
   // Loại bỏnode cuối cùng 
   Node[] tmpNode = new Node[values.length - 1];
   for (int i = 0; i < values.length – 1; i++)
    tmpNode[i] = values[i];
   this.values = tmpNode;
  }
  return result;
 }
 /* Phương thức thêm một node vào stack */
 public void push(Node node){
  if (values == null){ // Ngăn xếp đang rỗng 
   values = new Node[1];
   values[0] = node;
  }
  else{ // Ngăn xếp đã có dữliệu 
   Node[] tmpNode = new Node[values.length + 1];
   for (int i = 0; i < values.length; i++)
    tmpNode[i] = values[i];
   tmpNode[values.length] = node;
   this.values = tmpNode;
  }
 }
}

3. Hàng đợi
Hàng đợi (queue) có các thuộc tính cục bộ:
•  Mảng các giá trị trong hàng đợi
Các thao tác với hàng đợi:
•  Thêm vào một nút vào cuối hàng đợi
•  Lấy ra một nút từ đầu hàng đợi
Chương trình 2 cài đặt lớp hàng đợi

//Chương trình 2
public class MyQueu{
 private Node[] values;
 /* Các phương thức khởi dựng */
 public MyQueu(){}
 public MyQueu(Node[] values){
  this.values = values;
 }
 /* Phương thức lấy ra một node từ đầu queu */
 public Node remove(){
  Node result = null;
  if ((values != null) && (values.length > 0)){
   result = values[0];
   // Loại bỏnode đầu hàng đợi 
   Node[] tmpNode = new Node[values.length - 1];
   for (int i = 0; i<values.length – 1; i++)
    tmpNode[i] = values[i + 1];
   this.values = tmpNode;
  }
  return result;
 }
 /* Phương thức thêm một node vào cuối queu */
 public void insert(Node node){
  if (values == null){ // Hàng đợi đang rỗng 
   values = new Node[1];
   values[0] = node;
  }
  else{ // Hàng đợi đã có dữliệu 
   Node[] tmpNode = new Node[values.length + 1];
   for (int i = 0; i<values.length; i++)
    tmpNode[i] = values[i];
   tmpNode[values.length] = node;
   this.values = tmpNode;
  }
 }
}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.