Khái niệm Ngăn Xếp (Stack) và Cài đặt Ngăn Xếp với C++ - Cấu trúc dữ liệu và giải thuật

Stack là gì: stack là một kiểu dữ liệu trừu tượng, một cấu trúc có nhiều nút giống như List vậy (Danh sách liên kết) nhưng chúng ta chỉ được phép thêm nút mới vào đỉnh stack (tác vụ push) hoặc xóa nut ở đỉnh stack (tác vụ Pop), hay chúng ta còn gọi cơ chế của stack là cơ chế Lifo (vào trước ra sau). Bạn cứ hình dung stack như một cái băng đạn mỗi nút là một viên đạn, viên đạn nào vào trước thì ra sau, viên nào vào sau thì ra trước. OK
Còn stack để làm gì ư. Stack để giải quyết những vấn đề theo cơ chế LIFO như chuyển một biểu thức dạng trung tố về hậu tố.

Sau đây là mô hình cho Stack-ADT
1. Mô tả dữ liệu:

• Có nhiều nút cùng một kiểu
• Có đỉnh stack (top)

2. Mô tả các tác vụ trên stack

initialize
Chức năng: Khởi động stack
Dữ liệu nhập: Không
Dữ liệu xuất: stack top về vị trí khởi đầu.

empty:
Chức năng kiểm tra stack có bị rỗng không.
Dữ liệu nhập: Không
Dữ liệu xuất: True or False (True: khi stack rỗng, False: stack không bị rỗng).

pusth
Chức năng: thêm nút mới tại đỉnh stack
Dữ liệu nhập: nút mới.
Dữ liệu xuất: không

pop
Chức năng: xóa nút tại đỉnh stack.
Dữ liệu nhập: Không.
Điều kiện: stack không bị rỗng.
Dữ liệu xuất: nút bị xóa.

Stacktop:

Chức năng: truy xuất nút tại đỉnh stack.
Dữ liệu nhập: Không.
Điều kiện: stack không bị rỗng.
Dữ liệu xuất: nút tại đỉnh stack.

Stacksize
Chức năng: xác định số nút hiện có trong stack.
Dữ liệu: Không.
Dữ liệu xuất: số nút hiện có trong stack.

Clearstack:
Chức năng: xóa tất cả các nút ở trong stack.
Dữ liệu nhập: không.
Dữ liệu xuất:stack top về vị trí khởi đầu.

copystack:
Chức năng: copystack thành stack thành stack mới.
Dữ liệu nhập: stack nguồn.
Dữ liệu xuất: stack đích giống stack nguồn.

Phương pháp cài đặt stack

Có rất nhiều cách cài đặt một stack nhưng đơn giản cũng như để dễ hình dung nhất là cài đặt bằng mảng hay còn gọi là cài đặt theo kiểu kế tiếp. Ngoài ra còn nhiều cách cài đặt khác như cài đặt bằng Danh sách liên kết (DSLK đơn, DSLK vòng, DSLK kép, DSLK vòng+kép mình thấy cài đặt bằng DSLK vòng +kép là hay nhất)

Sau đây mình sẽ giới thiệu cho bạn về cách cài đặt một stack theo kiểu kế tiếp (bằng mảng đó) minh họa bằng ngôn ngữ C++   

1. const int Max = 100;
2. class stack
3. {
4.       private:
5.        int top;
6.       int nodes[Max];
7.    public:
8.        stack()  // khoi tao stack
9.       {
10.            top = -1; // gan top = -1
11.       }
12.        bool empty()// Kiem tra xem stack co rong hay khong
13.       {
14.            if(top == -1)
15.              return true;
16.          else
17.              return false;
18.       }
19.       void push(int data)
20.       {
21.          if(top == Max-1)
22.              cout<<"Stack bi day";  // truong hop stack bi day
23.          else
24.                nodes[++top] = data;
25.       }
26.       int pop()
27.       {
28.            if(empty())  //truong hop stack bi rong
29.              cout<<"Stack bi rong ";
30.          else
31.              return(nodes[top--]);
32.       }
33.       int stacktop()
34.       {
35.            if(empty())
36.               cout<<"Stack bi rong ";
37.              //su ly truong hop stack bi rong
38.          else
39.              return(nodes[top]);
40.       }
41. };

 Nguồn: Cộng đồng C Việt