Hướng dẫn stack trong python
Ngăn xếp (Stack) là một trong những cấu trúc dữ liệu cơ bản nhất mà chắc chắn sinh viên ngành Công nghệ thông tin nào cũng phải học. Ngăn xếp được ứng dụng trong nhiều giải thuật của các ngành khác nhau. Trong bài viết này, mình sẽ đồng hành cũng với các bạn tìm hiểu Ngăn xếp là gì, cách thức cài đặt Ngăn xếp với Python và một vài những ứng dụng đơn giản nhé. Chúng ta hãy cùng bắt đầu thôi nào! Let’s get started! Show Nội dung
1. Định nghĩa ngăn xếpNgăn xếp (Stack) là một kiểu danh sách tuyến tính đặc biệt mà phép bổ sung và phép loại bỏ được thực hiện ở một đầu, đầu đó gọi là đỉnh (Top). Mô tả hoạt động của Ngăn xếp Nhận thấy rằng, những cái bánh càng ở trên cao thì khi lấy bánh ra thì nó sẽ được lấy ra sớm hơn. Như vậy, nguyên tắc hoạt động của Ngăn xếp là “Vào sau – Ra trước” hay Last in – First out (LIFO). 2. Mô tả hoạt động của Ngăn xếpCấu trúc dữ liệu Ngăn xếp có cấu trúc đơn giản nhất, nhưng Ngăn xếp được sử dụng trong nhiều các ứng dụng khác nhau và là công cụ cho nhiều cấu trúc dữ liệu và các thuật toán phức tạp. Ta đặt S là đại diện cho Ngăn xếp (Stack), khi đó S phải hỗ trợ tối thiểu hai phương thức sau:
Ngoài ra, Ngăn xếp S còn có thêm những phương thức sau để thuận tiện trong quá trình làm việc:
3. Lưu trữ Ngăn xếp bằng Python ListKiểu List trong Python được sử dụng để mô tả cách thức lưu trữ cũng như hoạt động của Stack. Khi sử dụng phương thức append để bổ sung một phần tử vào biến List, phần tử mới đó được chèn vào ngay sau phần tử cuối cùng của biến. Phương thức
pop trong List được dùng để xóa phần tử cuối cùng của biến List. Ngăn xếp rỗng thì biến List rỗng. Sử dụng List để lưu trữ như Stack 4. Bài tậpBài 1: Cài đặt cấu trúc dữ liệu ngăn xếp sử dụng cấu trúc lưu trữ kế tiếp với phần tử dữ liệu là số nguyên. Sử dụng ngăn xếp chuyển một số nguyên dương hệ 10 sang hệ 2. Yêu cầu: trong chương trình có tạo và sử dụng lớp Stack.
Tài liệu tham khảo:
|