Trong bài này, tôi cùng các bạn sẽ cùng nhau đi chi tiết vào các thao tác cơ bản khi cài đặt stack bằng mảng với ngôn ngữ C/C++.

Các thao tác cơ bản khi cài đặt stack bằng mảng bao gồm:

• Khởi tạo stack: Init (S)
• Kiểm tra stack rỗng: Empty (S)
• Kiểm tra stack đầy: IsFull (S)
• Đưa phần tử vào Stack: Push(S,x)
• Lấy phần tử ra khỏi Stack: Pop (S, x)

Đầu tiên ta sẽ sử dụng với cách khai báo một stack sử dụng mảng ở bài trước như sau:

#define MAX 100
struct stack{
    int top;
    int A[MAX];
};
typedef struct stack STACK;

1.Các hàm khởi tạo và kiểm tra stack bằng mảng

1.1 Hàm khởi tạo stack

Stack ban đầu khi mới được khởi tạo luôn luôn mang dữ liệu rỗng (hay chưa có phần tử nào). Vì vậy sau bước khởi tạo ta cần gán phần tử Top của stack đó về giá trị -1 để đảm bảo đúng yêu cầu stack rỗng khi được khởi tạo.

Hàm khởi tạo void Init(STACK &s) dưới đây nhận STACK &s là stack cần được khởi tạo ban đầu sẽ gán phần tử top của stack đó về giá trị -1.

void Init (STACK &s){
    //gan phan tu top cua stack bang -1 de khoi tao
    s.top=-1;
}

1.2 Hàm kiểm tra stack rỗng

Hàm kiểm tra rỗng đối với stack có chức năng kiểm tra xem stack đó có phần tử nào hay không? Nếu stack đó rỗng thì có thể thực hiện thao tác thêm phần tử vào và nếu rỗng thì không được phép lấy phần tử ra.

Hàm int Empty(STACK s) truyền vào STACK s để kiểm kiểm tra xem stack đó có rỗng hay không? Nếu rỗng thì phần tử top của stack đó bằng -1

int Empty (STACK s){
    //neu phan tu top bang -1 thi stack rong va return 1
    if (s.top == -1){
        return 1;
    }
    //nguoc lai return 0
    return 0;
}

1.3 Hàm kiểm tra stack đầy

Khi cài đặt stack bằng mảng, ta cần nhập vào số lượng phần tử của mảng đó. Vì vậy đôi khi số lượng phần tử trong stack đầy rồi thì ta không được phép thêm phần tử vào stack nữa và để kiểm tra stack đã đầy hay chưa ta cần một hàm kiểm tra stack đầy.

Hàm int IsFull (STACK s) nhận STACK s làm danh sách cần kiểm tra đã đầy hay chưa? Điều kiện kiểm tra đầy là: Nếu phần tử top của stack bằng với kích thước MAX – 1 thì stack đó đã đầy:

int IsFull (STACK s){
    //neu phan tu top cua stack bang MAX - 1 thi stack da day thi return 1
    if (s.top==MAX-1){
        return 1;
    }
    //nguoc lai return 0
    return 0;
}

2.Các hàm thao tác push và pop với stack bằng mảng

2.1 Hàm push trong stack

Push chính là việc ta đưa phần tử vào trong stack đó, đối với việc cài đặt stack bằng mảng 1 chiều, khi thực hiện thao tác push chính là việc ta thêm phần tử vào cuối mảng.

Hàm void Push(STACK &s,int x) nhận vào 2 tham số là STACK &s chính là stack cần thêm phần tử vào và int x là dữ liệu được thêm vào. Trước khi thực hiện push cần kiểm tra điều kiện rằng stack đó chưa đầy mới được thêm phần tử.

Việc thêm phần tử vào stack chính là việc thêm phần tử vào cuối mảng vì vậy ta chỉ cần tăng chỉ số top của stack đó lên 1 đơn vị và gán phần tử mảng tại chỉ số top (hay phần tử cuối của mảng) bằng giá trị cần thêm.

void Push(STACK &s,int x){
    // neu stack chua day thi thuc hien push
    if(IsFull(s)==0){
        //tang chi so top len 1 don vi
        s.top++;
        //gan phan tu mang tai vi tri top bang gia tri x
        s.A[s.top]=x;
    }
}

Chú ý: Biến int x được truyền vào là do stack của ta đang sử dụng mảng int A[MAX] (vui lòng xem lại ở phần đầu bài viết này!). Trong một số bài toán khác ta có thể thay thế int bằng các kiểu dữ liệu khác như: float, char…hay kiểu dữ liệu SinhVien mà ta tự định nghĩa.

2.2 Hàm pop trong stack

Ta đã biết hàm push ở trên để thêm phần tử vào stack và khi đã thêm vào rồi thì ta cần có một hàm để lấy phần tử trong stack ra. Vì vậy ta có hàm pop để lấy phần tử Top trong stack ra và đồng thời sẽ thực hiện xóa luôn phần tử đó khi thực hiện lấy phần tử.

Hàm int Pop(STACK &s) nhận tham số STACK &s là stack cần được lấy phần tử ở trên đỉnh (top) ra và sau đó thực hiện xóa luôn phần tử đó.

int Pop(STACK &s){
    //khai bao bien x de chua du lieu
    int x;
     // neu stack khac rong
    if(!Empty(s)){
        //thuc hien gan phan tu cuoi cua stack bang x
        x = s.A[s.top];
        //giam so luong phan tu mang di 1 don vi
        s.top--;
    }
    //tra ve x duoc gan bang phan tu cuoi cung cua stack
    return x;
}

