Series Cấu trúc dữ liệu | Stack - Ngăn Xếp

--- ---

Mục lục

---

• Giới thiệu
• Định nghĩa
• Code
• Ứng dụng
• Áp dụng

Giới thiệu

---

Tưởng tượng bạn có một giá sách thì khi cất sách thì cuốn đó được đặt lên trên cùng, và khi lấy ra thì phải lấy cuốn trên cùng, chứ không thể lấy ra hoặc cất lên từ vị trí khác. Đó chính là cách hoạt động của cấu trúc Stack (Ngăn xếp) theo kiểu LIFO(Last In First Out - Vào sau ra trước)

Định nghĩa

---

Một ngăn xếp là một cấu trúc dữ liệu dạng thùng chứa (container) của các phần tử (thường gọi là các nút (node)) và có hai phép toán cơ bản:

• push: Bổ sung một phần tử vào đỉnh (top) của ngăn xếp, nghĩa là sau các phần tử đã có trong ngăn xếp.
• pop: Giải phóng và trả về phần tử đang đứng ở đỉnh của ngăn xếp.

Trong stack, các đối tượng có thể được thêm vào stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi stack.

Code

---

Cấu trúc Stack được chứa trong thư viện stack vậy nên chúng ta cần include< stack >
Cách khai báo:

stack<int> nganXep1; // stack có các phần tử kiểu int
stack<char> nganXep2; // kiểu char
...

stack<int> s;

Với stack $s$, ta có các hàm:

• s.size(): Trả về số lượng các phần tử trong stack
• s.empty(): Trả về true nếu stack rỗng(size=0) ngược lại trả về false
• s.push(x): Đầy phần tử $x$ vào đỉnh stack
• s.pop(): Loại bỏ đỉnh của stack
• s.top(): Trả về phần tử đỉnh của stack

Ví dụ:

#include<iostream>
#include<stack>
using namespace std;

stack<int> s;

int main() {
 for (int i=0;i<5;i++) {
  s.push(i); // s = {1,2,3,4,5}
 }
 s.push(100); // s = {1,2,3,4,5,100}
 cout<<s.top()<<endl; // in ra 100
 s.pop(); // s = {1,2,3,4,5}
 for(int i=0;i<5;i++){
  cout<<s.top()<<' ';
  s.pop();
 }
 // in ra 5 4 3 2 1
}

Ứng dụng

---

• Đảo ngược xâu: nhập từng kí tự xâu cho vào stack, sau đó lấy từng kí tự ra ta sẽ được 1 xâu đảo ngược.
• Chuyển hệ cơ số 10 sang cơ số 2(cơ số bất kì): thực hiện liên tiếp phép chia dư n cho 2 rồi , n=n/2 và push kq phép chia dư vào stack, sau khi chia xong ta lấy các phần tử trong stack ra.
• Tính biểu thức đại số, chuyển biểu thức đại số dạng trung sang hậu tố.
• Khử đệ quy (trong duyệt đồ thị DFS)

Áp dụng

---

PTIT123J - Dấu ngoặc đúng
https://www.spoj.com/PTIT/problems/PTIT123J/

Ý tưởng:
Có một stack lưu các kí tự “(” hoặc “[”, xét từ đầu xâu tới cuối:

• Nếu gặp dấu “(” hoặc “[” thì push vào stack
• Nếu gặp dấu “)” mà đỉnh stack là dấu “(” thì pop ra ngược lại in ra $NO$ vì đỉnh là “[” (không thể có loại “(…]”
• Nếu gặp dấu “]” mà đỉnh stack là dấu “[” thì pop ra ngược lại in ra $NO$ vì đỉnh là “(” (không thể có loại “[…)”
• Sau khi xét đến cuối xâu kiếm tra nếu trong stack còn phần tử thì in ra $NO$ ngược lại in ra $YES$.

#include<iostream>
#include<string>
using namespace std;
#include<stack>
int main()
{
 while(1)
 {
  string s;
  getline(cin, s);
  if (s[s.length() - 1] == '.' && s.length() == 1) break;;
  stack<char> stark;
  bool flag = true;
  //while(stark.size()) stark.pop();
  for (int i = 0; s[i] != '.'; i++) 
  {
   if (s[i] == '(') stark.push(s[i]);
   else if (s[i] == '[') stark.push(s[i]);
   else 
   {
    if (s[i] == ')') 
    {
     if (stark.size() == 0 || stark.top() != '(')
     {
      flag = false;
      break;
     }
     else stark.pop();
    }
    else if (s[i] == ']')
    {
     if (stark.size() == 0 || stark.top() != '[')
     {
      flag = false;
      break;
     }
     else stark.pop();
    }   
   }
  }
  if (flag && stark.size() == 0) cout << "yes" << endl;
  else cout << "no" << endl;
 }
 
 return 0;
}

Bài tập áp dụng:
PTIT121E - Nguyên tố hóa học
https://www.spoj.com/PTIT/problems/PTIT121E/

BCSTACK - Cấu trúc dữ liệu ngăn xếp (stack) (Cơ bản)
https://www.spoj.com/PTIT/problems/BCSTACK/