Giới thiệu

Trong khi một số cấu trúc dữ liệu rất linh hoạt và có thể được sử dụng trong nhiều ứng dụng, thì một số cấu trúc khác lại chuyên biệt và được thiết kế để xử lý các vấn đề cụ thể. Một cấu trúc chuyên biệt như vậy, được biết đến vì sự đơn giản nhưng tiện ích vượt trội của nó, là ngăn xếp.

Vậy ngăn xếp là gì? Về cốt lõi, ngăn xếp là một cấu trúc dữ liệu tuyến tính tuân theo LIFO Nguyên tắc (Vào sau ra trước). Hãy nghĩ về nó như một chồng đĩa trong căng tin; bạn chỉ lấy cái đĩa ở trên cùng, khi đặt cái đĩa mới thì nó sẽ lên trên cùng của chồng.

Phần tử được thêm vào cuối cùng là phần tử đầu tiên bị xóa

Nhưng tại sao việc hiểu ngăn xếp lại quan trọng? Trong những năm qua, các ngăn xếp đã tìm thấy ứng dụng của chúng trong rất nhiều lĩnh vực, từ quản lý bộ nhớ bằng các ngôn ngữ lập trình yêu thích của bạn đến chức năng nút quay lại trong trình duyệt web của bạn. Sự đơn giản nội tại này, kết hợp với khả năng ứng dụng rộng rãi của nó, khiến ngăn xếp trở thành một công cụ không thể thiếu trong kho vũ khí của nhà phát triển.

Trong hướng dẫn này, chúng ta sẽ đi sâu vào các khái niệm đằng sau ngăn xếp, cách triển khai, trường hợp sử dụng của chúng, v.v. Chúng ta sẽ xác định ngăn xếp là gì, cách chúng hoạt động và sau đó, chúng ta sẽ xem xét hai cách phổ biến nhất để triển khai cấu trúc dữ liệu ngăn xếp trong Python.

Các khái niệm cơ bản về cấu trúc dữ liệu ngăn xếp

Về bản chất, ngăn xếp có vẻ đơn giản nhưng nó sở hữu những sắc thái mang lại cho nó những ứng dụng linh hoạt trong miền tính toán. Trước khi đi sâu vào cách triển khai và cách sử dụng thực tế, hãy đảm bảo hiểu biết vững chắc về các khái niệm cốt lõi xung quanh ngăn xếp.

Nguyên tắc LIFO (Vào sau ra trước)

LIFO là nguyên tắc hướng dẫn đằng sau một ngăn xếp. Nó ngụ ý rằng mục cuối cùng vào ngăn xếp là mục đầu tiên rời khỏi ngăn xếp. Đặc điểm này giúp phân biệt ngăn xếp với các cấu trúc dữ liệu tuyến tính khác, chẳng hạn như hàng đợi.

Lưu ý: Một ví dụ hữu ích khác giúp bạn hiểu được khái niệm về cách thức hoạt động của ngăn xếp là hãy tưởng tượng mọi người vào và ra khỏi một thang máy – người cuối cùng vào thang máy là người đầu tiên bước ra!

Hoạt động cơ bản

Mọi cấu trúc dữ liệu được xác định bởi các hoạt động mà nó hỗ trợ. Đối với ngăn xếp, các thao tác này rất đơn giản nhưng quan trọng:

• Đẩy – Thêm một phần tử vào đầu ngăn xếp. Nếu ngăn xếp đầy, thao tác này có thể dẫn đến tràn ngăn xếp.

• Pop – Loại bỏ và trả về phần tử trên cùng của ngăn xếp. Nếu ngăn xếp trống, việc thử bật lên có thể gây ra tình trạng tràn ngăn xếp.

• Peek (hoặc Top) – Quan sát phần tử trên cùng mà không loại bỏ nó. Thao tác này hữu ích khi bạn muốn kiểm tra phần tử trên cùng hiện tại mà không làm thay đổi trạng thái của ngăn xếp.

Đến bây giờ, tầm quan trọng của cấu trúc dữ liệu ngăn xếp và các khái niệm nền tảng của nó đã rõ ràng. Khi tiếp tục, chúng ta sẽ đi sâu vào cách triển khai nó, làm sáng tỏ cách các nguyên tắc cơ bản này chuyển thành mã thực tế.

