Stack trong C++ là một kiểu dữ liệu cấu trúc dữ liệu được sử dụng để lưu trữ một tập hợp các phần tử và cung cấp hai thao tác chính: push và pop.
- Push: Thêm một phần tử vào đầu của stack.
- Pop: Loại bỏ phần tử đầu tiên trong stack.
Stack là một kiểu dữ liệu Last-In-First-Out (LIFO), nghĩa là phần tử cuối cùng được thêm vào sẽ được trả về đầu tiên.
Các bài viết liên quan:
STL cung cấp cho ta class stack cho phép sử dụng stack dễ dàng, ví dụ:
stack<int> myStack; myStack.push(5); myStack.push(3); myStack.push(7); cout << myStack.top() << endl; // 7 myStack.pop(); cout << myStack.top() << endl; // 3
Stack có nhiều ứng dụng trong lập trình, ví dụ như:
- Quản lý không gian đệm trong quá trình thực thi hàm.
- Duyệt các phần tử trong dạng ngược lại.
- Chuyển đổi từ hậu tố sang trung tố, và ngược lại.
- Xử lý các thuật toán như duyệt
- Duyệt các phần tử trong dạng ngược lại: Stack có thể sử dụng để duyệt một dãy dữ liệu theo thứ tự ngược lại, bằng cách thêm các phần tử vào stack và sau đó duyệt qua các phần tử trong stack bằng cách sử dụng hàm pop.
- Chuyển đổi từ hậu tố sang trung tố, và ngược lại: Stack có thể sử dụng để chuyển đổi các biểu thức từ hậu tố sang trung tố hoặc ngược lại bằng cách sử dụng các thuật toán liên quan đến stack.
- Xử lý các thuật toán như duyệt: Stack có thể sử dụng để xử lý các thuật toán duyệt như DFS (depth-first search) hoặc quản lý các phần tử đang xét trong quá trình duyệt.
Tất cả các ví dụ trên chỉ là một số trong rất nhiều ứng dụng của stack, nó còn có nhiều ứng dụng khác nữa và rất cần thiết trong lập trình.
Một vài ví dụ stack trong c++
- Ví dụ về stack trong C++:
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> myStack;
myStack.push(5);
myStack.push(3);
myStack.push(7);
cout << "Top element: " << myStack.top() << endl; // 7
myStack.pop();
cout << "Top element after pop: " << myStack.top() << endl; // 3
cout << "Stack size: " << myStack.size() << endl; // 2
if(myStack.empty())
cout << "Stack is empty" << endl;
else
cout << "Stack is not empty" << endl;
return 0;
}- Ví dụ về chuyển đổi biểu thức từ hậu tố sang trung tố:
#include <iostream>
#include <stack>
using namespace std;
string infixToPostfix(string infix) {
stack<char> operatorStack;
string postfix = "";
for(int i = 0; i < infix.length(); i++) {
if(infix[i] >= '0' && infix[i] <= '9')
postfix += infix[i];
else if(infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') {
while(!operatorStack.empty() && operatorStack.top() != '(' && (operatorStack.top() == '*' || operatorStack.top() == '/')) {
postfix += operatorStack.top();
operatorStack.pop();
}
operatorStack.push(infix[i]);
}
else if(infix[i] == '(') {
operatorStack.push(infix[i]);
}
else if(infix[i] == ')') {
while(operatorStack.top() != '(') {
postfix += operatorStack.top();
operatorStack.pop();
}
operatorStack.pop(); } }
while(!operatorStack.empty()) {
postfix += operatorStack.top();
operatorStack.pop();
}
return postfix;
}
int main() {
string infix = "(1+2)*3-4/(5+6)";
cout << "Infix: " << infix << endl;
cout << "Postfix: " << infixToPostfix(infix) << endl;
return 0;
}- Ví dụ về duyệt DFS
#include <iostream>
#include <stack>
using namespace std;
void DFS(int start, vector<int> adj[], bool visited[]) {
stack<int> st;
st.push(start);
visited[start] = true;
while(!st.empty()) {
int current = st.top();
st.pop();
cout << current << " ";
for(int i = 0; i < adj[current].size(); i++) {
if(!visited[adj[current][i]]) {
st.push(adj[current][i]);
visited[adj[current][i]] = true;
}
}
}
}
int main() {
int n = 5;
vector<int> adj[n];
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(2);
adj[2].push_back(0);
adj[2].push_back(3);
adj[3].push_back(3);
bool visited[n] = {false};
DFS(2, adj, visited);
return 0;
}
Trong các ví dụ trên, stack được sử dụng để lưu trữ các phần tử và thao tác trên nó. Các bạn có thể tham khảo và tùy chỉnh theo nhu cầu của mình.
