Cấu trúc dữ liệu là một tập hợp các giá trị dữ liệu, mối quan hệ giữa chúng và các chức năng hoặc hoạt động có thể được áp dụng cho dữ liệu. Bây giờ có rất nhiều Cấu trúc dữ liệu có sẵn. Nhưng hôm nay chúng ta sẽ tập trung vào Cấu trúc dữ liệu ngăn xếp. Tôi sẽ thảo luận về các chủ đề sau:
- Tại sao lại có cấu trúc dữ liệu?
- Các loại cấu trúc dữ liệu
- Cấu trúc dữ liệu ngăn xếp là gì?
- Tạo cấu trúc dữ liệu ngăn xếp
- Đẩy các phần tử vào ngăn xếp
- Phần tử Pop từ Ngăn xếp
- Các ứng dụng của cấu trúc dữ liệu ngăn xếp
Tại sao lại có cấu trúc dữ liệu?
Để trả lời điều này, bạn sẽ phải suy nghĩ ở cấp độ lớn. Hãy nghĩ cách bản đồ Google hiển thị cho bạn con đường tốt nhất chỉ trong một phần giây, cách nó trả về cho bạn kết quả tìm kiếm trong micro giây. Nó không chỉ xử lý với 100 trang web, nó xử lý hơn một tỷ trang web và vẫn hiển thị cho bạn kết quả nhanh chóng.
Vâng, mặc dù thuật toán được sử dụng đóng một vai trò quan trọng, nhưng cấu trúc dữ liệu hoặc vùng chứa được sử dụng là nền tảng của thuật toán đó. Trong bất kỳ ứng dụng nào, việc tổ chức và lưu trữ dữ liệu theo cách hoặc theo cấu trúc phù hợp nhất với cách sử dụng của nó là chìa khóa để truy cập và xử lý dữ liệu hiệu quả.
Các loại cấu trúc dữ liệu
Có một số cấu trúc dữ liệu tiêu chuẩn có thể được sử dụng để làm việc hiệu quả với dữ liệu. Chúng tôi thậm chí có thể tùy chỉnh chúng hoặc xây dựng những cái hoàn toàn mới để phù hợp với ứng dụng của mình.
Cấu trúc dữ liệu ngăn xếp là gì?
Hãy xem xét một số ví dụ thực tế:
- Gửi hàng
- Đĩa trên khay
- Đống tiền xu
- Ngăn kéo
- Xe lửa chạy trong bãi đường sắt
Tất cả các ví dụ này đều tuân theo Cuối cùng vào trước chiến lược. Xem xét đĩa trên khay, Khi bạn muốn lấy đĩa, bạn buộc phải chọn đĩa từ trên xuống trong khi khi các đĩa được giữ trên khay, chúng phải theo thứ tự ngược lại. Các ví dụ trên theo sau Cuối cùng Trong-Đầu-ra (LIFO) nguyên tắc được gọi là Cây rơm .
Ngoài các hoạt động bổ sung, tôi có thể nói rằng các Hoạt động chính có thể có trên ngăn xếp là:
- Đẩy hoặc chèn một phần tử lên đầu ngăn xếp
- Bật hoặc xóa một phần tử khỏi đầu ngăn xếp
Tạo cấu trúc dữ liệu ngăn xếp
class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ element = [None] * self .__ max_size self .__ top = -1
- max_size là số phần tử tối đa được mong đợi trong ngăn xếp.
- Các phần tử của ngăn xếp được lưu trữ trong danh sách python.
- Top cho biết chỉ số trên cùng của ngăn xếp mà ban đầu được lấy -1 để đánh dấu ngăn xếp trống.
Trạng thái ban đầu của Ngăn xếp có thể được nhìn thấy trong Hình nơi max_size = 5
cách sử dụng quyền hạn trong java
Đẩy phần tử vào ngăn xếp
Bây giờ, nếu bạn muốn nhập hoặc đẩy phần tử vào ngăn xếp, bạn phải nhớ rằng
- Phần trên cùng sẽ trỏ chỉ mục mà phần tử sẽ được chèn vào.
- Và sẽ không có phần tử nào được chèn khi ngăn xếp đầy, tức là khi max_size = top.
Vậy thuật toán nên là gì ??
# trả về kích thước tối đa của ngăn xếp def get_max_size (self): trả về self .__ max_size # trả về giá trị bool cho dù ngăn xếp có đầy hay không, Đúng nếu đầy và Sai nếu không thì def is_full (self): trả về self.get_max_size () - 1 == self .__ top #pushes phần tử ở đầu stack def push (self, data): if (self.is_full ()): print ('stack đã đầy') else: self .__ top = self .__ top + int (1 ) self .__ Elements [self .__ top] = data # Bạn có thể sử dụng __str __ () dưới đây để in các phần tử của đối tượng DS trong khi gỡ lỗi def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ Elements [index])) index- = 1 msg = '' .join (msg) msg = 'Stack data (Top to Bottom):' + msg return msgBây giờ, khi bạn thực hiện những điều sau:
stack1 = Ngăn xếp (4)
# Đẩy tất cả (các) phần tử bắt buộc.
stack1.push (“A”)
stack1.push (“B”)
stack1.push (“C”)
stack1.push (“E”)
print (stack1.is_full ())
in (stack1)
Đầu ra:
chồng đã đầy
Thật
Dữ liệu ngăn xếp (Từ trên xuống dưới): D C B A
Phần tử Pop từ Ngăn xếp
Bây giờ, khi bạn đã chèn các phần tử vào ngăn xếp, bạn muốn bật chúng lên, vì vậy bạn cần lưu ý những điều sau:
- Ngăn xếp không trống, tức là trên cùng! = -1
- Khi bạn xóa dữ liệu, đỉnh phải trỏ đến đỉnh trước đó của ngăn xếp.
Vậy, thuật toán sẽ là gì ??
#returns giá trị bool cho dù ngăn xếp có trống hay không, Đúng nếu trống và Sai nếu không def is_empty (self): trả về self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): print ('không có gì để bật, đã trống') else: a = self .__ element [self .__ top] self .__ top = self .__ top-1 return a #display tất cả các phần tử ngăn xếp từ trên xuống dưới. def display (self): for i in range (self .__ top, -1, -1): print (self .__ Elements [i], end = '') print ()Bây giờ, xem xét ngăn xếp đã tạo trước đó, hãy thử bật các phần tử
print (stack1.pop ())
print (stack1.pop ())
in (stack1)
print (stack1.pop ())
print (stack1.pop ())
print (stack1.pop ())
Đầu ra:
D
C
Dữ liệu ngăn xếp (Từ trên xuống dưới): B A
B
ĐẾN
không có gì để bật, đã trống rỗng
Các ứng dụng của cấu trúc dữ liệu ngăn xếp
- Ví dụ 1:
Ngăn xếp được sử dụng để triển khai thuật toán so khớp dấu ngoặc để đánh giá biểu thức số học và cả trong việc thực hiện các lệnh gọi phương thức.
Câu trả lời là 5.
- Ví dụ 2:
Clipboard trong Windows sử dụng hai ngăn xếp để triển khai các thao tác hoàn tác làm lại (ctrl + z, ctrl + y). Bạn đã từng làm việc trên các trình soạn thảo văn bản của Windows như MS-Word, Notepad, v.v. Đây là một văn bản được viết bằng MS-Word. Quan sát văn bản thay đổi như thế nào khi nhấp Ctrl-Z và Ctrl-Y.
Đây là một đoạn mã mô phỏng hoạt động hoàn tác làm lại. Xem qua mã và quan sát cách ngăn xếp được sử dụng trong việc triển khai này.
#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ Elements = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): trả về True return False def is_empty (self): if (self .__ top == - 1): trả về True return False def push (self, data): if (self.is_full ()): print ('Ngăn xếp đã đầy !!') else: self .__ top + = 1 self .__ element [self .__ top] = data def pop (self): if (self.is_empty ()): print ('Ngăn xếp trống! ! ') else: data = self .__ Elements [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' Ngăn xếp trống ') else: index = self .__ top while (index> = 0): print (self .__ Elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # Bạn có thể sử dụng __str __ () dưới đây để in các phần tử của Đối tượng DS trong khi gỡ lỗi def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ Elements [index])) index- = 1 msg = ' '.join (msg) msg =' Stack data (Top to Bottom): '+ msg return ms g # chức năng triển khai thao tác xóa hoặc xóa lùi def remove (): global clipboard, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ('Remove:', clipboard) # chức năng triển khai thao tác hoàn tác def undo (): global clipboard, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Không có dữ liệu nào để hoàn tác') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Undo:', clipboard) # chức năng thực hiện thao tác redo def redo (): global clipboard, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Không có dữ liệu để làm lại ') else: data = redo_stack.pop () if (dữ liệu không có trong khay nhớ tạm): print (' Không có dữ liệu nào để làm lại ') redo_stack.push (dữ liệu) else: clipboard.remove (dữ liệu) undo_stack.push ( data) print ('Redo:', clipboard) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (clipboard)) redo_stack = Stack (len (clipboard)) remove () undo () redo ()Đầu ra:
Xóa: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]
Hoàn tác: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’]
Làm lại: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]
cách sử dụng toán tử bitwise trong java
Với điều này, chúng ta đã kết thúc bài viết Cấu trúc dữ liệu ngăn xếp trong Python. Nếu bạn đã hiểu và tự chạy mã thành công, bạn không còn là người mới đối với Cấu trúc dữ liệu ngăn xếp.
Có một câu hỏi cho chúng tôi? Vui lòng đề cập đến nó trong phần bình luận của bài viết này và chúng tôi sẽ liên hệ lại với bạn trong thời gian sớm nhất.
Để có kiến thức chuyên sâu về Python cùng với các ứng dụng khác nhau của nó, bạn có thể đăng ký tham gia trực tiếp với hỗ trợ 24/7 và truy cập trọn đời.