Cách triển khai ngăn xếp từ đầu trong Python

Sau khi nắm được các nguyên tắc cơ bản đằng sau ngăn xếp, đã đến lúc xắn tay áo lên và đi sâu vào khía cạnh thực tế của mọi thứ. Việc triển khai ngăn xếp tuy đơn giản nhưng có thể được tiếp cận theo nhiều cách. Trong phần này, chúng ta sẽ khám phá hai phương pháp chính để triển khai ngăn xếp – sử dụng mảng và danh sách liên kết.

Triển khai ngăn xếp bằng mảng

Mảng, đang được vị trí bộ nhớ liền kề, cung cấp một phương tiện trực quan để thể hiện ngăn xếp. Chúng cho phép độ phức tạp về thời gian O(1) để truy cập các phần tử theo chỉ mục, đảm bảo các hoạt động Đẩy, bật và xem nhanh nhanh chóng. Ngoài ra, mảng có thể sử dụng bộ nhớ hiệu quả hơn vì không cần sử dụng nhiều con trỏ như trong danh sách liên kết.

Mặt khác, mảng truyền thống có kích thước cố định, nghĩa là khi đã khởi tạo, chúng không thể thay đổi kích thước. Điều này có thể dẫn đến một tràn ngăn xếp nếu không được giám sát. Điều này có thể được khắc phục bằng mảng động (như của Python list), có thể thay đổi kích thước nhưng thao tác này khá tốn kém.

Sau tất cả những điều đó, hãy bắt đầu triển khai lớp ngăn xếp của chúng ta bằng cách sử dụng mảng trong Python. Trước hết, hãy tạo một lớp, với hàm tạo lấy kích thước của ngăn xếp làm tham số:

class Stack: def __init__(self, size): self.size = size self.stack = [None] * size self.top = -1

Như bạn có thể thấy, chúng tôi đã lưu trữ ba giá trị trong lớp của mình. Các size là kích thước mong muốn của ngăn xếp, stack là mảng thực tế được sử dụng để biểu diễn cấu trúc dữ liệu ngăn xếp và top là chỉ số của phần tử cuối cùng trong stack mảng (đỉnh của ngăn xếp).

Từ giờ trở đi, chúng ta sẽ tạo và giải thích một phương thức cho từng thao tác ngăn xếp cơ bản. Mỗi phương thức đó sẽ được chứa trong Stack lớp chúng ta vừa tạo.

Hãy bắt đầu với push() phương pháp. Như đã thảo luận trước đó, thao tác đẩy sẽ thêm một phần tử vào đầu ngăn xếp. Trước hết, chúng tôi sẽ kiểm tra xem ngăn xếp có còn chỗ trống cho phần tử chúng tôi muốn thêm hay không. Nếu ngăn xếp đầy, chúng tôi sẽ tăng Stack Overflow ngoại lệ. Nếu không, chúng ta sẽ chỉ thêm phần tử và điều chỉnh top và stack phù hợp:

def push(self, item): if self.top == self.size - 1: raise Exception("Stack Overflow") self.top += 1 self.stack[self.top] = item

Bây giờ, chúng ta có thể định nghĩa phương thức để loại bỏ một phần tử khỏi đỉnh ngăn xếp – phương thức pop() phương pháp. Trước khi thử xóa một phần tử, chúng ta cần kiểm tra xem có phần tử nào trong ngăn xếp hay không vì việc cố gắng lấy một phần tử từ ngăn xếp trống chẳng ích gì:

def pop(self): if self.top == -1: raise Exception("Stack Underflow") item = self.stack[self.top] self.top -= 1 return item

Cuối cùng, chúng ta có thể định nghĩa peek() phương thức chỉ trả về giá trị của phần tử hiện ở trên cùng của ngăn xếp:

def peek(self): if self.top == -1: raise Exception("Stack is empty") return self.stack[self.top]

Và thế là xong! Bây giờ chúng ta có một lớp thực hiện hành vi của ngăn xếp bằng cách sử dụng danh sách trong Python.

Triển khai ngăn xếp bằng danh sách liên kết

