isalfa(x) to check whether character x is an alphabet or not
isdigit(x) to check whether character x is a digit or not
https://www.geeksforgeeks.org/reversing-a-queue-using-another-queue/?ref=rp
https://www.geeksforgeeks.org/reversing-first-k-elements-queue/?ref=rp
https://www.geeksforgeeks.org/stack-data-structure/
Q) Reverse a String in C++
Without Stack
Ex1) Reversing string str iteratively using 1 pointer
void reverse2(string& str)
{
int i;
int n = str.length();
for (i = 0; i < n / 2; i++)
{
swap(str[i], str[n - i - 1]);
}
}
1) Time complexity : O(n)
2) Auxiliary Space : O(1)
Ex2) Reverse string str iteratively using 2 pointer
void reverse3(string& str)
{
int i,j;
int n = str.length();
for (i = 0,j = n-1 ; i < j; i++,j--)
{
swap(str[i], str[j]);
}
}
1) Time complexity : O(n)
2) Auxiliary Space : O(1)
Ex3) Reverse string str recursively
void reverse4(string &str, int i = 0)
{
int n = str.length();
if (i == n / 2)
return;
swap(str[i], str[n - i - 1]);
reverse4(str, i + 1);
}
Time complexity : O(n)
Auxiliary Space : O(n)
https://www.geeksforgeeks.org/reverse-the-sentence-using-stack/
Q) Reverse a String in C++ (By Changing the order of words).
Without using the Stack Data Structure.
Using the strtok() function of C.
https://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression/
Q) Check for well formedness using a stack
Check for balanced brackets in a expression
1) exp = “[()]{}{[()()]()}”
Balanced
2) exp = “[(])”
Not Balanced
Ex1) Algorithm
1) Declare a character stack stk.
2) Traverse the String exp 😊 😊
If the current character of exp is a starting bracket ( i.e (,{,[ ) Then push it into the
If the current character of exp is a closing bracket ( i.e ),},] ) Then pop x from the s
o Let x = popped character = Obviously a opening bracket character.
o If x matches with the corresponding current closing bracket character
o Then fine
o Otherwise we say the brackets are not balanced
3) Note :-
In the examples String exp is shown as a String of paranthesis
However actually the String exp is an algebraic expression consisting of paranthesis.
exp[i] = Current Character
Ex2) The Program
// function to check if brackets are balanced // If current
bool areBracketsBalanced(string expr)
{ // Pop one ch
int i;
stack<char> stk; // x = Essent
char x;
// If x match
// Traversing the Expression correspondin
for (i=0;i<expr.length();i++)
{ // Then Fine
// If the current character exp[i] is a opening bracket switch (expr[i]
// Push it into the stack {
if ( expr[i] == '(' || expr[i] == '[' || expr[i] == '{' ) case ')':
{ x = stk
x = expr[i]; stk.pop
// Push the element in the stack if (x =
stk.push(x); ret
continue; break;
}
case '}':
// IF current current character exp[i] is not opening brack x = stk
et, stk.pop
// Then it must be closing. if (x =
// So stack cant be empty at this point. ret
if (stk.empty()) break;
return false;
case ']':
// Driver code x = stk
int main() stk.pop
{ if (x =
string expr = "{()}[]"; ret
break;
// Function call }
if (areBracketsBalanced(expr)) }
cout << "Balanced";
else // Check Empty Sta
cout << "Not Balanced"; return (stk.empty()
return 0; }
}
Ex4) Time and Space Complexities
1) Time Complexity = O(n)
2) Auxillary Space = O(n)
For the Stack used.
https://www.techiedelight.com/find-elements-array-greater-than-elements-right/
Q2) Find all elements in an array….
That are greater than all elements present to their right
Input:- arr[] = {10,4,6,3,5}
Output:- Elements greater than all elements present to their right = 10,6,5
Ex1) Program 1
Using the Stack DS.
1) For each element x in the given array arr
We pop out all the elements of the stack which are <= x
Then we insert that element x in the stack
2) Basically after we have completed step 1….
We are left with a stack which contains those elements of the array
which are greater than all the elements present to their right
3) Trick :-
Going (left right) in an array Going (bottom top) in the Stack.
Hence elements right of x Elements above x in the Stack.
// Function to print all elements x of an arr[]
// s.t all elements present to the right of a is greater than x
void find1(int arr[], int n)
{
stack<int> stk;
cout<<"\nThe elements in an array which is greater than all elements to their right is : ";
// do for each element
for (int i = 0; i < n; i++)
{
// remove all the elements that are less than the current element
while ((!stk.empty()) && (stk.top() < arr[i]))
{
stk.pop();
}
// push current element into the stack
stk.push(arr[i]);
}
// Print all elements in stack one by one
while (!stk.empty())
{
cout << stk.top() << ",";
stk.pop();
}
}
4) Time Complexity:- O(n)
5) Auxillary Space:-O(n)
bcoz a stack is used
Ex2) Solving the above problem
In Linear Time O(n) Time. AND
In Constant Space O(1)
1) Traverse array from the back
2) If curr_ele > max_so_far
Then curr_elem = max_so_far
AND max_so_far = One of such elements Hence Print it.
void find3(int arr[], int n)
{
int max_so_far = INT_MIN;
cout<<"\nThe elements in an array which is greater than all elements to their right is : ";
// traverse the array from right to left
for (int i = n - 1; i >= 0; i--)
{
// if current element is greater than maximum so far, print it and update max_so_far
if (arr[i] > max_so_far)
{
max_so_far = arr[i];
printf("%d,", arr[i]);
}
}
}
3) Time Complexity :- O(n)
4) Auxillary Space :- O(1)
Q) Minimum no. of bracket reversals to make an expression balanced.
https://www.techiedelight.com/next-greater-element/
Q) Find the next greater element for every array element
Given an integer array, find the next greater element for every array element.
The next greater element of a number x The first greater number to the right of x in the
1) In other words,
for each element A[i] in the array,
find an element A[j] such that j > i and A[j] > A[i]
and the value of j should be as minimum as possible.
2) If the NGE doesn’t exist in the array for any element, consider it -1.
NGE of last element is always -1.
1) Push the 1st element of array into the stack
2) Pick rest of the elements one by one from the array
Let the current_element be called curr_ele
If stack is not empty....compare s.top() with curr_ele
While curr_ele > s.top()….pop out the top elements(say x1,x2,..)….so curr_ele = NGE of x
3) Now push curr_ele into the stack
4) After steps 2,3 are complete…..if stack is not empty…That means those elements which are in
have no NGE
5) So pop out all the elements one by one from the stack and print their NGE as -1
1) Time Complexity:- O(n)….Worst case occurs when all elements are sorted in decreasing order
2) Auxillary Complexity :- O(n)….Additional stack is used
1)
void print_NGE (int arr [],int n)
{
int next ,i,j;
for(i=0;i<n-1;i++)
{
next = -1;
for(j=i+1;j<n;j++)
{
if(arr [j]>arr [i])
{
next = arr[j];
break ;
}
}
cout <<arr [i]<<"--->" <<next <<endl ;
}
}
1) Time Complexity :- O(n 2 )… Worst case occurs when all element are sorted in decreasing
order
2) Auxillary Space :- O(1)….No extra space is used
https://www.geeksforgeeks.org/stack-set-4-evaluation-postfix-expression/
Q) Evaluate postfix expression using a stack
Single Digit Operand
Ex1) Logic
1) Scan the given expression from leftright and process them as mentioned in Steps 2,3
2) If current_character of the expression is an operand
Then push it into the stack
This Stack is also called operand Stack
3) If current_character of the expression is an operator (say +)
pop out 2 elements from the stack (say x,y)
Compute the 2 popped out elements using the current_character_operator (i.e result = y+x
Then Push the result back into the stack
4) So like this when all the characters in the expression are finished processing
We are left with only one element in the stack
i.e the postfix value of the given expression
Ex2) The Program
int postfix1(string exp)
{
stack<int> stk;
int i;
for(i=0;i<exp.length();i++)
{
// If current_character is an operand
// Then push it into the stack
if( (exp[i]>='0') && (exp[i]<='9'))
{
stk.push(exp[i]-'0');
}
// If current_character is an operator
// pop out 2 elements from the stack (say x,y)
// Compute the 2 popped out elements using the current_character_operator
// Then Push the result back into the stack
else
{
int x = stk.top();
stk.pop();
int y = stk.top();
stk.pop();
if(exp[i]=='+')
stk.push(y+x);
if(exp[i]=='-')
stk.push(y-x);
if(exp[i]=='*')
stk.push(y*x);
if(exp[i]=='/')
stk.push(y/x);
}
}
// At this point the stack is left with only one element
// i.e the postfix value of the given expression
return stk.top();
}
// Driver code
int main()
{
string exp1 = "231*+9-";
int answer1 = postfix1(exp1);
cout<<"The Postfix Form = "<<exp1<<endl;
cout<<"The Postfix value = "<<answer1<<endl;
}
Output :-
The Postfix Form = 231*+9-
The Postfix value = -4
1) Time Complexity :- O(n)
We have scanned the entire expression once ( n = exp.length() )
2) Auxillary Space :- O(n)
i.e we have used a stack
Q) Evaluate prefix expression using a stack
Single Digit Operand
1) Same Concept is applied
But the Prefix expression is scanned from R L
Q) Evaluation of Prefix Notation using Operand Stack (Workout)
1) Prefix expression = + - 9 2 7 * 8 / 4 12
Scan the prefix expression from R L
Character Scanned Operand Stack
12 12
stk.push(12);
4 12,4
stk.push(4);
/ 3
int x = stk.pop() x = 4
int y = stk.pop() y = 12
y / x = 3
stk.push(y/x) = stk.push(3)
8 3,8
stk.push(8);
* 24
int x = stk.pop() x = 8
int y = stk.pop() y = 3
y * x = 24
stk.push(y*x) = stk.push(24)
7 24,7
stk.push(7);
2 24,7,2
stk.push(2);
- 24,5
int x = stk.pop() x = 2
int y = stk.pop() y = 7
y - x = 5
stk.push(y-x) = stk.push(5)
+ 29
int x = stk.pop() x = 5
int y = stk.pop() y = 24
y + x = 29
stk.push(y+x) = stk.push(29)
Final Answer 29
Q) Evaluation of Postfix Notation using Operand Stack (Workout)
1) Postfix expression = 9 3 4 * 8 + 4 / –
Scan the postfix expression from L R.
Character Scanned Operand Stack
9 9
stk.push(9);
3 9,3
stk.push(3);
4 9,3,4
stk.push(4);
* 9,12
int x = stk.pop() x = 4
int y = stk.pop() y = 3
y * x = 12
stk.push(y*x) = stk.push(12)
8 9,12,8
stk.push(8);
+ 9,20
int x = stk.pop() x = 8
int y = stk.pop() y = 12
y + x = 20
stk.push(y+x) = stk.push(20)
4 9,20,4
stk.push(4);
/ 9,5
int x = stk.pop() x = 4
int y = stk.pop() y = 20
y / x = 5
stk.push(y-x) = stk.push(5)
- 4
int x = stk.pop() x = 5
int y = stk.pop() y = 9
y - x = 4
stk.push(y-x) = stk.push(4)
Final Answer 4
Note :-
1 <= No. of elements in Operand Stack <= 3.
The maximum no. of elements present at any time of operand stack = 3.
https://www.techiedelight.com/merging-overlapping-intervals/
Q) Merging overlapping intervals
Given a set of intervals
First merge all overlapping intervals
Then print the non overlapping intervals
Ex1) Process
1) The idea is to sort the intervals in increasing order of their starting time.
Then create an empty stack
2) Now for each interval curr
If (Stk is empty) Then insert curr into stk.
If (top interval of stk doesn’t overlap with current interval) curr.begin > top.end
Then push it into the stk.
3) If (top interval of stk overlaps with current interval)
And curr.end > top.end
Then merge both the intervals i.e top.end = curr.end
4) At the end
Stack is left with non-overlapping intervals
Simply print them
Ex2) The Program.
#include <iostream> // Function to Merge Non Ov
#include <stack> void mergeIntervals(vector<I
#include <vector> {
#include <algorithm> // Sort Intervals in in
using namespace std; ime.
sort(intervals.begin(),
struct Interval stack<Interval> stk;
{
int start,end; // Do it for each Inter
}; for(const Interval &curr
{
// Sort Intervals based on their starting time in asc order // If Stack is emp
bool sortByStartingTime(const Interval &a, const Interval &b) // Then insert cur
{ if( stk.empty() )
return (a.start < b.start); stk.push(curr);
}
Interval top = stk.t
int main()
{ // If the 2 Interv
vector<Interval> intervals = { { 1, 5 }, { 2, 3 }, { 4, 6 }, // Then insert cur
{ 7, 8 }, { 8, 10 }, {12, 15} if(curr.start > stk.
}; stk.push(curr);
mergeIntervals(intervals); // If the 2 Interv
// AND curr.end >
return 0; // Then top.end =
} if(curr.end > stk.to
stk.top().end =
Output :-
The Non-Overlapping Intervals are =
}
{12,15}
{7,10} // After completing the
{1,6} // The Stack stk contai
// Hence now just print
cout<<"\nThe Non-Overlap
while(!stk.empty())
{
Interval x = stk.top
stk.pop();
printf("\n{%d,%d}",
}
}
1) Time Complexity = O(nlogn)
Time taken to sort = O(nlogn)
Time taken to traverse the entire Interval array = O(n)
Time taken to traverse stk = O(n)
Overall Time Complexity = O(n).
n = No. of Given Intervals = intervals.size()
2) Space Complexity = O(n)
Bcoz of the Stack stk used.
https://www.techiedelight.com/recursive-solution-sort-stack/
Q) Sort a Given Stack using Recursion
Ex1) Idea
1) This problem is a variant of the reverse Stack using Recursion.
2) How to do it
Pop all items from the stack stk one by one and hold them in the call stack.
Then as the recursion unfolds Then insert each of those popped values from Call Stack
i.e Sorted Insert each of those popped values from Call Stack back into the Input Stack.
3) The sortedInsert() routine is similar to the recursive Insertion Sort.
Ex2) The Program
#include <iostream> // Insert the given key into the sorted
#include <stack> while maintaining its sorted order.
#include <vector>
using namespace std; // This is similar to the recursive ins
void sortedInsert(stack<int> &stk, int k
{
int main() // Insert the key into the stack.
{ // Only if it satisfies this Base
vector<int> list = { 5, -2, 9, -7, 3 }; if( (stk.empty()) || (key > stk.top(
{
stack<int> stk; stk.push(key);
for (int x : list) { return;
stk.push(x); }
}
// Pop all items from the stack
cout<<"\n\nStack stk before sorting : "; and hold them in the call stack
printStack(stk); int x = stk.top();
stk.pop();
// Sorting the Stack stk. sortedInsert(stk, key);
sortStack(stk);
// After the recursion unfolds
cout <<"\n\nStack stk after sorting: "; // Then push each item into stk fr
printStack(stk); stk.push(x);
}
return 0;
} void sortStack(stack<int> &stk)
{
Output :- if(stk.empty())
Stack stk before sorting : return;
3
-7 int x = stk.top();
9 stk.pop();
-2 sortStack(stk);
5
// After the recursion unfolds
// Then sortedInsert each item x
Stack stk after sorting: into stk from the call stack
9 sortedInsert(stk, x);
5
3
-2
// Print the contents of the Stack stk.
-7
void printStack(stack<int> stk)
{
while (!stk.empty())
{
int x = stk.top();
stk.pop();
printf("\n%d",x);
}
cout << endl;
}
1) Time Complexity = O(n 2 )
Due to a similar reason in the previous Question.
2) Space Complexity = O(n)
O(n) If we take into account the implicit space for the Call Stack.
https://www.geeksforgeeks.org/stack-set-2-infix-to-postfix/?ref=rp
https://www.geeksforgeeks.org/convert-infix-prefix-notation/?ref=rp
https://www.geeksforgeeks.org/infix-to-prefix-conversion-using-two-stacks/?ref=rp
Q) Covert Infix expression to Postfix expression using Stack
Procedure:-
1) Scan the infix expression from L R
2) If the scanned character is an operand….Output it
3) If Scanned character is an operator
a) If precedence(scanned_operator) > precedence(operator at the top of stack)
b) Else If Stack is empty
c) Else if the top of the Stack contains Opening paranthesis ‘(‘
d) If either of the above 3 cases are true Then push the scanned operator in the Stack
4) If the scanned character is an operator
a) If precedence(scanned_operator) <= precedence(operator at the top of stack)
b) Then one by one keep on popping out of the Stack all those operators x which satisfy:-
precedence(scanned_operator) <= precedence(x)
Stop popping out when the precedence(x) < precedence(scanned_operator)
Also while popping out operators from the Stack…If opening or closing paranthesis is e
(i.e ‘(‘ or ‘)’ is encountered) Then stop popping at once
5) If the scanned character is an ‘(‘, push it to the stack.
6) If the scanned character is an ‘)‘
Keep on popping elements from the Stack till a ‘)’ is encountered
Also Keep on adding those popped elements to the output
Discard both the paranthesis
7) Perform Steps 2-6 till the entire infix expression has been scanned
8) Now after step 7….There is some content in the output….and some content in the Stack
Now pop out elements one by one from the Stack until the Stack is empty
And keep on adding the popped elements of the Stack to the output
9) Hence Finally
The Stack is empty
Output contains the Postfix Expression
Q) Convert Infix to Prefix expression using Stack
Procedure:-
1) Suppose infix_expression = A+B*C
2) Reverse the Infix Expression Hence reversed_infix_expression = C*B+A
While Reversing each ‘(‘ will become ‘)’
While Reversing each ‘)‘ will become ‘(’
3) Obtain postfix expression of the reversed_infix_expression Hence postfix_expression = CB
4) Reverse the Above postfix_expression Hence result = +A*BC.
5) Hence the required prefix_expression = +A*BC.
Formula :-
1) prefix_expression = reverse( infix_to_postfix(reversed_infix_expression) )
https://www.techiedelight.com/implement-a-queue-using-stack-data-structure/
Q) Implement Queues using 2 Stacks
https://www.geeksforgeeks.org/reversing-first-k-elements-queue/
Q) Reverse the first k elements of the queue
Q) Reversing String in C++(Using Stacks,loops)
Q)Some Basic Stack Applications ( Part 1)
1) Create an empty stack.
2) Tokenize the input string into words using spaces as separator(delimeter) with the help
3) Push the words into the stack.
4) Pop the words one by one from the stack untill the stack is empty
Q) Some Basics
1) A Stack is a Linear DS
Which follows LIFO priciple (Last in First Out)(Last element inserted is the first element r
Or the FILO principle (First in Last Out) (First element inserted is the last element remove
2) In computers memory :-
Stack implemented by Queue/Linked Lists.
Auxillary Space taken by Stack = O(n).
3) Time taken for Stack operations = O(1) = i.e constant time :-
push(x) , pop() , peek()
isFull() , isEmpty()
Q) Some Basic Stack Applications(Related to trees)
Q) Iterative Post Order Traversal (Using 2 stacks)
1) Unlike Linked Lists,1D arrays and other linear data structures which are traversed in linear ord
2) Trees can be traversed in multiple ways
Depth First Search (Pre-order,Post-Order,In-Order traversals)
Breadth first Search (Level-Order traversals)
Process :-
1) Push root into stack 1
2) Loop while the stack 1 is not empty
Pop out a node from stack 1 (say x)….and push it into stack 2
Push left and right children of popped node x (i.e x left,xright)…into the stack 1
3) After Step 2….stack 2 will contain elements from bottom to top in reverse post_order
4) So now just pop elements from stack 2 and print them…i.e print contents of stack 2 from top to
bottom
Q) What is a Queue
1) Aqueue is a data structure which follows FIFO (First-In, First-Out) principle.
i.e Element that is inserted first is the first one to be taken out.
The elements in a queue are added at one end called the REAR.
The elements in a queue are removed from another end called the FRONT.
2) There are 4 Queues
Linear Queue
Linear Dequeue
Circular Queue
Circular Dequeue.
3) Note :-
The process of inserting an element x in the queue = enqueue(x).
The process of deleting an element from the queue = dequeue
Q) What are Priority Queues
Q) Array implementation of Linear Queue
Ex1) Basic Concepts :-
1) If front = rear = -1
Then LinearQ is empty
2) If front = rear
If both front,rear point to the same location.
Then the LinearQ has only 1 element.
3) If rear = max_size – 1
Then LinearQ is full
4) Overflow Condition of LinearQ
Overflow condition means
o LinearQ is already full
o But still we want to insert more elements in the LinearQ
rear = max_size - 1
max_size = Max size of the LinearQ represented using array
5) Underflow Condition of LinearQ
Underflow condition means
o LinearQ is already empty
o But still we want to delete an element from the LinearQ
Ex2) Declare class and constructor for the LinearQ
class LinearQ
{
int front;// front points to the front element of the queue
int rear;// rear points to the last element of the queue
int* arr;// Linear Array to store circularQ elements
int max_size;// Refers to the size of the Linear Q
int curr_size;// Refers to the current_size of the Linear Q
public:
// Constructor to initialize the Q
LinearQ(int s)
{
front = rear = -1;
max_size = s;
arr = new int[s];
curr_size = 0;
}
// Destructor to de-allocate(free)memory allocated to circularQ
~LinearQ()
{
delete[] arr;
}
bool isFull();
bool isEmpty();
int count();
int get_front();
void insert(int x);
void deletion();
void display();
};
Ex3)
Q1) Given an array….Print the Next Greater Element
(NGE) of every element of the array
