Em Fresher Học Cấu Trúc Dữ Liệu Và Giải Thuật (P2)
Câu chuyện em fresher học Cấu trúc dữ liệu và giải thuật tiếp tục với những kiến thức mới về stack…
Thời gian cứ thế dần trôi, ngày lại ngày, tôi luôn mong đợi được gặp anh để được giảng dạy những kiến thức về cấu trúc dữ liệu và thuật toán. Tôi đã được học rất nhiều từ anh, các thuật toán về tìm kiếm, lý thuyết đồ thị, duyệt cây, độ phức tạp của giải thuật. Tôi chăm chú nghe anh như nuốt lấy từng lời, giọng nói của anh thật ấm áp, đôi mắt anh sáng long lanh nhìn tôi trìu mến
Stack (Ngăn xếp)
Hãy tưởng tượng anh tặng em một hộp kẹo Socola nhân dịp Valentine, nó gồm nhiều thanh kẹo xếp thành chồng trong hộp. Đó chính là hình ảnh của một ngăn xếp. Trong thực tế, ngăn xếp chỉ cho phép các hoạt động tại vị trí trên cùng, cũng như em chỉ có thể lấy thanh kẹo socola trên cùng trong chiếc hộp
Ngăn xếp có cấu trúc dữ liệu dạng Last In – First Out (LIFO). Các phần tử được sắp xếp tuần tự, phần tử được thêm vào cuối cùng sẽ được truy cập đầu tiên. Hoạt động thêm vào gọi là PUSH và xóa đi gọi là POP.
Khi Stack chứa đầy phần tử trạng thái đó gọi là Stack overflow, nó cũng giống như những thanh kẹo socola anh tặng em chứa đầy trong chiếc hộp và không thể chứa thêm
Ngược lại, khi Stack rỗng thì trạng thái đó gọi là Stack underflow
Dưới đây là một khai báo về Stack gồm có 1000 phần tử, top chỉ vào phần tử trên cùng của stack
class Stack {
static final int MAX = 1000;
int top;
int stack[] = new int[MAX]; // Maximum size of Stack
Stack () {
top = -1;
}
}
Cũng như hộp kẹo socola, anh tặng em. Nhiều lúc anh cũng muốn biết em đã ăn hết chưa, hay nó đã chứa đầy kẹo. Stack cũng vậy, cần phải check xem stack đã đầy chưa hay đang empty…
Lấy phần tử dữ liệu trên cùng của stack
int peek () {
return stack[top];
}
Kiểm tra ngăn xếp có empty không
boolean isEmpty () {
return (top < 0);
}
Kiểm tra ngăn xếp đã đầy hay chưa
bool isfull () {
if (top == MAX)
return true;
else
return false;
}Những thao tác cơ bản trên Stack
Push
Push giống như anh tặng em 1 thanh kẹo socola, em lại đặt nó nhẹ nhàng vào chiếc hộp của em
Lưu đồ thuật toán của thao tác Push như sau
Source code minh họa
boolean push (int x) {
if (top >= MAX) {
System.out.println ("Stack Overflow");
return false;
} else {
stack[++top] = x;
return true;
}
}
Vậy còn hoạt động POP thì sao anh. Tôi nhìn anh như chờ đợi
Pop
Hoạt động POP giống như em ăn từng thanh kẹo socola ngọt ngào trong chiếc hộp. Hoạt động pop() thực sự xóa phần tử xữ liệu và xóa nó khỏi không gian bộ nhớ.
Lưu đồ thuật toán của thao tác POP như sau
Source code minh họa
int pop () {
if (top < 0) {
System.out.println ("Stack Underflow");
return 0;
} else {
int x = stack[top--];
return x;
}
}
Còn tiếp…
Post Comment