Danh sách liên kết, đang cấu trúc dữ liệu động, có thể dễ dàng phát triển và thu nhỏ, điều này có thể có lợi cho việc triển khai ngăn xếp. Vì danh sách liên kết phân bổ bộ nhớ khi cần thiết nên ngăn xếp có thể tăng và giảm linh hoạt mà không cần thay đổi kích thước rõ ràng. Một lợi ích khác của việc sử dụng danh sách liên kết để triển khai ngăn xếp là các thao tác đẩy và bật chỉ yêu cầu thay đổi con trỏ đơn giản. Nhược điểm của điều đó là mọi phần tử trong danh sách liên kết đều có thêm một con trỏ, tiêu tốn nhiều bộ nhớ hơn so với mảng.

Như chúng ta đã thảo luận trong “Danh sách liên kết Python” bài viết, điều đầu tiên chúng ta cần triển khai trước danh sách liên kết thực tế là một lớp cho một nút:

class Node: def __init__(self, data): self.data = data self.next = None

Việc triển khai này chỉ lưu trữ hai điểm dữ liệu – giá trị được lưu trữ trong nút (data) và tham chiếu đến nút tiếp theo (next).

Loạt bài gồm 3 phần của chúng tôi về danh sách liên kết trong Python:

Bây giờ chúng ta có thể nhảy vào lớp ngăn xếp thực tế. Hàm tạo sẽ khác một chút so với hàm tạo trước đó. Nó sẽ chỉ chứa một biến – tham chiếu đến nút trên cùng của ngăn xếp:

class Stack: def __init__(self): self.top = None

Như mong đợi, push() phương thức thêm một phần tử mới (nút trong trường hợp này) vào đầu ngăn xếp:

def push(self, item): node = Node(item) if self.top: node.next = self.top self.top = node

Sản phẩm pop() Phương thức này kiểm tra xem có phần tử nào trong ngăn xếp không và loại bỏ phần tử trên cùng nếu ngăn xếp không trống:

def pop(self): if not self.top: raise Exception("Stack Underflow") item = self.top.data self.top = self.top.next return item

Cuối cùng, peek() phương thức chỉ đơn giản là đọc giá trị của phần tử từ đầu ngăn xếp (nếu có):

def peek(self): if not self.top: raise Exception("Stack is empty") return self.top.data

Lưu ý: Giao diện của cả hai Stack các lớp đều giống nhau – điểm khác biệt duy nhất là việc triển khai nội bộ các phương thức lớp. Điều đó có nghĩa là bạn có thể dễ dàng chuyển đổi giữa các cách triển khai khác nhau mà không phải lo lắng về nội dung bên trong của các lớp.

Việc lựa chọn giữa mảng và danh sách liên kết phụ thuộc vào các yêu cầu và ràng buộc cụ thể của ứng dụng.

Cách triển khai ngăn xếp bằng cấu trúc tích hợp của Python

Đối với nhiều nhà phát triển, việc xây dựng ngăn xếp từ đầu, tuy mang tính giáo dục nhưng có thể không phải là cách hiệu quả nhất để sử dụng ngăn xếp trong các ứng dụng trong thế giới thực. May mắn thay, nhiều ngôn ngữ lập trình phổ biến được trang bị các lớp và cấu trúc dữ liệu dựng sẵn hỗ trợ các hoạt động ngăn xếp một cách tự nhiên. Trong phần này, chúng ta sẽ khám phá các dịch vụ của Python về vấn đề này.

Python, là một ngôn ngữ linh hoạt và năng động, không có lớp ngăn xếp chuyên dụng. Tuy nhiên, cấu trúc dữ liệu tích hợp của nó, đặc biệt là các danh sách và lớp deque từ collections module, có thể dễ dàng phục vụ như ngăn xếp.

Sử dụng danh sách Python làm ngăn xếp

Danh sách Python có thể mô phỏng một ngăn xếp khá hiệu quả do tính chất động của chúng và sự hiện diện của các phương thức như append() và pop().

• Thao tác đẩy – Việc thêm một phần tử vào đầu ngăn xếp cũng đơn giản như sử dụng append() phương pháp:

  stack = []
  stack.append('A')
  stack.append('B')
  

