Lập trình C: Bài 15 – Cài đặt ngăn xếp (Stack)

Tháng Một 20, 2018 nguyenvanquan7826 Chưa được phân loại 49 responses

Ngăn xếp (Stack) là một danh sách có thứ tự mà phép chèn và xóa được thực hiện tại đầu cuối của danh sách và người ta gọi đầu cuối này là đỉnh (top) của stack

stack

Trong bài này chúng ta tìm hiểu cách cài đặt Stack trên mảng và trên con trỏ

1. Stack cài đặt trên mảng

code by nguyenvanquan7826
1
2
3
4
5
6
7
#define Max 100 //so phan tu toi da cua Stack
typedef int item; //kieu du lieu cua Stack
struct Stack
{
    int Top; //Dinh Top
    item Data[Max]; //Mang cac phan tu
};

1.1 Khởi tạo danh sách rỗng, kiểm tra danh sách rỗng, đầy

code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
void Init (Stack &S) //khoi tao Stack rong
{
    S.Top = 0; //Stack rong khi Top la 0
}
 
int Isempty(Stack S) //kiem tra Stack rong
{
    return (S.Top == 0);
}
 
int Isfull(Stack S) //kiem tra Stack day
{
    return (S.Top == Max); //
}

1.2 Thêm phần tử vào Stack (Push)

Để chèn thêm phần tử vào Stack ta chèn vào vị trí Top, và tang Top lên 1 đơn vị
push

code by nguyenvanquan7826
1
2
3
4
5
6
7
8
void Push(Stack &S, item x) //them phan tu vao Stack
{
    if (!Isfull(S))
    {
        S.Data[S.Top] = x; //Gan du lieu
        S.Top ++; //Tang Top len 1
    }
}

1.3 Lấy dữ liệu tại Top nhưng không xóa (Peak)

code by nguyenvanquan7826
1
2
3
4
int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
    return S.Data[S.Top-1]; //Lay du lieu tai Top
}

1.4 Xóa và lấy dữ liệu tại Top (Pop)

pop

code by nguyenvanquan7826
1
2
3
4
5
6
7
8
int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
    if (!Isempty(S))
    {
        S.Top --; //Giam Top
        return S.Data[S.Top]; //Lay du lieu tai Top
    }
}

1.5 Code toàn bộ chương trình (full)

link dự phòng

2. Stack cài đặt trên con trỏ

Stack trên con trỏ vẫn là stack bình thường nhưng link hoạt hơn vì nó dùng con trỏ để cấp phát và quản lý, không bị thừa hoặc thiếu gì cả.

stack pointer

2.1 Xây dựng cấu trúc

code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
typedef int item; //kieu du lieu
struct Node
{
    item Data; //du lieu
    Node *Next; //link
};
typedef struct Stack
{
    Node *Top;
};

2.2 Khởi tạo danh sách rỗng, kiểm tra danh sách rỗng, độ dài danh sách

code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
void Init (Stack &S) //khoi tao Stack rong
{
    S.Top = NULL;
}
 
int Isempty(Stack S) //kiem tra Stack rong
{
    return (S.Top == NULL);
}
 
int Len (Stack S)
{
    Node *P = S.Top;
    int i=0;
    while (P != NULL) //trong khi chua het Stack thi van duyet
    {
        i++;
        P = P->Next;
    }
    return i;
}

2.3 Tạo 1 Node

code by nguyenvanquan7826
1
2
3
4
5
6
7
Node *MakeNode(item x) //tao 1 Node
{
    Node *P = (Node*) malloc(sizeof(Node));
    P->Next = NULL;
    P->Data = x;
    return P;
}

2.4 Chèn phần tử vào Stack (Push)

Để chèn phần tử vào Stack thì chỉ cần cho con trỏ Note đó trỏ và Top, rồi Top trỏ lại nó là xong

push

code by nguyenvanquan7826
1
2
3
4
5
6
void Push(Stack &S, item x) //them phan tu vao Stack
{
    Node *P = MakeNode(x);
    P->Next = S.Top;
    S.Top = P;
}

2.5 Lấy dữ liệu tại Top nhưng không xóa (Peak)

code by nguyenvanquan7826
1
2
3
4
int Peak(Stack S) //Lay phan tu o dau Stack nhung khong xoa
{
    return S.Top->Data;
}

2.6 Xóa và lấy dữ liệu tại Top (Pop)

Ta chỉ cần cho con trỏ Top trỏ đến vị trí thứ 2 thôi.

pop

code by nguyenvanquan7826
1
2
3
4
5
6
7
8
9
int Pop(Stack &S) //Loai bo phan tu khoi Stack
{
    if (!Isempty(S))
    {
        item x = S.Top->Data; //luu lai gia tri
        S.Top = S.Top->Next; //Xoa phan tu Top
        return x;
    }
}

2.7 Chương trình hoàn chỉnh (full code)

link dự phòng

3. Sử dụng Stack có sẵn trong C++

Trong C++ đã xây dựng sẵn các phương thức (hàm) liên quan đến Stack, ta chỉ việc khai báo và sử dụng

code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream> // io
#include <stack> // use stack
 
using namespace std;
 
int main() {
    stack <int> S; // khai bao Stack voi kieu du lieu la int
     
    for (int i = 0; i < 10; i++) {
        S.push(i*78 + 26); // chen cac phan tu vao stack
    }
     
    cout << "Do dai stack: " << S.size() << "\n";
     
    // xuat tat ca phan tu trong stack
    while (!S.empty()) {    // trong khi stack chua trong
        int x = S.top();    // lay gia tri top
        S.pop();            // loai bo khoi stack
        cout << x << "  ";
    }
    cout << "\n";
     
    return 0;
}

4. VÍ dụ về ứng dụng của Stack

Stack có nhiều ứng dụng, sau đây là 1 ứng dụng trong chuyển đổi cơ số. Code sau sẽ chuyển số cơ số 10 sang cơ số x nhập từ bàn phím

code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream> // io
#include <stack> // use stack
 
using namespace std;
 
int main() {
    char num[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
    stack <char> S; // khai bao Stack voi kieu du lieu la int
     
    int coSo, so, du;
     
    cout << "Nhap so can chuyen: ";
    cin >> so;
     
    cout << "Nhap co so can chuyen: ";
    cin >> coSo;
     
    // chuyen doi bang cach dua vao Stack
    while(so) {
        du = so % coSo;
        S.push(num[du]);
        so /= coSo;
    }
     
    // Xuat ra
    while(!S.empty()) {
        cout << S.top();
        S.pop();
    }
     
    return 0;
}

[rps-include post=”2703″ shortcodes=”false”]