Ngăn xếp (Stack) là cấu trúc dữ liệu Last In First Out (LIFO). Dùng trong đánh giá biểu thức, gọi hàm và đệ quy. Stack có các thao tác nguyên thủy.
ADT (Abstract Data Type) - logic hoạt động bị ẩn khỏi người dùng.
Các thao tác Stack ADT
- isFull() – Kiểm tra stack đầy
- isEmpty() – Kiểm tra stack rỗng
- push(x) – Đẩy x vào stack
- pop() – Xóa phần tử đỉnh stack
- peek() – Xem phần tử đỉnh (không xóa)
- size() – Số phần tử trong stack
Ví dụ C++
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> stk;
if(stk.empty()) cout << "Stack is empty" << endl;
else cout << "Stack is not empty" << endl;
// insert
stk.push(10); stk.push(20); stk.push(30); stk.push(40); stk.push(50);
cout << "Size of the stack: " << stk.size() << endl;
// pop and display
while(!stk.empty()) {
int item = stk.top(); // peek
stk.pop();
cout << item << " ";
}
}Kết quả
Stack is empty Size of the stack: 5 50 40 30 20 10