• Hoạt động bật lên – Có thể loại bỏ phần tử trên cùng bằng cách sử dụng pop() phương thức không có bất kỳ đối số nào:

  top_element = stack.pop() 

• Hoạt động lén lút Việc truy cập phần trên cùng mà không cần bật lên có thể được thực hiện bằng cách lập chỉ mục phủ định:

  top_element = stack[-1] 

Sử dụng deque Lớp học từ bộ sưu tập Mô-đun

Sản phẩm deque Lớp (viết tắt của hàng đợi hai đầu) là một công cụ linh hoạt khác để triển khai ngăn xếp. Nó được tối ưu hóa để thêm và bật nhanh từ cả hai đầu, giúp thao tác ngăn xếp hiệu quả hơn một chút so với danh sách.

• Khởi tạo:

  from collections import deque
  stack = deque()
  

• Thao tác đẩy – Tương tự như danh sách, append() phương pháp được sử dụng:

  stack.append('A')
  stack.append('B')
  

• Hoạt động bật lên – Giống như danh sách, pop() phương pháp thực hiện công việc:

  top_element = stack.pop() 

• Hoạt động lén lút – Cách làm tương tự như với danh sách:

  top_element = stack[-1] 

Khi nào nên sử dụng cái nào?

Mặc dù cả danh sách và deque đều có thể được sử dụng làm ngăn xếp, nhưng nếu bạn chủ yếu sử dụng cấu trúc làm ngăn xếp (với các phần nối thêm và bật lên từ một đầu), thì deque có thể nhanh hơn một chút do được tối ưu hóa. Tuy nhiên, đối với hầu hết các mục đích thực tế và trừ khi xử lý các ứng dụng quan trọng về hiệu năng, danh sách của Python là đủ.

Lưu ý: Phần này đi sâu vào các dịch vụ tích hợp sẵn của Python cho hành vi giống như ngăn xếp. Bạn không nhất thiết phải phát minh lại bánh xe (bằng cách triển khai ngăn xếp từ đầu) khi bạn có trong tay những công cụ mạnh mẽ như vậy.

Các vấn đề tiềm ẩn liên quan đến ngăn xếp và cách khắc phục chúng

Mặc dù ngăn xếp cực kỳ linh hoạt và hiệu quả, giống như bất kỳ cấu trúc dữ liệu nào khác, nhưng chúng không tránh khỏi những cạm bẫy tiềm ẩn. Điều cần thiết là phải nhận ra những thách thức này khi làm việc với ngăn xếp và có sẵn các chiến lược để giải quyết chúng. Trong phần này, chúng ta sẽ đi sâu vào một số vấn đề phổ biến liên quan đến ngăn xếp và khám phá các cách khắc phục chúng.

Stack Overflow

Điều này xảy ra khi cố gắng đẩy một phần tử lên một ngăn xếp đã đạt đến dung lượng tối đa. Đây đặc biệt là sự cố trong môi trường có kích thước ngăn xếp cố định, chẳng hạn như trong một số tình huống lập trình cấp thấp nhất định hoặc lệnh gọi hàm đệ quy.

Nếu bạn đang sử dụng ngăn xếp dựa trên mảng, hãy cân nhắc chuyển sang mảng động hoặc triển khai danh sách liên kết để tự thay đổi kích thước. Một bước khác để ngăn ngừa tràn ngăn xếp là liên tục theo dõi kích thước của ngăn xếp, đặc biệt là trước các thao tác đẩy và cung cấp thông báo lỗi hoặc lời nhắc rõ ràng về tình trạng tràn ngăn xếp.

Nếu tràn ngăn xếp xảy ra do có quá nhiều lệnh gọi đệ quy, hãy xem xét các giải pháp lặp lại hoặc tăng giới hạn đệ quy nếu môi trường cho phép.

ngăn xếp tràn

Điều này xảy ra khi có nỗ lực lấy một phần tử từ ngăn xếp trống. Để ngăn điều này xảy ra, hãy luôn kiểm tra xem ngăn xếp có trống hay không trước khi thực hiện các thao tác bật lên hoặc nhìn trộm. Trả lại thông báo lỗi rõ ràng hoặc xử lý luồng ngầm một cách duyên dáng mà không làm hỏng chương trình.

