Trong khoa học máy tính, một ngăn xếp (còn gọi là bộ xếp chồng, tiếng Anh: Stack) là một cấu trúc dữ liệu trừu tượng hoạt động theo nguyên lý “vào sau ra trước” (Last In First Out (LIFO). Tức là, phần tử cuối cùng được chèn vào ngăn xếp sẽ là phần tử đầu tiên được lấy ra khỏi ngăn xếp.
Một ví dụ trực quan, bạn có một chồng sách và bạn để nó trong một cái hộp như hình phía dưới. Giả sử hộp này vừa khít các cuốn sách. Khi đó, bạn có các thao tác:
Thêm một cuốn sách vào hộp(push của stack)
Lấy một cuốn sách khỏi hộp, bạn chỉ lấy được thằng trên cùng(pop của stack)
Cấu trúc dữ liệu ngăn xếp bị giới hạn theo cách như trên. Như vậy, việc thao tác với ngăn xếp của chúng ta chỉ bao gồm các hành động sau:
Push: Thêm một phần tử vào đỉnh của ngăn xếp, số phần tử của ngăn xếp tăng lên 1.
Pop: Xóa bỏ phần tử đầu tiên ở đỉnh của ngăn xếp, số phần tử của ngăn xếp giảm đi 1.
Top: Lấy giá trị của phần tử đầu tiên ở đỉnh của ngăn xếp, số phần tử của ngăn xếp không thay đổi.
IsEmpty: Kiểm tra ngăn xếp trống hay không. Ngăn xếp trống là ngăn xếp không có phần tử nào.
IsFull: Kiểm tra ngăn xếp đã đầy hay chưa. Thao tác này không phải lúc nào cũng có.
Size: Lấy số lượng phần tử stack đang có.
2. Cài đặt ngăn xếp bằng mảng
Tại mục hướng dẫn này, mình sẽ cùng các bạn đi chi tiết từng thao tác của cấu trúc dữ liệu ngăn xếp. Chúng ta sẽ triển khai cài đặt ngăn xếp các số nguyên sử dụng mảng. Ở mục tiếp theo, tôi sẽ cung cấp cho các bạn một số cách cài đặt khác nữa.
Chúng ta sẽ sử dụng mảng 1 chiều kiểu int làm Stack stack, một biến capacity để lưu kích thước(sức chứa) của stack và một biến top để lưu chỉ số của phần tử ở top của Stack stack.
2.1. Kiểm tra stack đầy(IsFull)
Hàm này sẽ kiểm tra xem stack hiện tại đã đầy hay chưa. Nếu chỉ số top của stack đang bằng với capacity - 1, tức stack đã đầy.
cpp
1bool IsFull(int capacity){
2 if(top >= capacity - 1){
3 return true;
4 }else{
5 return false;
6 }
7}
2.2. Kiểm tra stack rỗng(IsEmpty)
Nếu như stack đang không có phần tử nào, ta sẽ gán chỉ số top = -1 để đánh dấu. Như vậy, để kiểm tra stack có đang rỗng hay không rất đơn giản. Ta chỉ cần so sánh giá trị top có phải -1 hay không mà thôi.
cpp
1bool IsEmpty(){
2 if(top == -1){
3 return true;
4 }else{
5 return false;
6 }
7}
2.3. Thêm phần tử vào đỉnh stack(Push)
Chúng ta sẽ chỉ có thể push(thêm phần tử) vào đỉnh stack khi stack chưa đầy. Nếu stack đầy, chúng ta sẽ đưa ra thông báo và không thực hiện push. Ngược lại, ta sẽ tăng top lên một đơn vị và gán giá trị cho phần tử tại chỉ số top.
cpp
1void Push(int stack[], int value, int capacity){
2 if(IsFull(capacity) == true){
3 printf("\nStack is full. Overflow condition!");
4 }else{
5 ++top;
6 stack[top] = value;
7 }
8}
2.4. Xóa phần tử khỏi đỉnh stack(Pop)
Chúng ta sẽ chỉ có thể pop(xóa phần tử) khỏi đỉnh stack khi stack không trống. Nếu stack trống, chúng ta sẽ đưa ra thông báo và không thực hiện pop. Ngược lại, ta sẽ giảm giá trị top đi một đơn vị.
cpp
1void Pop(){
2 if(IsEmpty() == true){
3 printf("\nStack is empty. Underflow condition!");
4 }else{
5 --top;
6 }
7}
2.5. Lấy giá trị phần tử ở đỉnh stack(Top)
Để lấy giá trị phần tử ở đỉnh stack, ta có thao tác rất đơn giản:
cpp
1int Top(int stack[]){
2 return stack[top];
3}
2.6. Lấy số lượng phần tử stack đang có(Size)
Biến top lưu chỉ số lớn nhất của stack. Như vậy, việc lấy size của stack cực kỳ đơn giản:
cpp
1int Size(){
2 return top + 1;
3}
Và cuối cùng, chúng ta sẽ có 1 chương trình cài đặt stack hoàn thiện như sau:
cpp
1#include <stdio.h>
2
3int top = -1;
4
5bool IsFull(int capacity){
6 if(top >= capacity - 1){
7 return true;
8 }else{
9 return false;
10 }
11}
12
13bool IsEmpty(){
14 if(top == -1){
15 return true;
16 }else{
17 return false;
18 }
19}
20
21void Push(int stack[], int value, int capacity){
22 if(IsFull(capacity) == true){
23 printf("\nStack is full. Overflow condition!");
24 }else{
25 ++top;
26 stack[top] = value;
27 }
28}
29
30void Pop(){
31 if(IsEmpty() == true){
32 printf("\nStack is empty. Underflow condition!");
33 }else{
34 --top;
35 }
36}
37
38
39int Top(int stack[]){
40 return stack[top];
41}
42
43int Size(){
44 return top + 1;
45}
46
47int main(){
48 int capacity = 3;
49 int top = -1;
50 int stack[capacity];
51
52 // pushing element 5 in the stack .
53 Push(stack, 5, capacity);
54
55 printf("\nCurrent size of stack is %d", Size());
56
57 Push(stack, 10, capacity);
58 Push(stack, 24, capacity);
59
60 printf("\nCurrent size of stack is %d", Size());
61
62 // As the stack is full, further pushing will show an overflow condition.
63 Push(stack, 12, capacity);
64
65 //Accessing the top element
66 printf("\nThe current top element in stack is %d", Top(stack));
67
68 //Removing all the elements from the stack
69 for(int i = 0 ; i < 3;i++)
70 Pop();
71 printf("\nCurrent size of stack is %d", Size());
72
73 //As the stack is empty , further popping will show an underflow condition.
74 Pop();
75}
Kết quả chạy chương trình trên:
cpp
1Current size of stack is 1
2Current size of stack is 3
3Stack is full. Overflow condition!
4The current top element in stack is 24
5Current size of stack is 0
6Stack is empty. Underflow condition!
stack_c_plus_plus
3. Ứng dụng của stack
Chúng ta sẽ sử dụng stack vào bài toán kiểm tra dãy ngoặc có hợp lệ hay không.
Bạn có một dãy các dấu ngoặc bao gồm ngoặc đóng ‘)’ và ngoặc mở ‘(‘. Bạn phải kiểm tra xem dãy ngoặc đó có hợp lệ hay không.
Một dãy ngoặc hợp lệ thì sẽ không thừa dấu ngoặc hoặc không có dấu ngoặc lẻ loi, chẳng hạn như: (), (()), ((()))() là các dãy ngoặc hợp lệ. Còn ((, ()), (()( là các dãy ngoặc không hợp lệ.
Bạn có thể giải quyết bài toán này với stack. Hãy xem chúng ta làm như thế nào nhé.
Ý tưởng: Duyệt qua từng dấu ngoặc trong dãy ngoặc; Sử dụng một stack để push các dấu ngoặc mở vào stack, mỗi khi gặp dấu ngoặc đóng, thực hiện pop một phần tử khỏi stack. Dãy ngoặc sẽ không hợp lệ khi bạn không thể pop hoặc khi kết thúc duyệt mà stack vẫn chưa rỗng.
39 cout << "Top of stack is " << TOS -> data << endl;
40
41 if(TOS -> next != NULL)
42 {
43 cout << "Other Elements are : ";
44 Stack *current = TOS -> next;
45
46 while(current)
47 {
48 cout << current -> data << " ";
49 current = current -> next;
50 }
51
52 cout << endl;
53 }
54 }
55}
56
57int main()
58{
59 for(int i = 0; i < 5; i++)
60 Push(i);
61
62 Print_Stack();
63
64 for(int i = 0; i < 6; i++)
65 Pop();
66
67 Print_Stack();
68
69 return 0;
70}
71
72
73/* Output
74Top of stack is 4
75Other Elements are : 3 2 1 0
76Stack is empty
77Stack is empty
78*/
4.4. Sử dụng stack trong thư viện STL
cpp
1#include <iostream>
2#include <stack>
3
4int main () {
5 std::stack<int> mystack;
6
7 for (int i=0; i<5; ++i) mystack.push(i);
8
9 std::cout << "Popping out elements...";
10 while (!mystack.empty()) {
11 std::cout << ' ' << mystack.top();
12 mystack.pop();
13 }
14 std::cout << '\n';
15
16 return 0;
17}
5. Bài tập thực hành
Cho một biểu thức hậu tố với số hạng là các số nguyên dương và ba toán tử +, -, *. Hãy tính giá trị của biểu thức hậu tố.
Ví dụ: biểu thức hậu tố: 2 3 4 + * 5 – 2 2 * + có giá trị là 13.
Dữ liệu nhập:
– Gồm một dòng thể hiện biểu thức hậu tố, mỗi số hạng là một số nguyên dương trong phạm vi từ 1 đến 100. Giữa hai số hạng, hoặc giữa hai toán tử, hoặc giữa số hạng và toán tử, cách nhau một khoảng trắng. Chiều dài biểu thức không quá 100 ký tự. Dữ liệu đề bài cho đảm bảo biểu thức hậu tố là hợp lệ. Trong quá trình tính toán đảm bảo trị tuyệt đối các giá trị trung gian không vượt quá 109.
Dữ liệu xuất:
– Là giá trị của biểu thức hậu tố.
Lưu ý: dùng hàm gets() hay getline() để đọc chuỗi.
Ví dụ
#input:
234+*5-22*+
#output:
13
Lưu tiến độ học tập
Đăng nhập và ghi danh để lưu tiến độ, bình luận và nhận chứng chỉ. Mở trang khóa học