Lý thuyết

Stack là một danh sách được bổ sung 2 thao tác: thêm một phần tử vào cuối danh sách, và loại bỏ một phần tử ở cuối danh sách. Ví trí cuối của Stack được gọi là đỉnh (top).

Stack và Queue là các cấu trúc dữ liệu được sử dụng để lưu trữ các yếu tố dữ liệu và nó dựa trên một số các ví dụ có thực trong cuộc sống hàng ngày của chúng ta. Ví dụ, Stack là một chồng đĩa CD, nơi bạn có thể lấy ra và đưa vào đĩa CD thông qua đỉnh của ngăn xếp đĩa CD.

Stack in C++ Example: C++ Stack Program And Algorithm

Chủ yếu Stack có ba hàm cơ bản sau được thực hiện:

Push: Thêm một mục(phần tử, thành phần) trong stack. Nếu stack đầy, thì nó được cho là điều kiện Tràn.
Pop: Loại bỏ một mục khỏi stack. Các mục được xuất hiện theo thứ tự đảo ngược mà chúng được Push. Nếu stack trống, thì nó được cho là điều kiện trống.
Peek hoặc Top: Trả về phần tử trên cùng của stack.
isEmpty: Trả về true nếu stack trống, ngược lại là false.

Tất cả các hàm trên của stack đều có độ phức tạp O(1)

BÀI TẬP ỨNG DỤNG : Tìm Min/Max trên đoạn tịnh tiến

Sơ lược đề bài: Cho một dãy số có n phần tử, in ra max của các đoạn có độ dài k liên tiếp trong dãy

Cách làm thông thường:

Ta lặp từ 1-> n, với mỗi đoạn k, ta lặp qua đoạn k và lấy phần tử min, max.

Độ phức tạp: O(N*k)

Sử dụng stack:

Trước hết ta tìm phần tử lớn hơn nó bên phải đầu tiên
Đặt 1 biến j và i. Tại mỗi vị trí kiểm tra, ta lặp tìm phần tử lớn nhất bên phải mà vẫn thuộc vùng (i+k-1)
Chạy chay: (k = 3). A = (1, 2, 3, 1, 4, 5, 2, 3, 6)