Welcome to Day 8 of my 100 Days of DSA challenge! Today’s focus is on stacks, a fundamental data structure that operates on the Last-In-First-Out (LIFO) principle. Stacks are incredibly versatile and form the backbone of solutions for many algorithmic problems.
I spent the day solving five problems that deepened my understanding of stack operations and their practical applications. From managing elements to efficiently handling constraints, today’s challenges showcased the power of stacks in problem-solving.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s keep learning and building! 🚀
1. Implement a Stack Using Arrays
The program implements a stack using arrays in C++ and provides an interactive menu for performing basic stack operations. The stack is managed with a fixed size (MAX), and operations like push, pop, and peek (view the top element) are handled through member functions.
The
pushmethod adds an element to the top of the stack, ensuring no overflow.The
popmethod removes the top element, checking for underflow.The
peekmethod retrieves the top element without removing it.The
isEmptymethod checks if the stack is empty.
Code:
#include <iostream>
using namespace std;
#define MAX 1000
class Stack {
int top;
int a[MAX]; // Array to store stack elements
public:
Stack() { top = -1; }
// Function to push an element onto the stack
bool push(int x) {
if (top >= (MAX - 1)) {
cout << "Stack Overflow" << endl;
return false;
}
else {
a[++top] = x;
cout << x << " pushed into stack" << endl;
return true;
}
}
// Function to pop an element from the stack
int pop() {
if (top < 0) {
cout << "Stack Underflow" << endl;
return 0;
}
else {
int x = a[top--];
return x;
}
}
// Function to get the top element of the stack
int peek() {
if (top < 0) {
cout << "Stack is Empty" << endl;
return 0;
}
else {
return a[top];
}
}
// Function to check if the stack is empty
bool isEmpty() {
return (top < 0);
}
};
int main() {
Stack s;
int choice, num;
while (true) {
cout << "Select an operation to perform:\n";
cout << "1. Push\n";
cout << "2. Pop\n";
cout << "3. Top (Peek)\n";
cout << "4. Check if Stack is Empty\n";
cout << "5. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter the number you want to push: ";
cin >> num;
s.push(num);
break;
case 2:
if (s.isEmpty())
cout << "Stack is already empty!" << endl;
else
cout << s.pop() << " popped from stack" << endl;
break;
case 3:
if (s.isEmpty())
cout << "Stack is empty!" << endl;
else
cout << "Element at the top is: " << s.peek() << endl;
break;
case 4:
if (s.isEmpty())
cout << "Stack is empty!" << endl;
else
cout << "Stack is not empty." << endl;
break;
case 5:
cout << "Exiting the program. Goodbye!" << endl;
return 0;
default:
cout << "Invalid input! Please try again." << endl;
}
}
}
Output:
2. Check for Balanced Parentheses Using a Stack
The program checks if an input string contains balanced parentheses using a stack. It pushes opening brackets ((, {, [) onto the stack and, for closing brackets (), }, ]), verifies if the top of the stack contains the matching opening bracket. If there is a mismatch or an unmatched closing bracket, it determines the string is not balanced. At the end, the stack is checked to ensure it's empty, confirming all brackets were matched.
Code:
#include <iostream>
#include <stack>
using namespace std;
// Function to check if the given parentheses are balanced
bool is_balanced(string expr) {
stack<char> st;
// Traverse the given expression
for (char ch : expr) {
if (ch == '(' || ch == '{' || ch == '[') {
// Push opening brackets onto the stack
st.push(ch);
}
else if (ch == ')' || ch == '}' || ch == ']') {
// Check for matching closing brackets
if (st.empty()) {
return false; // Unmatched closing bracket
}
char top = st.top();
st.pop();
if ((ch == ')' && top != '(') ||
(ch == '}' && top != '{') ||
(ch == ']' && top != '[')) {
return false; // Mismatched brackets
}
}
}
// If the stack is empty, all brackets are balanced
return st.empty();
}
int main() {
string expr;
cout << "Enter an expression to check for balanced parentheses: ";
cin >> expr;
if (is_balanced(expr))
cout << "The parentheses are balanced." << endl;
else
cout << "The parentheses are not balanced." << endl;
return 0;
}
Output:
3. Next Greater Element Using a Stack
The code uses a stack to solve the "next greater element" problem in an efficient manner. It traverses the array from right to left, maintaining a stack of elements that are potential candidates for the "next greater" value. For each element, it removes smaller elements from the stack until it finds a larger one or the stack becomes empty. The next greater element is either the stack's top or none if the stack is empty.
Code:
#include <iostream>
#include <stack>
using namespace std;
// Function to find the next greater element for each element in the array
void next_greater_element(int arr[], int n) {
stack<int> s; // Stack to keep track of elements
// Array to store the results
int *result = new int[n];
for (int i = n - 1; i >= 0; i--) {
// Remove elements from the stack that are smaller than or equal to arr[i]
while (!s.empty() && s.top() <= arr[i]) {
s.pop();
}
// If stack is not empty, the top element is the next greater element
if (!s.empty())
result[i] = s.top();
else
// If the stack is empty, there is no greater element
result[i] = -1;
// Push the current element onto the stack
s.push(arr[i]);
}
// Print the results in the specified format
for (int i = 0; i < n; i++) {
cout << "Next greater element of " << arr[i] << " is " << (result[i] == -1 ? "none" : to_string(result[i])) << endl;
}
delete[] result;
}
int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
int *arr = new int[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++)
cin >> arr[i];
next_greater_element(arr, n);
delete[] arr;
return 0;
}
Output:
4. Reverse a String Using a Stack
The program reverses a string using a stack by first pushing all characters of the string onto the stack. Then, it pops the characters from the stack, which reverses their order due to the Last-In-First-Out (LIFO) nature of the stack. The reversed characters are concatenated to form the final reversed string, which is then displayed as the output.
Code:
#include <iostream>
#include <stack>
#include <string>
using namespace std;
// Function to reverse a string using a stack
string reverse_string(string str) {
stack<char> s;
// Push all characters of the string onto the stack
for (char ch : str)
s.push(ch);
// Pop characters from the stack to form the reversed string
string reversed = "";
while (!s.empty()) {
reversed += s.top();
s.pop();
}
return reversed;
}
int main() {
string input;
cout << "Enter a string to reverse: ";
getline(cin, input);
string reversed = reverse_string(input);
cout << "Reversed string is: " << reversed << endl;
return 0;
}
Output:
5. Implement a Stack that Supports Push, Pop, and Finding the Minimum Element in O(1) Time
In the above code, a stack is implemented with an additional auxiliary stack to keep track of the minimum element. The user is prompted to choose between different operations: pushing an element, popping an element, and retrieving the current minimum element. The stack operations are performed in constant time (O(1)) to ensure efficiency. The minimum element is tracked separately in a secondary stack to allow constant time retrieval of the minimum value. The program runs in a loop until the user opts to exit.
Code:
#include <iostream>
#include <stack>
using namespace std;
class MinStack {
private:
stack<int> s; // Main stack to store elements
stack<int> minStack; // Auxiliary stack to store minimum elements
public:
// Push an element onto the stack
void push(int x) {
s.push(x);
// If the minStack is empty or the current element is smaller than the current minimum, push it onto the minStack
if (minStack.empty() || x <= minStack.top())
minStack.push(x);
}
// Pop the top element from the stack
void pop() {
if (!s.empty()) {
// If the element to be popped is the same as the current minimum, pop from the minStack as well
if (s.top() == minStack.top())
minStack.pop();
s.pop();
}
else
cout << "Stack is empty!" << endl;
}
// Get the minimum element in the stack
int getMin() {
if (!minStack.empty())
return minStack.top();
return -1; // Return -1 if the stack is empty
}
};
int main() {
MinStack stack;
int choice, num;
while (true) {
cout << "\nChoose an operation:\n";
cout << "1. Push an element\n";
cout << "2. Pop an element\n";
cout << "3. Get the minimum element\n";
cout << "4. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter the element to push: ";
cin >> num;
stack.push(num);
cout << num << " pushed onto stack." << endl;
break;
case 2:
stack.pop();
break;
case 3:
num = stack.getMin();
if (num == -1)
cout << "Stack is empty!" << endl;
else
cout << "Minimum element is: " << num << endl;
break;
case 4:
cout << "Exiting program." << endl;
return 0;
default:
cout << "Invalid choice, please try again." << endl;
}
}
return 0;
}
Output:
Day 8 was a deep dive into the powerful world of stacks, where I tackled various problems that showcased their efficiency in solving complex tasks. From finding the next greater element to implementing a stack with constant-time minimum retrieval, each problem reinforced the importance of stacks in optimizing algorithms.
Looking forward to continuing the journey and solving even more challenging problems on Day 9! 🚀