Trong những môi trường có thể chấp nhận được, hãy cân nhắc việc trả về một giá trị đặc biệt khi xuất hiện từ một ngăn xếp trống để biểu thị tính không hợp lệ của thao tác.

Ràng buộc bộ nhớ

Trong môi trường hạn chế về bộ nhớ, ngay cả việc thay đổi kích thước động các ngăn xếp (như ngăn xếp dựa trên danh sách liên kết) cũng có thể dẫn đến cạn kiệt bộ nhớ nếu chúng phát triển quá lớn. Do đó, hãy theo dõi mức sử dụng bộ nhớ tổng thể của ứng dụng và mức tăng trưởng của ngăn xếp. Có lẽ nên giới thiệu một giới hạn mềm về kích thước của ngăn xếp.

Mối quan ngại về an toàn của chủ đề

Trong môi trường đa luồng, các hoạt động đồng thời trên một ngăn xếp được chia sẻ bởi các luồng khác nhau có thể dẫn đến sự không nhất quán về dữ liệu hoặc các hành vi không mong muốn. Giải pháp tiềm năng cho vấn đề này có thể là:

• Mutexes và khóa – Sử dụng mutexes (đối tượng loại trừ lẫn nhau) hoặc khóa để đảm bảo rằng chỉ một luồng có thể thực hiện các thao tác trên ngăn xếp tại một thời điểm nhất định.
• Hoạt động nguyên tử – Tận dụng các hoạt động nguyên tử, nếu được môi trường hỗ trợ, để đảm bảo tính nhất quán của dữ liệu trong các hoạt động đẩy và bật.
• Ngăn xếp theo chủ đề cục bộ – Trong trường hợp mỗi luồng cần ngăn xếp của nó, hãy cân nhắc sử dụng bộ nhớ cục bộ của luồng để cung cấp cho mỗi luồng một phiên bản ngăn xếp riêng biệt.

Mặc dù ngăn xếp thực sự rất mạnh mẽ nhưng việc nhận thức được các vấn đề tiềm ẩn và tích cực triển khai các giải pháp sẽ đảm bảo các ứng dụng mạnh mẽ và không có lỗi. Nhận ra những cạm bẫy này là một nửa trận chiến – nửa còn lại là áp dụng các phương pháp hay nhất để giải quyết chúng một cách hiệu quả.

Kết luận

Ngăn xếp, mặc dù có bản chất có vẻ đơn giản, nhưng lại củng cố nhiều hoạt động cơ bản trong thế giới điện toán. Từ phân tích các biểu thức toán học phức tạp đến quản lý lệnh gọi hàm, tiện ích của chúng rất rộng rãi và cần thiết. Khi chúng ta tìm hiểu chi tiết về cấu trúc dữ liệu này, rõ ràng sức mạnh của nó không chỉ nằm ở tính hiệu quả mà còn ở tính linh hoạt của nó.

Tuy nhiên, như với tất cả các công cụ, hiệu quả của nó phụ thuộc vào cách sử dụng. Chỉ cần đảm bảo rằng bạn hiểu rõ về các nguyên tắc của nó, những cạm bẫy tiềm ẩn và các phương pháp hay nhất để đảm bảo rằng bạn có thể khai thác sức mạnh thực sự của ngăn xếp. Cho dù bạn đang triển khai một cơ sở từ đầu hay tận dụng các tiện ích tích hợp sẵn trong các ngôn ngữ như Python, thì chính ứng dụng có tâm của các cấu trúc dữ liệu này sẽ làm nổi bật các giải pháp của bạn.

• Phân phối nội dung và PR được hỗ trợ bởi SEO. Được khuếch đại ngay hôm nay.
• PlatoData.Network Vertical Generative Ai. Trao quyền cho chính mình. Truy cập Tại đây.
• PlatoAiStream. Thông minh Web3. Kiến thức khuếch đại. Truy cập Tại đây.
• Trung tâmESG. Than đá, công nghệ sạch, Năng lượng, Môi trường Hệ mặt trời, Quản lý chất thải. Truy cập Tại đây.
• PlatoSức khỏe. Tình báo thử nghiệm lâm sàng và công nghệ sinh học. Truy cập Tại đây.
• nguồn: https://stackabuse.com/guide-to-stacks-in-python/