Giaosucan's blog - Chia sẻ kiến thức theo cách bá đạo

Ticker

20/recent/ticker-posts

Em fresher mưa - Phần 2

Series: Cấu trúc dữ liệu và thuật toán dành cho các bạn fresher lấy cảm hứng từ MV đậm chất ngôn tình của Hương Tràm, Em gái mưa.
Phần 1

Hương tràm em gái mưa


Một chủ đề đầy xúc động, Em fresher mưa xoay quanh tình yêu đơn phương, đầy nước mắt và nụ cười của một em fresher mới ra trường đối với anh leader của mình


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 đã đầu 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


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


Vậy là một kiến thức mới về Cấu trúc dữ liệu và giải thuật tôi đã được học từ anh. Khóe mắt tôi cay cay, giọt nước mắt lăn dài trên má, nhưng môi tôi vẫn thoáng nở nụ cười. Nụ cười của niềm vui, niềm hạnh phúc khi được ở bên anh




(Còn tiếp)

Đăng nhận xét

4 Nhận xét

  1. "Vậy là một kiến thức mới về Cấu trúc dữ liệu và giải thuật tôi đã được học từ anh. Khóe mắt tôi cay cay, giọt nước mắt lăn dài trên má, nhưng môi tôi vẫn thoáng nở nụ cười. Nụ cười của niềm vui, niềm hạnh phúc khi được ở bên anh".

    Hơ hơ học thêm kiến thức sao lại khóc nhể :(

    Trả lờiXóa
  2. đây là những kiến thức rất cơ bản

    Trả lờiXóa