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

Cấu trúc dữ liệu STACK – QUEUE

I. STACK – Ngăn xếp
1. Khái niệm:
Một ngăn xếp là một cấu trúc dữ liệu dạng thùng chứa (container) của các phần tử (thường gọi là các nút (node)) và có hai phép toán cơ bản: push and pop. Push bổ sung một phần tử vào đỉnh (top) của ngăn xếp, nghĩa là sau các phần tử đã có trong ngăn xếp. Pop giải phóng và trả về phần tử đang đứng ở đỉnh của ngăn xếp. Trong stack, các đối tượng có thể được thêm vào stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi stack.
VD thực tế : có thể coi stack như 1 băng đạn , mỗi viên đạn là 1 phần tử. chỉ có thể lắp đạn vào đầu băng đạn (push ) và mỗi lần bắn sẽ bắn viên đạn trên cùng băng đạn ( pop). Hay còn gọi là LIFO (Last In First Out) vào trước ra trước.

2. Khai báo:
#include<stack> // thư viện
Ví dụ khai báo stack kiểu int
stack<int> s; (nếu kiểu kí tự thì khia báo stack<char>s)
s.size() : trả về kích thước hiện tại của stack (số phần tử trong stack).
s.empty() : true (1) stack nếu rỗng, và (0) ngược lại.
s.push(x) : đẩy phần tử x vào đỉnh stack.
s.pop() : loại bỏ phẩn tử ở đỉnh của stack.
s.top() : truy cập tới phần tử ở đỉnh stack.
Tất cả hàm trên đều có Độ phức tạp O(1); 

3. Ứng dụng
-Đảo ngược xâu: nhập từng kí tự xâu cho vào stack, sau đó lấy từng kí tự ra ta sẽ được 1 xâu đảo ngược.
- Chuyển hệ cơ số 10 sang cơ số 2: thực hiện liên tiếp phép chia dư n cho 2 rồi , n=n/2 và push kq phép chia dư vào stack, sau khi chia xong ta lấy các phần tử trong stack ra.
- Tính biểu thức đại số, chuyển biểu thức đại số dạng trung sang hậu tố. - Khử đệ quy (trong duyệt đồ thị DFS)