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