Stack là cấu trúc dữ liệu Last In First Out. Ngăn xếp được sử dụng trong các lĩnh vực khác nhau để đánh giá các biểu thức, gọi và chiến lược đệ quy, v.v. Ngăn xếp có một số hoạt động nguyên thủy. Ở đây chúng ta sẽ thấy các hoạt động đó của ngăn xếp và xem một ví dụ sử dụng ngăn xếp ADT.
ADT (kiểu dữ liệu trừu tượng) là loại kiểu dữ liệu đặc biệt, có hành vi được xác định bởi một tập hợp các giá trị và tập hợp các hoạt động. Từ khóa “Abstract” được sử dụng vì chúng ta có thể sử dụng các kiểu dữ liệu này, chúng ta có thể thực hiện các thao tác khác nhau. Nhưng những hoạt động đó hoạt động như thế nào thì hoàn toàn bị ẩn với người dùng. ADT được tạo bằng các kiểu dữ liệu nguyên thủy, nhưng lôgic hoạt động bị ẩn.
Đây là một vài thao tác hoặc chức năng của Stack ADT.
- isFull (), được sử dụng để kiểm tra xem ngăn xếp đã đầy hay chưa
- isEmpry (), được sử dụng để kiểm tra xem ngăn xếp có trống hay không
- push (x), được sử dụng để đẩy x vào ngăn xếp
- pop (), được sử dụng để xóa một phần tử khỏi đầu ngăn xếp
- peek (), được sử dụng để lấy phần tử cao nhất của ngăn xếp
- size (), hàm này được sử dụng để nhận số phần tử có trong ngăn xếp
Ví dụ
#include<iostream>
#include<stack>
using namespace std;
main(){
stack<int> stk;
if(stk.empty()){
cout << "Stack is empty" << endl;
} else {
cout << "Stack is not empty" << endl;
}
//insert elements into stack
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 dispay elements
while(!stk.empty()) {
int item = stk.top(); // same as peek operation
stk.pop();
cout << item << " ";
}
} Đầu ra
Stack is empty Size of the stack: 5 50 40 30 20 10