Trong hướng dẫn này mình sẽ giới thiệu các bạn cách để tạo Stack bằng mảng một chiều. Ở bài trước chúng ta đã tìm hiểu cách cài đặt Stack bằng danh sanh liên kết rồi. Đây là hai cách cơ bản nhất để có thể cài đặt Stack.
Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như: isEmpty(), isFull(), push(), top(), pop(). Đây là các hàm cơ bản nhưng rất cần thiết cho Stack, hầu hết khi làm việc với Stack cần phải có các hàm này.
1. Hàm isEmpty và isFull
Trước khi tạo các hàm isEmpty() và isFull() để kiểm tra Stack rỗng hay đầy thì ta phải tạo một số biến cơ bản cần sử dụng trong Stack:
- curren_size: chúng ta sẽ khởi tạo cho nó bằng -1, đây là size hiện tại của Stack.
- MAX_SIZE: chúng ta sẽ khởi tạo cho nó bằng 100, đây là size tối đa của Stack.
- stack[MAX_SIZE]: đây là một mảng stack với số phần tử tối đa là MAX_SIZE.
/* tạo các biến cơ bản */ //tạo size hiện tại và khởi tạo cho nó bằng -1 int curren_size = -1; //tạo một hằng số làm size max = 100 const int MAX_SIZE = 100; //tạo một mảng stack với số phần tử bằng max int stack[MAX_SIZE];
Hàm isEmpty
Hàm kiểm tra Stack có tồn tại phần tử hay không là một hàm rất quan trọng. Vì khi muốn thực hiện các thao tác như xóa đối với Stack ta cần biết được trong Stack có tồn tại phần tử hay không, nếu không tồn tại thì ta không thể xóa phần tử trong Stack được.
Để kiểm tra Stack rỗng hay không rất đơn giản, vì lúc đầu ta đã khởi tạo cho biến curren_size = -1, vậy nên ta chỉ cần kiểm tra nếu curren_size = -1 thì tức là trong Stack chưa có gì, khi đó ta chỉ cần return và kết thúc hàm.
/* kiểm tra stack rỗng */
bool isEmpty(){
//kiểm tra nếu curren_size == -1 thì return và kết thúc hàm
return (curren_size == -1);
}Hàm isFull
Tương tự như hàm kiểm tra Stack rỗng hay không, việc kiểm tra Stack đã đầy hay chưa cũng rất quan trọng. Vì khi muốn thêm một phần tử nào đó vào Stack ta cần biết được trong Stack còn chỗ trống hay không, nếu Stack đã đầy thì ta không thể thêm phần tử vào Stack được.
Để kiểm tra Stack đã đầy hay chưa ta chỉ cần kiểm tra nếu curren_size == MAX_SIZE thì ra return rồi kết thúc hàm.
/* kiểm tra stack đầy */
bool isFull(){
//kiểm tra neeys curren_size == MAX_SIZE thì return và kết thúc hàm
return (curren_size == MAX_SIZE);
}2. Hàm Push
Sau khi đã tạo các hàm điều kiện isEmpty() và isFull() ta sẽ bắt đầu thực hiện tạo hàm thêm phần tử vào Stack. Nếu không có dữ liệu ta không thể thực hiện các thao tác khác trên Stack được, vì vậy đây là một bước cũng khá quan trọng.
Như đã nói thì để có thể thêm một phần tử vào Stack thì trong Stack vẫn còn chỗ trống, vì vậy trước tiên ta cần sử dụng hàm isFull() để kiểm tra xem Stack đã đầy hay chưa, nếu chưa đầy thì ta mới thực hiện các câu lệnh.
- Tăng curren_size lên để tạo thêm chỗ trống trong stack để thêm phần tử mới vào.
- Gán data vào vị trí curren_size trong Stack.
Nếu trong Stack đã đầy thì thông báo Stack đã đầy và kết thúc hàm.
/* hàm thêm phần tử vào Stack */
void push(int data){
//việc đầu tiên ta kiểm tra xem stack đã đầy hay chưa, nếu chưa tha thực hiện:
if(!isFull()){
//tăng curren_size lên để tạo thêm chổ trống trong stack để thêm phần tử mới vào
curren_size++;
//sau đó gán data vào đúng vị trí curren_size trong stack
stack[curren_size] = data;
}
//ngược lại nếu trong stack đã đầy thì thông báo cho người dùng biết rằng stack đã đầy
else{
cout<<"Stack đã đầy !!"<<endl;
}
}3. Hàm Top
Hàm top() là một hàm lấy giá trị ở trên đầu (top) trong Stack nhưng không xóa nó khỏi Stack, giống như ta chỉ xem phần tử đầu thôi chứ không xóa nó.
Việc đầu tiên ta sẽ kiểm tra xem Stack có tồn tại phần tử hay không, nếu Stack có tôn tại phần tử thì ta bắt đầu thực hiện các câu lệnh:
- Gán giá trị ở vị trí curren_size cho biến data.
- Return giá trị data
Ngược lại nếu trong Stack rỗng thì thông báo và kết thúc hàm.
/* lấy phần tử ở top nhưng không xóa nó khỏi stack */
int top(){
//kiểm tra xem stack có rỗng hay không, nếu không ta thực hiện:
if(!isEmpty()){
//gán giá trị ở vị trí curren_size cho biến data
int data = stack[curren_size];
//sau đó return data
return data;
}
//ngược lại nếu stack rỗng thì thông báo cho người dùng biết stack rỗng
else{
cout<<"Stack rỗng !!"<<endl;
}
}4. Hàm Pop
Tương tự như hàm top(), hàm pop() cũng có nhiệm vụ là lấy phần tử trên cùng (top) trong Stack nhưng đồng thời sẽ xóa nó khỏi Stack. Đây là điểm khác nhau giữa hai hàm lấy phần tử này.
Ta cũng sẽ phải kiểm tra xem Stack có tồn tại phần tử hay không, nếu có tồn tại phần tử thì ta thực hiện các câu lệnh:
- Gán giá trị ở vị trí curren_size cho biến data.
- Giảm curren_size đi vì hàm pop() sau khi lấy sẽ xóa phần tử đó khỏi Stack.
- Return giá trị data
Ngược lại nếu Stack rỗng thì thông báo và kết thúc hàm.
/*lấy phần tử ở top và xóa nó khỏi stack*/
int pop(){
//kiểm tra xem stack có rỗng hay không, nếu không ta thực hiện:
if(!isEmpty()){
//gán giá trị ở vị trí curren_size cho biến data
int data = stack[curren_size];
//giảm curren_size đi vì hàm pop() sau khi lấy sẽ xóa phần tử đó khỏi stack
curren_size--;
//sau đó return data
return data;
}
//ngược lại nếu stack rỗng thì thông báo cho người dùng biết stack rỗng
else{
cout<<"Stack rỗng !!"<<endl;
}
}
5. Ví dụ xây dựng một cấu trúc Stack hoàn chỉnh
Trong ví dụ này mình sẽ thực hiện tạo một mảng stack[] là các số nguyên, sau đó thêm một số phần tử sẵn trong Stack. Mình sẽ thực hiện các thao tác như hiển thị giá trị trên cùng, xóa giá trị trên cùng trong Stack. Các bạn có thể thao khảo code dưới đây, trong đó mình có chú thích cho các bạn dễ hiểu.
Full code:
#include <iostream>
using namespace std;
/* tạo các biến cơ bản */
//tạo size hiện tại và khởi tạo cho nó bằng -1
int curren_size = -1;
//tạo một hằng số làm size max = 100
const int MAX_SIZE = 100;
//tạo một mảng stack với số phần tử bằng max
int stack[MAX_SIZE];
/* kiểm tra stack rỗng */
bool isEmpty(){
//kiểm tra nếu curren_size == -1 thì return và kết thúc hàm
return (curren_size == -1);
}
/* kiểm tra stack đầy */
bool isFull(){
//kiểm tra neeys curren_size == MAX_SIZE thì return và kết thúc hàm
return (curren_size == MAX_SIZE);
}
/* hàm thêm phần tử vào Stack */
void push(int data){
//việc đầu tiên ta kiểm tra xem stack đã đầy hay chưa, nếu chưa tha thực hiện:
if(!isFull()){
//tăng curren_size lên để tạo thêm chổ trống trong stack để thêm phần tử mới vào
curren_size++;
//sau đó gán data vào đúng vị trí curren_size trong stack
stack[curren_size] = data;
}
//ngược lại nếu trong stack đã đầy thì thông báo cho người dùng biết rằng stack đã đầy
else{
cout<<"Stack đã đầy !!"<<endl;
}
}
/* lấy phần tử ở top nhưng không xóa nó khỏi stack */
int top(){
//kiểm tra xem stack có rỗng hay không, nếu không ta thực hiện:
if(!isEmpty()){
//gán giá trị ở vị trí curren_size cho biến data
int data = stack[curren_size];
//sau đó return data
return data;
}
//ngược lại nếu stack rỗng thì thông báo cho người dùng biết stack rỗng
else{
cout<<"Stack rỗng !!"<<endl;
}
}
/*lấy phần tử ở top và xóa nó khỏi stack*/
int pop(){
//kiểm tra xem stack có rỗng hay không, nếu không ta thực hiện:
if(!isEmpty()){
//gán giá trị ở vị trí curren_size cho biến data
int data = stack[curren_size];
//giảm curren_size đi vì hàm pop() sau khi lấy sẽ xóa phần tử đó khỏi stack
curren_size--;
//sau đó return data
return data;
}
//ngược lại nếu stack rỗng thì thông báo cho người dùng biết stack rỗng
else{
cout<<"Stack rỗng !!"<<endl;
}
}
int main() {
int lc;
//ta thực hiện thêm một vài phần tử vào stack
//cụ thể ta sẽ thêm những số sau: 10, 11, 12, 13, 14, 15, 16
cout<<"Danh sách các số bao gồm: 10, 11, 12, 13, 14, 15, 16";
for(int i = 10; i <= 16; i++){
push(i);
}
do{
cout << "\n\n\t\t ============== Menu ==============";
cout << "\n\t1. Hiển thị phần tử đầu Stack";
cout << "\n\t2. Xóa phần tử đầu Stack";
cout << "\n\t0. Ket thuc";
cout << "\n\n\t\t ============== End ==============";
cout<<"\nNhập lựa chọn bạn muốn chọn: ";
cin>> lc;
switch(lc){
case 0: break;
case 1:
cout<<"Phần tử đầu tiên trong Stack: "<<top();
break;
case 2:
pop();
cout<<"Xóa phần tử top thành công !!!";
break;
default:
cout<<"\nNhập sai, vui lòng nhập lại!";
}
} while(lc);
cout<<"Chương trình này được đang tại Freetuts.net";
}
Kết quả: Mình đã khởi tạo sẵn các giá trị 10, 11, 12, 13, 14, 15, 16 trong Stack.
6. Kết luận
Như vậy là chúng ta đã tìm hiểu xong cách cài đặt Stack bằng mảng một chiều, các bạn hãy nắm rõ cách cài đặt Stack bằng cả mảng và cả danh sách liên kết nhé. Vì mỗi bài toán ta cần sử dụng một cấu trúc lưu trữ khác nhau, vậy nên hãy sử dụng nó một cách linh hoạt. Ở các bài tiếp theo mình sẽ áp dụng Stack để giải một số bài toán cơ bản trong C++, các bạn hãy chú ý theo dõi nhé !!!
Thuật toán căn bản 
Danh sách liên kết đơn 
Danh sách liên kết đôi 
Cấu trúc cây 
Ngăn xếp Stack 
Hàng đợi Queue 
