Em Fresher Học Cấu Trúc Dữ Liệu Và Giải Thuật (P2)

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

Nguyễn thanh vy


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
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


Push operation
Lưu đồ thuật toán của thao tác Push như sau


Lưu đồ thuật toán push


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ớ.

Screen Shot 2016-07-25 at 2.21.19 PM

Lưu đồ thuật toán của thao tác POP như sau


Lưu đồ thuật toán Pop


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...