public class ArrayStack {
private int maxSize;
private int[] stackArray;
private int top;
// Khởi tạo stack
public ArrayStack(int size) {
maxSize = size;
stackArray = new int[maxSize];
top = -1; // Stack trống
}
// Thêm phần tử vào đỉnh stack
public void push(int value) {
if (top == maxSize - 1) {
System.out.println("Stack đầy!");
return;
}
stackArray[++top] = value;
}
// Lấy phần tử khỏi đỉnh stack
public int pop() {
if (top == -1) {
System.out.println("Stack trống!");
return -1;
}
return stackArray[top--];
}
// Xem phần tử ở đỉnh mà không xóa
public int peek() {
if (top == -1) {
System.out.println("Stack trống!");
return -1;
}
return stackArray[top];
}
// Kiểm tra stack có trống không
public boolean isEmpty() {
return (top == -1);
}
// Kiểm tra stack có đầy không
public boolean isFull() {
return (top == maxSize - 1);
}
}
public class LinkedStack {
private class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
private Node top;
public LinkedStack() {
top = null;
}
// Thêm vào đỉnh stack
public void push(int value) {
Node newNode = new Node(value);
newNode.next = top;
top = newNode;
}
// Lấy từ đỉnh stack
public int pop() {
if (isEmpty()) {
System.out.println("Stack trống!");
return -1;
}
int value = top.data;
top = top.next;
return value;
}
// Xem đỉnh stack
public int peek() {
if (isEmpty()) {
System.out.println("Stack trống!");
return -1;
}
return top.data;
}
// Kiểm tra stack có trống không
public boolean isEmpty() {
return top == null;
}
}
public boolean isBalanced(String expression) {
LinkedStack stack = new LinkedStack();
for (char c : expression.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty()) {
return false;
}
char top = (char) stack.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
}
public String reverse(String str) {
LinkedStack stack = new LinkedStack();
// Đẩy tất cả ký tự vào stack
for (char c : str.toCharArray()) {
stack.push(c);
}
// Lấy từng ký tự khỏi stack để tạo chuỗi đảo ngược
StringBuilder reversed = new StringBuilder();
while (!stack.isEmpty()) {
reversed.append((char)stack.pop());
}
return reversed.toString();
}
public String infixToPostfix(String infix) {
StringBuilder postfix = new StringBuilder();
java.util.Stack<Character> stack = new java.util.Stack<>();
for (char c : infix.toCharArray()) {
// Nếu là toán hạng, thêm vào chuỗi kết quả
if (Character.isLetterOrDigit(c)) {
postfix.append(c);
}
// Nếu là dấu mở ngoặc, đẩy vào stack
else if (c == '(') {
stack.push(c);
}
// Nếu là dấu đóng ngoặc, lấy từ stack đến khi gặp dấu mở ngoặc
else if (c == ')') {
while (!stack.isEmpty() && stack.peek() != '(') {
postfix.append(stack.pop());
}
stack.pop(); // Loại bỏ '('
}
// Nếu là toán tử, so sánh độ ưu tiên với toán tử ở đỉnh stack
else {
while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek())) {
postfix.append(stack.pop());
}
stack.push(c);
}
}
// Đẩy các toán tử còn lại trong stack vào chuỗi kết quả
while (!stack.isEmpty()) {
postfix.append(stack.pop());
}
return postfix.toString();
}
// Xác định độ ưu tiên toán tử
private int precedence(char ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
public class CircularQueue {
private int maxSize;
private int[] queueArray;
private int front;
private int rear;
private int nItems;
public CircularQueue(int size) {
maxSize = size;
queueArray = new int[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
// Thêm vào cuối queue
public void enqueue(int value) {
if (isFull()) {
System.out.println("Queue đầy!");
return;
}
// Tăng rear và quay vòng nếu cần
rear = (rear + 1) % maxSize;
queueArray[rear] = value;
nItems++;
}
// Lấy từ đầu queue
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue trống!");
return -1;
}
int temp = queueArray[front];
front = (front + 1) % maxSize;
nItems--;
return temp;
}
// Xem phần tử đầu queue
public int peek() {
if (isEmpty()) {
System.out.println("Queue trống!");
return -1;
}
return queueArray[front];
}
// Kiểm tra queue có trống không
public boolean isEmpty() {
return (nItems == 0);
}
// Kiểm tra queue có đầy không
public boolean isFull() {
return (nItems == maxSize);
}
// Kích thước hiện tại của queue
public int size() {
return nItems;
}
}
public class LinkedQueue {
private class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
private Node front;
private Node rear;
public LinkedQueue() {
front = null;
rear = null;
}
// Thêm vào cuối queue
public void enqueue(int value) {
Node newNode = new Node(value);
// Nếu queue trống
if (rear == null) {
front = newNode;
rear = newNode;
return;
}
// Thêm vào sau rear và cập nhật rear
rear.next = newNode;
rear = newNode;
}
// Lấy từ đầu queue
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue trống!");
return -1;
}
// Lưu giá trị cần trả về
int value = front.data;
// Di chuyển front
front = front.next;
// Nếu front trở thành null, cập nhật cả rear
if (front == null) {
rear = null;
}
return value;
}
// Xem phần tử đầu queue
public int peek() {
if (isEmpty()) {
System.out.println("Queue trống!");
return -1;
}
return front.data;
}
// Kiểm tra queue có trống không
public boolean isEmpty() {
return front == null;
}
}
public void BFS(Graph graph, int startVertex) {
// Đánh dấu tất cả các đỉnh chưa thăm
boolean[] visited = new boolean[graph.getVertexCount()];
// Tạo queue
LinkedQueue queue = new LinkedQueue();
// Đánh dấu đỉnh hiện tại đã thăm
visited[startVertex] = true;
queue.enqueue(startVertex);
while (!queue.isEmpty()) {
// Lấy một đỉnh từ queue và in ra
int vertex = queue.dequeue();
System.out.print(vertex + " ");
// Lấy tất cả các đỉnh kề của đỉnh lấy ra
// Nếu đỉnh kề chưa được thăm, đánh dấu đã thăm và thêm vào queue
for (int adjVertex : graph.getAdjVertices(vertex)) {
if (!visited[adjVertex]) {
visited[adjVertex] = true;
queue.enqueue(adjVertex);
}
}
}
}
public class CustomerService {
private LinkedQueue queue;
private int maxWaitTime;
public CustomerService() {
queue = new LinkedQueue();
maxWaitTime = 0;
}
// Khách hàng mới đến
public void customerArrival(int customerId, int arrivalTime) {
System.out.println("Khách hàng " + customerId + " đến lúc " + arrivalTime);
queue.enqueue(customerId);
}
// Phục vụ khách hàng
public void serveCustomer(int currentTime) {
if (!queue.isEmpty()) {
int customerId = queue.dequeue();
int waitTime = currentTime - customerId;
maxWaitTime = Math.max(maxWaitTime, waitTime);
System.out.println("Phục vụ khách hàng " + customerId + " lúc " + currentTime);
System.out.println("Thời gian chờ: " + waitTime);
} else {
System.out.println("Không có khách hàng chờ.");
}
}
// Lấy thời gian chờ tối đa
public int getMaxWaitTime() {
return maxWaitTime;
}
}
public void levelOrderTraversal(Node root) {
if (root == null) {
return;
}
LinkedQueue queue = new LinkedQueue();
queue.enqueue(root);
while (!queue.isEmpty()) {
Node current = (Node)queue.dequeue();
System.out.print(current.data + " ");
if (current.left != null) {
queue.enqueue(current.left);
}
if (current.right != null) {
queue.enqueue(current.right);
}
}
}
public class DoublyLinkedList {
private class Node {
int data;
Node prev;
Node next;
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
private Node head;
private Node tail;
public DoublyLinkedList() {
head = null;
tail = null;
}
// Thêm vào đầu danh sách
public void insertAtFront(int data) {
Node newNode = new Node(data);
// Nếu danh sách trống
if (head == null) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
}
// Thêm vào cuối danh sách
public void insertAtEnd(int data) {
Node newNode = new Node(data);
// Nếu danh sách trống
if (tail == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
// Xóa nút từ đầu danh sách
public int removeFromFront() {
if (head == null) {
System.out.println("Danh sách trống!");
return -1;
}
int data = head.data;
// Nếu chỉ có một nút
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
head.prev = null;
}
return data;
}
// Xóa nút từ cuối danh sách
public int removeFromEnd() {
if (tail == null) {
System.out.println("Danh sách trống!");
return -1;
}
int data = tail.data;
// Nếu chỉ có một nút
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.prev;
tail.next = null;
}
return data;
}
// In danh sách từ đầu đến cuối
public void displayForward() {
Node current = head;
System.out.print("null <-> ");
while (current != null) {
System.out.print(current.data + " <-> ");
current = current.next;
}
System.out.println("null");
}
// In danh sách từ cuối đến đầu
public void displayBackward() {
Node current = tail;
System.out.print("null <-> ");
while (current != null) {
System.out.print(current.data + " <-> ");
current = current.prev;
}
System.out.println("null");
}
}
public class CircularLinkedList {
private class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head;
private Node tail;
public CircularLinkedList() {
head = null;
tail = null;
}
// Thêm vào đầu danh sách
public void insertAtFront(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
tail.next = head; // Tạo liên kết vòng
} else {
newNode.next = head;
head = newNode;
tail.next = head; // Cập nhật liên kết vòng
}
}
// Thêm vào cuối danh sách
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (tail == null) {
head = newNode;
tail = newNode;
tail.next = head; // Tạo liên kết vòng
} else {
tail.next = newNode;
tail = newNode;
tail.next = head; // Cập nhật liên kết vòng
}
}
// Xóa từ đầu danh sách
public int removeFromFront() {
if (head == null) {
System.out.println("Danh sách trống!");
return -1;
}
int data = head.data;
// Nếu chỉ có một nút
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
tail.next = head; // Cập nhật liên kết vòng
}
return data;
}
// In danh sách
public void display() {
if (head == null) {
System.out.println("Danh sách trống!");
return;
}
Node current = head;
do {
System.out.print(current.data + " -> ");
current = current.next;
} while (current != head);
System.out.println(" (quay lại " + head.data + ")");
}
}
public class BrowserHistory {
private DoublyLinkedList history;
private Node currentPage;
private class Node {
String url;
Node prev;
Node next;
public Node(String url) {
this.url = url;
this.prev = null;
this.next = null;
}
}
public BrowserHistory(String homepage) {
currentPage = new Node(homepage);
}
// Truy cập trang mới
public void visit(String url) {
Node newPage = new Node(url);
newPage.prev = currentPage;
currentPage.next = newPage;
currentPage = newPage;
System.out.println("Đã truy cập: " + url);
}
// Quay lại trang trước
public String back() {
if (currentPage.prev != null) {
currentPage = currentPage.prev;
return currentPage.url;
} else {
return currentPage.url; // Không thể quay lại
}
}
// Đi tới trang sau
public String forward() {
if (currentPage.next != null) {
currentPage = currentPage.next;
return currentPage.url;
} else {
return currentPage.url; // Không thể đi tiếp
}
}
}
public class RoundRobinScheduler {
private CircularLinkedList processes;
public RoundRobinScheduler() {
processes = new CircularLinkedList();
}
// Thêm tiến trình mới
public void addProcess(int processId) {
processes.insertAtEnd(processId);
System.out.println("Đã thêm tiến trình " + processId);
}
// Chạy lập lịch round robin
public void run(int timeQuantum) {
System.out.println("Bắt đầu lập lịch Round-Robin với quantum thời gian = " + timeQuantum);
// Mô phỏng 10 chu kỳ lập lịch
for (int i = 0; i < 10; i++) {
int processId = processes.removeFromFront();
System.out.println("Chạy tiến trình " + processId + " trong " + timeQuantum + "ms");
// Sau khi chạy, đưa tiến trình lại cuối hàng đợi
processes.insertAtEnd(processId);
// Mô phỏng thời gian chạy
try {
Thread.sleep(timeQuantum * 10); // Mô phỏng chậm
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
public class BinarySearchTree {
private class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
private Node root;
public BinarySearchTree() {
root = null;
}
// Thêm một giá trị vào BST
public void insert(int value) {
root = insertRec(root, value);
}
private Node insertRec(Node root, int value) {
// Nếu cây rỗng, trả về nút mới
if (root == null) {
return new Node(value);
}
// Nếu không, đệ quy xuống cây
if (value < root.data) {
root.left = insertRec(root.left, value);
} else if (value > root.data) {
root.right = insertRec(root.right, value);
}
return root;
}
// Tìm kiếm một giá trị trong BST
public boolean search(int value) {
return searchRec(root, value);
}
private boolean searchRec(Node root, int value) {
// Điều kiện cơ sở: cây rỗng hoặc tìm thấy giá trị
if (root == null) {
return false;
}
if (root.data == value) {
return true;
}
// Giá trị nhỏ hơn -> tìm kiếm cây con bên trái
if (value < root.data) {
return searchRec(root.left, value);
}
// Ngược lại, tìm kiếm cây con bên phải
return searchRec(root.right, value);
}
// Xóa một giá trị khỏi BST
public void delete(int value) {
root = deleteRec(root, value);
}
private Node deleteRec(Node root, int value) {
// Điều kiện cơ sở
if (root == null) {
return root;
}
// Tìm nút cần xóa
if (value < root.data) {
root.left = deleteRec(root.left, value);
} else if (value > root.data) {
root.right = deleteRec(root.right, value);
} else {
// Nút có một hoặc không có con
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}
// Nút có hai con: tìm phần tử nhỏ nhất của cây con bên phải
root.data = minValue(root.right);
// Xóa phần tử nhỏ nhất của cây con bên phải
root.right = deleteRec(root.right, root.data);
}
return root;
}
private int minValue(Node root) {
int minValue = root.data;
while (root.left != null) {
minValue = root.left.data;
root = root.left;
}
return minValue;
}
// Duyệt cây theo thứ tự trung (Inorder traversal): trái -> gốc -> phải
public void inorder() {
inorderRec(root);
System.out.println();
}
private void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.data + " ");
inorderRec(root.right);
}
}
// Duyệt cây theo thứ tự trước (Preorder traversal): gốc -> trái -> phải
public void preorder() {
preorderRec(root);
System.out.println();
}
private void preorderRec(Node root) {
if (root != null) {
System.out.print(root.data + " ");
preorderRec(root.left);
preorderRec(root.right);
}
}
// Duyệt cây theo thứ tự sau (Postorder traversal): trái -> phải -> gốc
public void postorder() {
postorderRec(root);
System.out.println();
}
private void postorderRec(Node root) {
if (root != null) {
postorderRec(root.left);
postorderRec(root.right);
System.out.print(root.data + " ");
}
}
}
public class HashTable {
private class HashNode {
String key;
int value;
HashNode next;
public HashNode(String key, int value) {
this.key = key;
this.value = value;
this.next = null;
}
}
private HashNode[] buckets;
private int numBuckets;
private int size;
public HashTable() {
this(10); // Default size
}
public HashTable(int capacity) {
numBuckets = capacity;
buckets = new HashNode[numBuckets];
size = 0;
}
// Hàm băm
private int hashFunction(String key) {
int hashCode = key.hashCode();
return Math.abs(hashCode) % numBuckets;
}
// Kích thước bảng băm
public int size() {
return size;
}
// Kiểm tra bảng băm có trống không
public boolean isEmpty() {
return size() == 0;
}
// Thêm phần tử vào bảng băm
public void put(String key, int value) {
// Tìm chỉ số bucket từ khóa
int bucketIndex = hashFunction(key);
HashNode head = buckets[bucketIndex];
// Kiểm tra nếu khóa đã tồn tại, thì cập nhật giá trị
while (head != null) {
if (head.key.equals(key)) {
head.value = value;
return;
}
head = head.next;
}
// Thêm nút mới vào đầu danh sách liên kết
size++;
head = buckets[bucketIndex];
HashNode newNode = new HashNode(key, value);
newNode.next = head;
buckets[bucketIndex] = newNode;
}
// Lấy giá trị từ khóa
public int get(String key) {
// Tìm chỉ số bucket từ khóa
int bucketIndex = hashFunction(key);
HashNode head = buckets[bucketIndex];
// Tìm kiếm khóa trong danh sách liên kết
while (head != null) {
if (head.key.equals(key)) {
return head.value;
}
head = head.next;
}
// Khóa không tồn tại
return -1;
}
// Xóa phần tử với khóa cụ thể
public int remove(String key) {
// Tìm chỉ số bucket từ khóa
int bucketIndex = hashFunction(key);
HashNode head = buckets[bucketIndex];
HashNode prev = null;
// Tìm kiếm khóa trong danh sách liên kết
while (head != null) {
if (head.key.equals(key)) {
break;
}
prev = head;
head = head.next;
}
// Nếu khóa không tồn tại
if (head == null) {
return -1;
}
// Giảm kích thước
size--;
// Xóa nút
if (prev != null) {
prev.next = head.next;
} else {
buckets[bucketIndex] = head.next;
}
return head.value;
}
// In bảng băm
public void display() {
for (int i = 0; i < numBuckets; i++) {
System.out.print("Bucket " + i + ": ");
HashNode current = buckets[i];
while (current != null) {
System.out.print("(" + current.key + ":" + current.value + ") ");
current = current.next;
}
System.out.println();
}
}
}
// Ví dụ sử dụng bảng băm làm từ điển
public class Dictionary {
private HashTable hashTable;
public Dictionary() {
hashTable = new HashTable(100);
}
// Thêm từ vào từ điển
public void addWord(String word, int meaning) {
hashTable.put(word, meaning);
System.out.println("Đã thêm từ \"" + word + "\" vào từ điển.");
}
// Tra cứu từ
public void lookupWord(String word) {
int meaning = hashTable.get(word);
if (meaning != -1) {
System.out.println("Nghĩa của \"" + word + "\": " + meaning);
} else {
System.out.println("Từ \"" + word + "\" không có trong từ điển.");
}
}
// Xóa từ
public void removeWord(String word) {
int result = hashTable.remove(word);
if (result != -1) {
System.out.println("Đã xóa từ \"" + word + "\" khỏi từ điển.");
} else {
System.out.println("Từ \"" + word + "\" không có trong từ điển.");
}
}
// Hiển thị tất cả các từ
public void displayDictionary() {
System.out.println("Từ điển:");
hashTable.display();
}
}
Viết chương trình cho phép người dùng:
BỘ ĐÁNH GIÁ BIỂU THỨC SỐ HỌC
-----------------------------------
Nhập biểu thức (nhập 'exit' để thoát): 3 + 4 * 2 - (6 / 3)
Biểu thức trung tố: 3 + 4 * 2 - (6 / 3)
Biểu thức hậu tố: 3 4 2 * + 6 3 / -
Kết quả: 9
Nhập biểu thức (nhập 'exit' để thoát): 5 * (3 + 2) - 4 ^ 2
Biểu thức trung tố: 5 * (3 + 2) - 4 ^ 2
Biểu thức hậu tố: 5 3 2 + * 4 2 ^ -
Kết quả: 9
Nhập biểu thức (nhập 'exit' để thoát): 10 / (3 - 3)
Biểu thức trung tố: 10 / (3 - 3)
Biểu thức hậu tố: 10 3 3 - /
Lỗi: Chia cho 0!
Nhập biểu thức (nhập 'exit' để thoát): exit
Cảm ơn bạn đã sử dụng chương trình!
⬅️ Trở lại: DSA/Part1.md | 🏠 Home | ➡️ Tiếp theo: DSA/Part2.md