Chú ý: Hàm pop trên có kiểu trả về int Pop() là vì dữ liệu trong stack đang được lưu trữ là mảng mang dữ liệu số nguyên int A[MAX]. Trong một số bài toán ta hoàn toàn có thể thay thế kiểu dữ liệu đó bằng float, char…hay kiểu dữ liệu SinhVien mà ta tự định nghĩa.

2.3 Hàm top trong stack

Ngược lại với hàm pop là lấy phần tử ở trên đỉnh (top) của stack và xóa luôn phần tử đó thì ta có hàm top chỉ thực hiện lấy phần tử trên đỉnh (top) của stack ra và hoàn toàn không xóa phần tử của stack.

int Top(STACK &s){
    //khai bao bien x de chua du lieu
    int x;
    // stack khac rong
    if(!Empty(s)){
        //thuc hien gan phan tu cuoi bang x
        x = s.A[s.top];
        //tra ve x duoc gan bang phan tu cuoi cung cua mang
        return x;
    }else{ //neu stack do rong thi tra ve NULL
        return NULL;
    }
}

Tương tự như hàm Pop thì hàm Top cũng có kiểu dữ liệu trả về cho hàm là int Top() các bạn có thể xem lại phần giải thích ở phần Pop.

3.Nhập xuất phần tử vào mảng ngăn xếp stack

Với việc nhập xuất phần tử với stack ta sẽ sử dụng lại các hàm push, pop và top ở trên!

Hàm nhập N phần tử vào stack như sau:

void Input(STACK &s, int n){
    //duyet tu 0 den n
    for(int i = 0; i< n; i++){
        //thuc hien nhap gia tri vao bien x
        int x;
        printf("Nhap gia tri phan tu thu %d: ",i);
        scanf("%d",&x);
        //thuc hien push vao stack
        Push(s,x);
    }
}

Hàm xuất các phần tử trong stack ra như sau:

void Output(STACK s){
    //duyet tu phan tu top ve phan tu cuoi stack
    for(int i = s.top; i > -1; i--){
        //hien thi ra ket qua
        printf("%d \n",s.A[i]);
    }
}

4.Chương trình cài đặt stack bằng mảng hoàn chỉnh

Phần trên ta đã tìm hiểu các hàm cần thiết cho việc cài đặt stack bằng mảng, chương trình dưới đây sẽ lắp ghép hoàn chỉnh các hàm trên lại thành một chương trình cài đặt stack hoàn chỉnh.

#include <stdio.h>
#define MAX 100
struct stack{
    int top;
    int A[MAX];
};
typedef struct stack STACK;

void Init (STACK &s){
    //gan phan tu top cua stack bang -1 de khoi tao
    s.top=-1;
}

int Empty (STACK s){
    //neu phan tu top bang -1 thi stack rong va return 1
    if (s.top == -1){
        return 1;
    }
    //nguoc lai return 0
    return 0;
}

int IsFull (STACK s){
    //neu phan tu top cua stack bang MAX - 1 thi stack da day thi return 1
    if (s.top==MAX-1){
        return 1;
    }
    //nguoc lai return 0
    return 0;
}

void Push(STACK &s,int x){
    // neu stack chua day thi thuc hien push
    if(IsFull(s)==0){ 
        //tang chi so top len 1 don vi
        s.top++;
        //gan phan tu mang tai vi tri top bang gia tri x
        s.A[s.top]=x;
    }
}

int Pop(STACK &s){
    //khai bao bien x de chua du lieu
    int x;
     // neu stack khac rong
    if(!Empty(s)){
        //thuc hien gan phan tu cuoi cua stack bang x
        x = s.A[s.top];
        //giam so luong phan tu mang di 1 don vi
        s.top--;
    }
    //tra ve x duoc gan bang phan tu cuoi cung cua stack
    return x;
}

int Top(STACK &s){
    //khai bao bien x de chua du lieu
    int x;
     // stack khac rong
    if(!Empty(s)){
        //thuc hien gan phan tu cuoi bang x
        x = s.A[s.top];
        //tra ve x duoc gan bang phan tu cuoi cung cua mang
        return x;
    }else{ //neu stack do rong thi tra ve NULL
        return NULL;
    }
}
void Input(STACK &s, int n){
    //duyet tu 0 den n
    for(int i = 0; i< n; i++){
        //thuc hien nhap gia tri vao bien x
        int x;
        printf("Nhap gia tri phan tu thu %d: ",i);
        scanf("%d",&x);
        //thuc hien push vao stack
        Push(s,x);
    }
}
void Output(STACK s){
    //duyet tu phan tu top ve phan tu cuoi trong stack
    for(int i = s.top; i > -1; i--){
        //hien thi ra ket qua
        printf("%d \n",s.A[i]);
    }
}
int main(){
    //tao mot stack s
    STACK s;
    //nhap n phan tu can them vao stac
    int n;
    printf("Nhap n: ");
    scanf("%d",&n);
    //khoi tao stack s
    Init(s);
    //goi ham nhap n phan tu vao stack
    Input(s,n);
    //goi ham xuat cac phan tu o tron stact
    printf("Stack vua nhap la: \n");
    Output(s);
    //lay phan tu top cua stack ra nhung khong xoa
    printf("Top cua stack voi ham top %d",Top(s));
    //lay phan tu top cua stack ra va xoa
    printf("\nTop cua stack voi ham pop %d \n",Pop(s));
    printf("Stack sau khi pop la\n");
    Output(s);
}