61
The stack in the C++ Standard Template Library (STL) is a container adapter that implements a Last-In-First-Out (LIFO) structure.
Elements are added and removed from the same end of the stack (the “top”), making it ideal for tasks where the last added element needs to be processed first.
Key Features of stack
- LIFO Structure: Elements are added and removed from the top.
- Efficient Operations: push, pop, and top operations are constant time.
- Restricted Access: Only the top element can be accessed directly; no random access.
Basic Syntax
#include <stack> using namespace std; stack<Type> s;
Let’s explore the stack with examples demonstrating common operations.
1. Basic Operations: push, pop, and top
The push function adds an element to the top of the stack, pop removes the top element, and top retrieves the top element.
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
// Adding elements
s.push(10);
s.push(20);
s.push(30);
// Access top element
cout << "Top element: " << s.top() << endl;
// Remove elements and display them
cout << "Elements in the stack: ";
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << endl;
return 0;
}
Output:
Top element: 30 Elements in the stack: 30 20 10
2. Checking if the Stack is Empty
The empty function checks if the stack is empty, returning true if it is and false otherwise.
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
// Check if the stack is empty
if (s.empty()) {
cout << "The stack is empty." << endl;
}
// Add an element and check again
s.push(5);
if (!s.empty()) {
cout << "The stack is not empty." << endl;
}
return 0;
}
Output:
The stack is empty. The stack is not empty.
3. Getting the Size of the Stack
Use the size function to retrieve the number of elements in the stack.
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
// Insert elements
s.push(10);
s.push(20);
s.push(30);
// Display the size of the stack
cout << "Size of the stack: " << s.size() << endl;
return 0;
}
Output:
Size of the stack: 3
4. Using stack with Custom Data Types
You can store custom objects in a stack as long as they have a valid copy constructor and assignment operator.
#include <iostream>
#include <stack>
#include <string>
using namespace std;
// Custom structure for storing person information
struct Person {
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
};
int main() {
stack<Person> s;
// Insert custom objects
s.push(Person("Alice", 25));
s.push(Person("Bob", 30));
s.push(Person("Charlie", 35));
// Access and display elements
cout << "People in the stack:" << endl;
while (!s.empty()) {
Person p = s.top();
cout << "Name: " << p.name << ", Age: " << p.age << endl;
s.pop();
}
return 0;
}
Output:
People in the stack: Name: Charlie, Age: 35 Name: Bob, Age: 30 Name: Alice, Age: 25
5. Reversing a Sequence Using a Stack
You can use a stack to reverse a sequence of elements, as elements are retrieved in reverse order.
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
vector<int> numbers = {1, 2, 3, 4, 5};
stack<int> s;
// Push elements to the stack
for (int num : numbers) {
s.push(num);
}
// Pop elements to display them in reverse order
cout << "Reversed sequence: ";
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << endl;
return 0;
}
Output:
Reversed sequence: 5 4 3 2 1
6. Using stack with Strings
You can use stack to manage strings, which is useful for applications like reversing words or checking balanced parentheses.
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
stack<string> s;
// Insert strings
s.push("apple");
s.push("banana");
s.push("cherry");
// Display and remove strings in LIFO order
cout << "Strings in the stack: ";
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << endl;
return 0;
}
Output:
Strings in the stack: cherry banana apple
7. Using stack to Check for Balanced Parentheses
A stack is useful for checking if parentheses in an expression are balanced.
#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool isBalanced(const string &str) {
stack<char> s;
for (char ch : str) {
if (ch == '(') {
s.push(ch);
} else if (ch == ')') {
if (s.empty()) return false;
s.pop();
}
}
return s.empty();
}
int main() {
string expr = "(1 + (2 * (3 + 4)))";
if (isBalanced(expr)) {
cout << "The expression has balanced parentheses." << endl;
} else {
cout << "The expression does not have balanced parentheses." << endl;
}
return 0;
}
Output:
The expression has balanced parentheses.
8. Clearing All Elements from a Stack
To clear all elements in a stack, use a loop to remove each element with pop.
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
// Insert elements
s.push(10);
s.push(20);
s.push(30);
// Clear the stack
while (!s.empty()) {
s.pop();
}
// Verify that the stack is empty
cout << "Is the stack empty? " << (s.empty() ? "Yes" : "No") << endl;
return 0;
}
Output:
Is the stack empty? Yes
9. Using stack to Evaluate a Postfix Expression
stack is commonly used to evaluate postfix (Reverse Polish Notation) expressions.
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int evaluatePostfix(const string &expr) {
stack<int> s;
for (char ch : expr) {
if (isdigit(ch)) {
s.push(ch - '0'); // Convert char to int
} else {
int b = s.top(); s.pop();
int a = s.top(); s.pop();
switch (ch) {
case '+': s.push(a + b); break;
case '-': s.push(a - b); break;
case '*': s.push(a * b); break;
case '/': s.push(a / b); break;
}
}
}
return s.top();
}
int main() {
string postfixExpr = "53+82-*";
cout << "Result of postfix expression evaluation: " << evaluatePostfix(postfixExpr) << endl;
return 0;
}
Output:
Result of postfix expression evaluation: 16
Summary Table of stack Operations
| Operation | Code Example | Description |
|---|---|---|
| Initialize | stack<int> s; | Initializes an empty stack |
| Add Element | s.push(10); | Adds an element to the top of the stack |
| Remove Element | s.pop(); | Removes the top element |
| Access Top | s.top(); | Accesses the top element |
| Check if Empty | s.empty(); | Returns true if the stack is empty |
| Get Size | s.size(); | Returns the number of elements in the stack |
| Custom Data Types | stack<CustomType> s; | Stores custom objects |
| Clear All Elements | Use while (!s.empty()) { s.pop(); } | Clears all elements manually |
| Check Balanced Parentheses | isBalanced(expression); | Uses stack to check if parentheses are balanced |
| Evaluate Postfix Expression | evaluatePostfix(expr); | Uses stack to evaluate a postfix expression |
Complete Example
This example demonstrates initializing a stack, adding and removing elements, checking if elements exist, and clearing the stack.
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
// Adding elements
s.push(5);
s.push(10);
s.push(15);
// Display the top element
cout << "Top element: " << s.top() << endl;
// Display all elements in the stack
cout << "Elements in the stack: ";
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << endl;
// Check if stack is empty after clearing
cout << "Is the stack empty? " << (s.empty() ? "Yes" : "No") << endl;
return 0;
}
Sample Output:
Top element: 15 Elements in the stack: 15 10 5 Is the stack empty? Yes
Key Takeaways
- stack in C++ provides a LIFO structure, useful for scenarios where the most recent element needs to be processed first.
- Key operations include push, pop, top, empty, and size.
- It is commonly used for applications like expression evaluation, parentheses matching, and reversing sequences where a LIFO structure is ideal.