Thông báo: Download 4 khóa học Python từ cơ bản đến nâng cao tại đây.
Làm việc với cấu trúc Dữ liệu Stack trong Python
Stack (ngăn xếp) là một cấu trúc dữ liệu tuyến tính theo nguyên tắc LIFO (Last In First Out - vào sau ra trước) hoặc FILO (First In Last Out - vào trước ra sau). Trong bài viết này, mình sẽ tìm hiểu khái niệm về stack và cách tạo cũng như sử dụng stack trong Python.
Stack là gì?
Có nhiều cấu trúc dữ liệu có thể sử dụng trong Python, một trong số đó là stack. Hãy tưởng tượng một chồng sách đặt lên nhau, nếu bạn muốn thêm một cuốn sách, bạn sẽ đặt nó lên đầu chồng sách. Tương tự, nếu muốn lấy một cuốn sách, bạn cũng sẽ lấy từ trên cùng. Đây là nguyên tắc cơ bản của stack.
- Kích thước cố định: Stack có độ dài cố định, nghĩa là có số lượng phần tử tối đa. Nếu bạn cố thêm phần tử khi stack đã đầy, sẽ xảy ra "OVERFLOW".
- Không hỗn hợp kiểu dữ liệu: Các phần tử trong stack phải cùng kiểu dữ liệu, không thể thêm kiểu khác vào cùng stack, giống như việc đặt sách Toán vào chồng sách Tin học sẽ tạo ra một đống lộn xộn!
Tạo Stack trong Python
Python không có kiểu dữ liệu stack tích hợp sẵn, nhưng chúng ta có thể tạo stack bằng cách sử dụng Lập trình Hướng Đối tượng (OOP) và danh sách (list
) của Python.
class Stack: """ Stack cơ bản với các thao tác: - push: thêm phần tử - pop: loại bỏ phần tử trên cùng - peek: lấy phần tử trên cùng mà không xóa - show: hiển thị toàn bộ stack """ __status__ = { -2: "LỖI - SAI KIỂU DỮ LIỆU", -1: "LỖI - RỖNG STACK", 0: "LỖI - TRÀN STACK", 1: "THÀNH CÔNG", } def __init__(self, size: int, _class: type): self.stack = [] # Khởi tạo stack rỗng self.size = size # Kích thước của stack self.type = _class # Kiểu dữ liệu của stack def push(self, element) -> int: if not isinstance(element, self.type): return Stack.__status__[-2] elif len(self.stack) >= self.size: return Stack.__status__[0] else: self.stack.append(element) self.element = element return Stack.__status__[1] def pop(self) -> int: if len(self.stack) == 0: return Stack.__status__[-1] else: self.stack.pop() self.element = self.stack[-1] if self.stack else None return Stack.__status__[1] def peek(self): return self.element if self.stack else None def show(self): return self.stack if self.stack else None
Sử dụng Stack trong Python
Bây giờ, chúng ta sẽ tạo một stack với độ dài 5 và kiểu dữ liệu là số nguyên.
Bài viết này được đăng tại [free tuts .net]
stack = Stack(size=5, _class=int)
Thêm dữ liệu vào Stack
>>> stack.push(36) 'THÀNH CÔNG' >>> stack.push(67) 'THÀNH CÔNG' >>> stack.show() [36, 67]
Xóa phần tử khỏi Stack
>>> stack.pop() 'THÀNH CÔNG' >>> stack.pop() 'THÀNH CÔNG' >>> stack.pop() 'LỖI - RỖNG STACK'
Kiểm tra giới hạn Stack
>>> stack.push(17) 'THÀNH CÔNG' >>> stack.push(25) 'THÀNH CÔNG' >>> stack.push("Python") 'LỖI - SAI KIỂU DỮ LIỆU' >>> stack.push(49) 'THÀNH CÔNG' >>> stack.push(52) 'THÀNH CÔNG' >>> stack.push(93) 'LỖI - TRÀN STACK' >>> stack.show() [17, 25, 49, 52]
Kết bài
Qua bài viết này, mình đã tìm hiểu về cấu trúc dữ liệu Stack, một trong những khái niệm cơ bản nhưng rất hữu ích trong lập trình. Stack với nguyên tắc hoạt động LIFO (Last In First Out) giúp quản lý dữ liệu