Scribd
Upload
7 views4 pages

C++ Stack Problems and Solutions

The document outlines 10 important stack-related problems in C++, including solutions for validating parentheses, converting infix to postfix expressions, evaluating postfix expressions, and implementing stacks and queues using other data structures. Each problem includes a brief description, the time complexity, and the corresponding code implementation. Additional problems covered include finding the next greater element, calculating the largest rectangle in a histogram, designing a min stack, solving the stock span problem, and identifying a celebrity in a party.

Uploaded by

Sudipta Sahu
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views4 pages

C++ Stack Problems and Solutions

The document outlines 10 important stack-related problems in C++, including solutions for validating parentheses, converting infix to postfix expressions, evaluating postfix expressions, and implementing stacks and queues using other data structures. Each problem includes a brief description, the time complexity, and the corresponding code implementation. Additional problems covered include finding the next greater element, calculating the largest rectangle in a histogram, designing a min stack, solving the stock span problem, and identifying a celebrity in a party.

Uploaded by

Sudipta Sahu
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

10 Important Stack Questions in C++

1. Valid Parentheses Checker


Check if the input string has valid opening and closing brackets.
Time Complexity: O(n)
bool isValid(string s) {
stack<char> stk;
for (char c : s) {
if (c == '(' || c == '{' || c == '[')
[Link](c);
else {
if ([Link]()) return false;
char top = [Link]();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) return false;
[Link]();
}
}
return [Link]();
}

2. Infix to Postfix Conversion


Convert an infix expression (e.g., A+B) to postfix (e.g., AB+).
Time Complexity: O(n)
int precedence(char op) {
if(op == '+'||op == '-') return 1;
if(op == '*'||op == '/') return 2;
return 0;
}

3. Evaluate Postfix Expression


Evaluate a postfix expression using a stack.
Time Complexity: O(n)
int evalPostfix(string exp) {
stack<int> st;
for(char c : exp) {
if(isdigit(c)) [Link](c - '0');
else {
int val2 = [Link](); [Link]();
int val1 = [Link](); [Link]();
switch(c) {
case '+': [Link](val1 + val2); break;
case '-': [Link](val1 - val2); break;
case '*': [Link](val1 * val2); break;
case '/': [Link](val1 / val2); break;
}
}
}
return [Link]();
}

4. Implement Stack Using Queues


Simulate stack operations using two queues.
Push: O(1), Pop: O(n)
void push(int x) { [Link](x); }
int pop() {
while([Link]() > 1) {
[Link]([Link]()); [Link]();
}
int top = [Link](); [Link]();
swap(q1, q2);
return top;
}

5. Implement Queue Using Stacks


Simulate queue using two stacks.
Enqueue: O(1), Dequeue: O(n)
void enqueue(int x) { [Link](x); }
int dequeue() {
if ([Link]()) {
while (![Link]()) {
[Link]([Link]()); [Link]();
}
}
int top = [Link](); [Link]();
return top;
}

6. Next Greater Element


Find next greater element for each element in array.
Time Complexity: O(n)
vector<int> nextGreater(vector<int>& nums) {
stack<int> st; vector<int> res([Link](), -1);
for (int i = 0; i < [Link](); ++i) {
while (![Link]() && nums[i] > nums[[Link]()]) {
res[[Link]()] = nums[i]; [Link]();
}
[Link](i);
}
return res;
}

7. Largest Rectangle in Histogram


Find area of largest rectangle that fits in a histogram.
Time Complexity: O(n)
int largestRectangle(vector<int>& heights) {
stack<int> st; heights.push_back(0);
int maxArea = 0;
for (int i = 0; i < [Link](); ++i) {
while (![Link]() && heights[i] < heights[[Link]()]) {
int h = heights[[Link]()]; [Link]();
int w = [Link]() ? i : i - [Link]() - 1;
maxArea = max(maxArea, h * w);
}
[Link](i);
}
return maxArea;
}

8. Min Stack
Design a stack that supports push, pop, and retrieving the minimum in constant time.
Time Complexity: O(1)
stack<int> s, minSt;
void push(int x) {
[Link](x);
if([Link]() || x <= [Link]()) [Link](x);
}
void pop() {
if([Link]() == [Link]()) [Link]();
[Link]();
}
int getMin() { return [Link](); }

9. Stock Span Problem


Calculate the stock span for each day.
Time Complexity: O(n)
vector<int> stockSpan(vector<int>& prices) {
stack<int> st; vector<int> span([Link]());
for (int i = 0; i < [Link](); ++i) {
while (![Link]() && prices[i] >= prices[[Link]()]) [Link]();
span[i] = ([Link]()) ? (i + 1) : (i - [Link]());
[Link](i);
}
return span;
}

10. Celebrity Problem


Find celebrity in a party of N people using stack.
Time Complexity: O(n)
int findCelebrity(int n, vector<vector<int>>& M) {
stack<int> s;
for (int i = 0; i < n; i++) [Link](i);
while ([Link]() > 1) {
int a = [Link](); [Link]();
int b = [Link](); [Link]();
if (M[a][b]) [Link](b);
else [Link](a);
}
int c = [Link]();
for (int i = 0; i < n; i++) {
if (i != c && (M[c][i] || !M[i][c])) return -1;
}
return c;
}

You might also like