Sự khác biệt giữa Stack và Heap

Stack vs Heap

Stack là một danh sách được sắp xếp, trong đó chèn và xóa các mục danh sách có thể được thực hiện chỉ ở một đầu gọi là hàng đầu. Do đó, stack được coi là cấu trúc dữ liệu Last in First out (LIFO). Heap là một cấu trúc dữ liệu đặc biệt dựa trên cây và nó đáp ứng một thuộc tính đặc biệt được gọi là heap property. Ngoài ra, heap là một cây hoàn chỉnh, có nghĩa là không có khoảng trống giữa lá cây i. e. trong một cây hoàn chỉnh mỗi cấp độ được điền vào trước khi thêm một cấp độ mới vào cây và các nút trong một mức nhất định được điền từ trái sang phải.

Stack là gì?

Như đã đề cập ở trên, stack là một cấu trúc dữ liệu, trong đó các phần tử được thêm vào và loại bỏ khỏi một đầu gọi là đỉnh. Stacks cho phép chỉ có hai hoạt động cơ bản được gọi là push và pop. Thao tác đẩy thêm một phần tử mới vào phía trên ngăn xếp. Thao tác pop loại bỏ một phần tử khỏi đầu ngăn xếp. Nếu ngăn xếp đã đầy, khi một thao tác đẩy được thực hiện, nó được coi là một ngăn xếp tràn. Nếu một thao tác pop được thực hiện trên một ngăn xếp đã rỗng, nó được coi là một stack underflow. Do số lượng nhỏ hoạt động có thể được thực hiện trên một ngăn xếp, nó được coi là một cấu trúc dữ liệu bị hạn chế. Ngoài ra, theo cách mà các hoạt động push và pop được xác định, rõ ràng là các phần tử đã được thêm vào cuối cùng stack đi ra khỏi ngăn xếp đầu tiên. Vì vậy ngăn xếp được coi là một cấu trúc dữ liệu LIFO.

Heap là gì?

Như đã đề cập ở trên, heap là một cây hoàn chỉnh đáp ứng các thuộc tính heap. Heap property phát biểu rằng, nếu y là một nút con của x thì giá trị được lưu trữ trong nút x phải lớn hơn hoặc bằng giá trị được lưu trữ trong nút y (giá trị (x) ≥ value (y)). Thuộc tính này ngụ ý rằng nút có giá trị lớn nhất luôn luôn được đặt ở gốc. Một đống được xây dựng bằng cách sử dụng thuộc tính này được gọi là một đống tối đa. Có một biến thể của thuộc tính heap mà các nhà nước đảo ngược này. (tức là giá trị (x) ≤ giá trị (y)). Điều này ngụ ý rằng nút có giá trị nhỏ nhất luôn luôn được đặt ở gốc, do đó được gọi là min-heap. Có rất nhiều hoạt động được thực hiện trên heaps như tìm kiếm tối thiểu (trong min-heaps) hoặc tối đa (trong max-heaps), xóa tối thiểu (trong min-heaps) hoặc tối đa (trong max-heaps), tăng (max -heaps) hoặc giảm (trong min-heaps) chìa khóa, vv

Sự khác nhau giữa Stack và Heap là gì?

Sự khác biệt chính giữa ngăn xếp và đống là trong khi stack là một cấu trúc dữ liệu tuyến tính, heap là một cấu trúc dữ liệu phi tuyến tính. Stack là một danh sách được sắp xếp theo sau thuộc tính LIFO, trong khi heap là một cây hoàn chỉnh theo sau thuộc tính heap.Hơn nữa, ngăn xếp là một cấu trúc dữ liệu hạn chế chỉ hỗ trợ một số hoạt động hạn chế là push và pop, trong khi heap hỗ trợ một loạt các hoạt động như tìm và xóa tối thiểu hoặc tối đa, tăng hoặc giảm phím và hợp nhất.