Ngăn xếp là một cấu trúc dữ liệu tuyến tính hoạt động trên Cuối cùng vào Đầu ra cơ chế (LIFO). Phần tử đi vào đầu tiên trong ngăn xếp là phần tử cuối cùng được xử lý.
Ví dụ
Cấu trúc dữ liệu ngăn xếp có thể được hiểu với sự trợ giúp của ví dụ về ngăn xếp các món ăn.
Các món ăn được xếp chồng lên nhau. Đĩa hoặc đĩa đầu tiên ở dưới cùng của đống và đĩa cuối cùng được đặt ở trên cùng của đống hoặc chồng. Bất cứ khi nào chúng tôi cần một đĩa, chúng tôi sẽ lấy đĩa ở trên cùng của chồng, là đĩa được đưa vào hoặc đặt cuối cùng. Đĩa được đặt trước sẽ là đĩa cuối cùng được gắp. Do đó, cơ chế CUỐI CÙNG ĐẦU TIÊN ĐƯỢC tuân theo.
Triển khai ngăn xếp trong Python
Ngăn xếp trong Python có thể được triển khai theo nhiều cách khác nhau bằng cách sử dụng các cấu trúc dữ liệu tuyến tính khác hoặc các mô-đun tích hợp sẵn trong thư viện Python.
Phương pháp 1 - Triển khai bằng cách sử dụng danh sách
Ngăn xếp trong Python có thể được triển khai bằng cách sử dụng danh sách. Tuy nhiên, việc sử dụng danh sách để triển khai ngăn xếp không hiệu quả nhiều và do đó không được khuyến khích.
Các hoạt động liên quan
append () - Hàm này thêm một phần tử vào cuối ngăn xếp.
pop () - Hàm này xóa và trả về phần tử cuối cùng hoặc phần tử trên cùng trong ngăn xếp. Hàm này hiển thị các phần tử theo thứ tự LIFO.
Ví dụ
stack=[]
stack.append(1)
stack.append(2)
stack.append(3)
print("Intial Stack",stack)
print("Element popped from the stack")
print(stack.pop())
print(stack.pop())
print("Stack after popping some elements",stack) Đầu ra
Intial Stack [1, 2, 3] Element popped from the stack 3 2 Stack after popping some elements [1]
Bạn không thể xóa thêm phần tử khi ngăn xếp trống. Làm như vậy dẫn đến ngoại lệ.
stack.pop() IndexError: pop from empty list
Phương pháp 2 - Triển khai bằng queue.LifoQueue
Đây là cách để triển khai ngăn xếp bằng cách sử dụng mô-đun sẵn có từ python. Chúng ta cần nhập LifoQueue từ hàng đợi. Chúng ta có thể khởi tạo LifoQueue hoặc ngăn xếp với một số kích thước cụ thể. Kích thước bằng 0 có nghĩa là một ngăn xếp vô hạn.
Các hoạt động liên quan
kích thước tối đa - số phần tử tối đa được phép trong ngăn xếp
get () - xóa và trả lại phần tử cuối cùng hoặc phần tử trên cùng khỏi ngăn xếp. Nếu ngăn xếp trống, hãy đợi cho đến khi ngăn xếp có ít nhất một phần tử.
get_nowait () - xóa và trả về phần tử cuối cùng khỏi ngăn xếp. Nếu ngăn xếp trống, hãy tăng một ngoại lệ.
đặt (mục) - thêm một phần tử vào cuối ngăn xếp. Nếu ngăn xếp đã đầy, hãy đợi cho đến khi có sẵn vùng trống.
put_nowait (item) - thêm một phần tử vào cuối ngăn xếp. Nếu ngăn xếp đã đầy, hãy đưa ra một ngoại lệ.
đầy đủ () - trả về true nếu ngăn xếp đầy, nếu không trả về false.
trống () - trả về True nếu ngăn xếp trống, ngược lại là false
qsize () - trả về số phần tử có trong ngăn xếp
Ví dụ
from queue import LifoQueue
s=LifoQueue(maxsize=3)
s.put(1)
s.put(2)
s.put(3)
print("Is stack full",s.full())
print("Element popped from the stack")
print(s.get())
print(s.get())
print("Number of elements in stack",s.qsize())
print("Is stack empty",s.empty()) Đầu ra
Is stack full True Element popped from the stack 3 2 Number of elements in stack 1 Is stack empty False
Phương pháp 3:Triển khai bằng cách sử dụng collection.deque
Đây là một cách khác để triển khai ngăn xếp trong Python. Chúng tôi cần nhập deque từ mô-đun bộ sưu tập.
Các hoạt động liên quan
append () - Hàm này thêm một phần tử vào cuối ngăn xếp.
pop () - Hàm này loại bỏ và trả về phần tử cuối cùng trong ngăn xếp với độ phức tạp thời gian là O (1).
Ví dụ
from collections import deque
stack=deque()
stack.append(1)
stack.append(2)
stack.append(3)
print("Intial stack: ",stack)
print("Element popped from the stack")
print(stack.pop())
print(stack.pop())
print("Stack after popping some elements: ",stack) Đầu ra
Intial stack: deque([1, 2, 3]) Element popped from the stack 3 2 Stack after popping some elements: deque([1])
Sử dụng hàm pop () trên một deque trống sẽ tạo ra một ngoại lệ.