Bài 6.2. Tạo stack từ list
Nội dung bài học
Nhắc lại về stack
- Là cấu trúc dữ liệu trong đó các phần tử tuân theo quy luật FILO. Tức là phần tử nào đưa vào trước nhất sẽ ra sau cùng.
- Phần tử ở đầu stack gọi là phần tử top.
- Thao tác trên stack gồm: push, pop, top, size, is_empty, is_full.
Các hành động
- push(value) – thêm phần tử mới vào đầu stack. Trước khi thêm phần tử cần kiểm tra stack đã đầy chưa. Kết quả thêm mới sẽ là True nếu thành công và False nếu ngược lại.
- pop() – xóa và trả về phần tử ở đầu stack. Quy ước nếu danh sách rỗng, ta thông báo “Stack rỗng” và trả về None.
- top() – lấy phần tử đầu stack nhưng không xóa nó khỏi stack. Quy ước nếu danh sách rỗng, ta thông báo “Stack rỗng” và trả về None.
- is_full() – kiểm tra xem stack đã đầy chưa.
- is_empty() – kiểm tra xem stack có rỗng không.
- size() – trả về kích thước hiện tại của stack.
Triển khai stack
class Stack:
def __init__(self, capacity=0):
self.__data: list = []
self.__capacity: int
self.__size: int = 0
# giả định rằng capacity khi không chỉ định là 10
if capacity <= 0:
self.__capacity = 10
else:
self.__capacity = capacity
# phương thức kiểm tra stack rỗng
def is_empty(self):
return self.__size == 0
# phương thức thêm mới phần tử vào stack
def push(self, value) -> bool:
if self.is_full():
print('==> Stack đầy. Thêm thất bại.')
return False
else:
self.__data.append(value)
self.__size += 1
return True
# phương thức xóa bỏ phần tử cuối
def pop(self):
if self.is_empty():
print('==> Stack rỗng')
return None
else:
element = self.__data.pop()
self.__size -= 1
return element
# phương thức lấy ra phần tử top
def top(self):
if self.is_empty():
print('==> Stack rỗng')
return None
else:
element = self.__data[self.__size - 1]
return element
# phương thức trả về kích thước hiện thời
def size(self):
return self.__size
# phương thức kiểm tra stack đã đầy chưa
def is_full(self):
return self.__size == self.__capacityVí dụ minh họa
# lớp mô tả thông tin sinh viên
class Student:
def __init__(self, student_id=None, first_name=None, last_name=None, gpa=0.0):
self.__gpa: float = gpa
self.__last_name: str = last_name
self.__first_name: str = first_name
self.__student_id: str = student_id
@property
def student_id(self):
return self.__student_id
@student_id.setter
def student_id(self, value):
self.__student_id = value
@property
def first_name(self):
return self.__first_name
@first_name.setter
def first_name(self, value):
self.__first_name = value
@property
def last_name(self):
return self.__last_name
@last_name.setter
def last_name(self, value):
self.__last_name = value
@property
def gpa(self):
return self.__gpa
@gpa.setter
def gpa(self, value):
self.__gpa = value
def __str__(self):
return f'[{self.student_id}, {self.first_name}, {self.last_name}, {self.gpa}]'
def __eq__(self, other): # phương thức chỉ định sự tương đương của hai SV
if other is None:
return False
else:
return self.student_id == other.student_id # cùng mã SV# lớp mô tả một stack và các hành động của nó
class Stack:
def __init__(self, capacity=0):
self.__data: list = []
self.__capacity: int
self.__size: int = 0
# giả định rằng capacity khi không chỉ định là 10
if capacity <= 0:
self.__capacity = 10
else:
self.__capacity = capacity
# phương thức kiểm tra stack rỗng
def is_empty(self):
return self.__size == 0
# phương thức thêm mới phần tử vào stack
def push(self, value) -> bool:
if self.is_full():
print('==> Stack đầy. Thêm thất bại.')
return False
else:
self.__data.append(value)
self.__size += 1
return True
# phương thức xóa bỏ phần tử cuối
def pop(self):
if self.is_empty():
print('==> Stack rỗng')
return None
else:
element = self.__data.pop()
self.__size -= 1
return element
# phương thức lấy ra phần tử top
def top(self):
if self.is_empty():
print('==> Stack rỗng')
return None
else:
element = self.__data[self.__size - 1]
return element
# phương thức trả về kích thước hiện thời
def size(self):
return self.__size
# phương thức kiểm tra stack đã đầy chưa
def is_full(self):
return self.__size == self.__capacity
# hàm hiển thị các phần tử trong stack
def show_stack_elements(stack: Stack):
while not stack.is_empty():
print(stack.pop())
# hàm test các chức năng
def test():
students = [
Student("SV1001", "Nam", "Hoàng", 3.26),
Student("SV1002", "Hoa", "Lương", 3.36),
Student("SV1003", "Bách", "Ngô", 3.21),
Student("SV1004", "Trung", "Trần", 3.54),
Student("SV1005", "Loan", "Lê", 3.04),
Student("SV1006", "Mai", "Nguyễn", 3.87),
Student("SV1007", "Khoa", "Lê", 3.71),
Student("SV1008", "Ánh", "Nguyễn", 3.64),
Student("SV1009", "Dung", "Trần", 3.27),
Student("SV1010", "Chi", "Mai", 3.09),
Student("SV1011", "Phương", "Ma", 3.45)
]
stack = Stack()
# thêm các phần tử vào stack
for element in students:
stack.push(element)
print(f'==> Số phần tử trong stack: {stack.size()}')
print(f'==> Stack đầy? {stack.is_full()}')
# lấy phần tử đầu stack
print(f'==> Phần tử đầu stack: {stack.top()}')
# xóa phần tử đầu stack
print('SAU KHI XÓA MỘT PHẦN TỬ KHỎI STACK: ')
stack.pop()
print(f'==> Số phần tử trong stack: {stack.size()}')
print(f'==> Phần tử đầu stack: {stack.top()}')
print('CÁC PHẦN TỬ CÒN LẠI TRONG STACK: ')
print('==> Các phần tử trong stack: ')
show_stack_elements(stack)
# pop thử stack sau khi stack rỗng
print('CÁC THAO TÁC KHI STACK RỖNG: ')
stack.pop()
print(f'==> Số phần tử trong stack: {stack.size()}')
print(f'==> Phần tử đầu stack: {stack.top()}')
if __name__ == '__main__':
test()
==> Stack đầy. Thêm thất bại.
==> Số phần tử trong stack: 10
==> Stack đầy? True
==> Phần tử đầu stack: [SV1010, Chi, Mai, 3.09]
SAU KHI XÓA MỘT PHẦN TỬ KHỎI STACK:
==> Số phần tử trong stack: 9
==> Phần tử đầu stack: [SV1009, Dung, Trần, 3.27]
CÁC PHẦN TỬ CÒN LẠI TRONG STACK:
==> Các phần tử trong stack:
[SV1009, Dung, Trần, 3.27]
[SV1008, Ánh, Nguyễn, 3.64]
[SV1007, Khoa, Lê, 3.71]
[SV1006, Mai, Nguyễn, 3.87]
[SV1005, Loan, Lê, 3.04]
[SV1004, Trung, Trần, 3.54]
[SV1003, Bách, Ngô, 3.21]
[SV1002, Hoa, Lương, 3.36]
[SV1001, Nam, Hoàng, 3.26]
CÁC THAO TÁC KHI STACK RỖNG:
==> Stack rỗng
==> Số phần tử trong stack: 0
==> Stack rỗng
==> Phần tử đầu stack: NoneBài tập thực hành
- Tải đề bài: click vào đây
- Bài giải mẫu: click vào đây
