Cấu trúc dữ liệu - Ngăn xếp

Nov 06 2022
Thuật toán và cấu trúc dữ liệu từ 0 đến anh hùng
Trong khoa học máy tính, ngăn xếp là một kiểu dữ liệu trừu tượng đóng vai trò như một tập hợp các phần tử, với hai hoạt động chính: Đẩy, thêm phần tử vào tập hợp và Pop, loại bỏ phần tử được thêm gần đây nhất chưa được xóa. - Wikipedia Về cơ bản, ngăn xếp là một danh sách có thứ tự, trong đó việc chèn và xóa được thực hiện ở một đầu, nơi kết thúc thường được gọi là đầu.
Hình ảnh được tạo bằng DALL-E

Trong khoa học máy tính, ngăn xếp là một kiểu dữ liệu trừu tượng đóng vai trò như một tập hợp các phần tử, với hai hoạt động chính:

Đẩy , thêm một phần tử vào bộ sưu tập và

Pop , loại bỏ phần tử được thêm gần đây nhất mà vẫn chưa bị xóa. - Wikipedia

Về cơ bản, ngăn xếp là một danh sách có thứ tự, trong đó việc chèn và xóa được thực hiện ở một đầu, nơi kết thúc thường được gọi là đỉnh. Cuối cùng, Đầu ra (LIFO) hoặc Đầu tiên vào, Cuối cùng (FILO).

Sự giống nhau

Hãy tưởng tượng bạn làm việc trong một nhà hàng lau đĩa và bạn có những chiếc đĩa xếp chồng lên nhau trong căng tin. Tấm nằm trên cùng là tấm được lấy ra đầu tiên, tức là tấm đã được đặt ở vị trí thấp nhất sẽ nằm trong chồng lâu nhất. Do đó, có thể thấy đơn giản là tuân theo thứ tự LIFO (Last In First Out) / FILO (First In Last Out).

Thời gian phức tạp:

  • push () : O (1)
  • pop () : O (1)
  • peek () : O (1)

Bạn có thể triển khai một Ngăn xếp bằng cách sử dụng Mảng hoặc Danh sách được liên kết, có một số ưu và nhược điểm khi chọn cái này hay cái kia.

Ưu điểm:

  • Stack sử dụng Linked : An toàn hơn, đáng tin cậy hơn vì chúng không bị hỏng dễ dàng và tự động làm sạch các đối tượng.
  • Ngăn xếp sử dụng Mảng : Dễ thực hiện và con trỏ được lưu trong bộ nhớ không liên quan đến việc chúng ta có quyền truy cập ngẫu nhiên.
  • Ngăn xếp sử dụng Được liên kết: Cần có thêm bộ nhớ, tổng kích thước phải được xác định trước và nếu ngăn xếp nằm ngoài bộ nhớ có thể dẫn đến kết thúc bất thường.
  • Ngăn xếp sử dụng Mảng : Nhược điểm chính là không phát triển và thu nhỏ tùy theo nhu cầu trong thời gian chạy.

Ngăn xếp là một cấu trúc dữ liệu tuyến tính tuân theo nguyên tắc Cuối cùng vào Đầu ra trước (LIFO). Điều này có nghĩa là phần tử cuối cùng được chèn vào bên trong ngăn xếp sẽ bị loại bỏ đầu tiên.

⬅️ Mảng và danh sách liên kết | Mục lục | Tiếp theo (Sắp có) ➡️

© Copyright 2021 - 2022 | vngogo.com | All Rights Reserved