Table of contents
- Q1. Implement a stack using arrays.
- Q2. Write a program to check for balanced parentheses using a stack.
- Q3. Solve the "next greater element" problem using a stack.
- Q4. Write a program to reverse a string using a stack.
- Q5. Implement a stack that supports push, pop, and finding the minimum element in O(1) time.
Today’s practice focused on mastering stacks. I worked on implementing a stack using arrays, checking for balanced parentheses, and solving the "next greater element" problem using a stack. Additionally, I tackled reversing a string with a stack and building a stack that supports push, pop, and finding the minimum element in constant time. These exercises gave me a deeper understanding of stack operations and their practical applications.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Implement a stack using arrays.
#include <iostream>
using namespace std;
int push(int stack[],int &top,int e,int n){
if(top==n){
cout<<"Stack Overflow has occured, no more elements can be added"<<endl;
}
else{
stack[top]=e;
top++;
}
return top;
}
int pop(int stack[],int &top,int n){
if(top==-1){
cout<<"Stack Underflow has occured, no more elements left to remove"<<endl;
}
else{
cout<<stack[top-1]<<endl;
top--;
}
return top;
}
void display_stack(int stack[],int top){
cout<<"The structure of the stack is: ";
for(int i=0;i<top;i++){
cout<<stack[i]<<" ";
}
cout<<endl;
}
int main()
{
int n,k;
int top=0;
cout<<"Limit the amount of elements(enter max no. of elements): ";
cin>>n;
int stack[n];
push(stack,top,5,n);
push(stack,top,4,n);
push(stack,top,6,n);
display_stack(stack,top);
push(stack,top,7,n);
push(stack,top,8,n);
display_stack(stack,top);
pop(stack,top,n);
display_stack(stack,top);
return 0;
}
This code implements a stack data structure using arrays. The push function adds elements to the stack if there is space available; if the stack is full (i.e., top == n), it prints a stack overflow message. The pop function removes and prints the top element of the stack, or prints a stack underflow message if the stack is empty. The display_stack function prints all the elements currently in the stack. In the main function, a stack of user-defined size n is created, and a series of push and pop operations are performed to demonstrate the functionality. The program handles stack overflow and underflow conditions.
Q2. Write a program to check for balanced parentheses using a stack.
#include <iostream>
#include <vector>
using namespace std;
void push(vector<char> &stack, char e) {
stack.push_back(e);
}
void pop(vector<char> &stack) {
stack.pop_back();
}
int main() {
vector<char> stack;
string str;
cout << "Enter the parenthesis expression: ";
cin >> str;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(' || str[i] == '{' || str[i] == '[') {
push(stack, str[i]);
} else if (str[i] == ')' || str[i] == '}' || str[i] == ']') {
// Check if stack is empty or top does not match
if (stack.empty() ||
(str[i] == ')' && stack.back() != '(') ||
(str[i] == '}' && stack.back() != '{') ||
(str[i] == ']' && stack.back() != '[')) {
cout << "Expression isn't balanced";
return 0; // Exit immediately
}
pop(stack);
} else {
cout << "Invalid expression";
return 0; // Exit immediately
}
}
// If the stack is empty after processing, it's balanced
if (stack.empty()) {
cout << "Expression is balanced";
} else {
cout << "Expression isn't balanced";
}
return 0;
}
This code checks whether a given string containing parentheses, braces, and brackets is balanced. It uses a stack (implemented with a vector<char>) to track opening brackets. As it iterates through the string, it pushes opening brackets onto the stack and pops them when a corresponding closing bracket is encountered. If an unmatched closing bracket or an invalid character is found, the program immediately prints that the expression isn't balanced. At the end, if the stack is empty, it indicates the expression is balanced; otherwise, it’s unbalanced. The program handles all types of brackets and ensures they are properly nested.
Q3. Solve the "next greater element" problem using a stack.
#include <iostream>
using namespace std;
#include <vector>
void push(vector<int> &stack, int e) {
stack.push_back(e);
}
void pop(vector<int> &stack) {
stack.pop_back();
}
void display_result(vector<int> &result) {
cout << "NGE of array is: ";
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
cout << endl;
}
int main() {
int n;
vector<int> stack;
cout << "Enter length of array: ";
cin >> n;
int arr[n];
cout << "Enter elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
vector<int> result(n, -1);
for (int i = n - 1; i >= 0; i--) {
while (!stack.empty() && stack.back() <= arr[i]) {
pop(stack); // Remove elements from the stack that are not the next greater element
}
if (!stack.empty()) { // If the stack is not empty, the top element is the next greater element
result[i] = stack.back(); // Assign the next greater element
}
push(stack, arr[i]);
}
display_result(result);
return 0;
}
This code finds the Next Greater Element (NGE) for each element in an array using a stack. It processes the array from right to left, maintaining a stack of elements that could be potential NGEs. For each element, smaller or equal elements on the stack are removed, leaving the next greater element (if any) at the top of the stack. The NGE is stored in the result array, and if no greater element exists, -1 is retained. After processing, the result is displayed, showing the NGE for each element in order. This approach efficiently computes the NGE in O(n) time.
Q4. Write a program to reverse a string using a stack.
#include <iostream>
using namespace std;
#include <vector>
void push(vector <char> &stack,char e){
stack.push_back(e);
}
void pop(vector <char> &stack){
if (stack.empty()) {
cout << "Stack is empty. Cannot pop." << endl;
return;
}
cout<<stack.back();
stack.pop_back();
}
int main()
{
vector <char>stack;
string str;
cout<<"Enter the string: ";
cin>>str;
for(int i=0;i<str.size();i++){
push(stack,str[i]);
}
cout<<"The reversed string is: ";
while (!stack.empty()) {
pop(stack);
}
return 0;
}
This program reverses a string using a stack implemented with a vector. It first pushes each character of the input string onto the stack. Once all characters are pushed, the program pops characters off the stack one by one, printing them in reverse order of insertion. The use of a stack ensures that the string is reversed efficiently in O(n) time. The program also handles cases where the stack is empty before popping, providing a safety check.
Q5. Implement a stack that supports push, pop, and finding the minimum element in O(1) time.
#include <iostream>
using namespace std;
#include <vector>
void push(vector <int> &stack,int e,vector<int> &aux){
if( aux.empty() || e<=aux.back()){
aux.push_back(e);
}
stack.push_back(e);
}
void pop(vector <int> &stack, vector<int> &aux){
if (stack.empty()) {
cout << "Stack is empty. Cannot pop." << endl;
return;
}
int end1=stack.size()-1;
int end2=aux.size()-1;
cout<<stack[end1];
if(stack[end1]==aux[end2]){
aux.pop_back();
}
stack.pop_back();
}
void find_min_element(vector <int> &aux){
int end=aux.size()-1;
cout<<"Minimum element is: "<<aux[end];
}
void display_stack(vector <int> &stack){
cout<<"Structure of stack is: ";
for(int i=0;i<stack.size();i++){
cout<<stack[i]<<" ";
}
}
int main()
{
vector <int>stack;
vector <int>aux;
push(stack,2,aux);
push(stack,10,aux);
push(stack,9,aux);
push(stack,1,aux);
push(stack,3,aux);
display_stack(stack);
cout<<endl;
pop(stack,aux);
cout<<endl;
display_stack(stack);
cout<<endl;
find_min_element(aux);
return 0;
}
This program implements a stack that supports push, pop, and finding the minimum element in O(1) time using two vectors: stack (for storing elements) and aux (for tracking minimum elements). When an element is pushed, it is added to both stack and aux if it is less than or equal to the current minimum. During a pop operation, if the popped element matches the top of aux, it is also removed from aux. The find_min_element function retrieves the last element in aux, which always contains the minimum value of the stack.
Today’s practice was a great way to strengthen my understanding of stacks. Whether it was implementing stacks, solving the next greater element problem, or reversing strings, each problem added valuable insight into stack operations. I’m eager to explore even more stack-related challenges as I continue to build my skills.