C++ - Stacks Part 5: Advanced Techniques and Best Practices
Advanced uses of stacks involve combining them with other STL algorithms or containers to solve complex problems.
Examples and Explanation
Sorting Using Stacks
std::stack<int> stack;
std::stack<int> tempStack;
stack.push(3);
stack.push(1);
stack.push(2);
while (!stack.empty()) {
int temp = stack.top();
stack.pop();
while (!tempStack.empty() && tempStack.top() > temp) {
stack.push(tempStack.top());
tempStack.pop();
}
tempStack.push(temp);
}
while (!tempStack.empty()) {
std::cout << tempStack.top() << " ";
tempStack.pop();
}
// Output: 1 2 3
Explanation: Two stacks are used to sort elements in ascending order.
Simulating Recursion
void iterativeFactorial(int n) {
std::stack<int> stack;
int result = 1;
for (int i = n; i > 1; --i) {
stack.push(i);
}
while (!stack.empty()) {
result *= stack.top();
stack.pop();
}
std::cout << "Factorial: " << result << "\n";
}
Explanation: A stack simulates recursion by manually managing the call stack.
Parsing Mathematical Expressions
int evaluateExpression(const std::string &expression) {
std::stack<int> stack;
for (char c : expression) {
if (isdigit(c)) {
stack.push(c - '0');
} else {
int b = stack.top(); stack.pop();
int a = stack.top(); stack.pop();
switch (c) {
case '+': stack.push(a + b); break;
case '-': stack.push(a - b); break;
case '*': stack.push(a * b); break;
case '/': stack.push(a / b); break;
}
}
}
return stack.top();
}
Explanation: Stacks are instrumental in evaluating postfix expressions.
