Stack Designer

1. You are given an array arr of size N. You need to push the elements of the array into a stack and
then print them while popping.
Example 1:
Input:
n=5
arr = {1 2 3 4 5}
Output:
54321
Example 2:
Input: n = 7
arr = {1 6 43 1 2 0 5}
Output: 5 0 2 1 43 6 1
Your Task:
Since this is a function problem, you don't need to take any input. Just complete the provided
functions _push() and _pop().
Constraints:
1 <= Ai <= 10^7
Ans:-
stack<int>_push(int arr[],int n)
{
//return a stack with all elements of arr inserted in it
stack<int>s;
for(int i=0;i<n;i++)
{
s.push(arr[i]);
}
return s;
}
/* _pop function to print elements of the stack
remove as well
*/void _pop(stack<int> s)
{
//print top and pop for each element until it becomes empty
while(!s.empty())
{
 cout<<s.top()<<" ";
s.pop();
}
}
Operations On Stacks
2. Given a stack of integers and Q queries. The task is to perform the operation on stack according
to the query.
The queries can be of 4 types:
i x: (adds element x in the stack).
r: (removes the topmost element from the stack).
h: Prints the topmost element.
f y: (check if the element y is present or not in the stack). Print "Yes" if present, else "No".
Example 1:
Input: Q = 6
Queries = {(i, 2), (i, 4), (i, 3),
(i, 5), (h), (f, 8)}
Output: 5
No
Explanation: Inserting 2, 4, 3, and 5
onto the stack. Returning top element
which is 5. Finding 8 will give No,
as 8 is not in the stack.
Example 2:
Input:
Q=4
Queries = {(i, 3), (i, 4), (r), (f, 3)}
Output: Yes
Explanation: Inserting 3 and 4 onto the stack.
Removing 4 from the stack.
Finding 3 will give Yes as output
because 3 is available in the stack.
Your Task:
Your task is to complete functions insert(), remove(), headOf_Stack() which takes a stack as input
parameter, and find() which takes a stack and value as input parameter, to insert, remove returning
top element, and finding the element in stack respectively.
Expected Time Complexity:
For find(): O(N),
For others: O(1).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ Number of queries ≤ 10^3
//Function to push an element into the stack.
void insert(stack<int> &s,int x)
{
s.push(x);
}
//Function to remove top element from stack.
void remove(stack<int> &s)
{
s.pop();
}
//Function to print the top element of stack.
void headOf_Stack(stack<int> &s)
{
int x= s.top();
cout<<x<<" "<<endl;
}
//Function to search an element in the stack.

bool find(stack<int> s, int val)

{
bool exists=false;
while(!s.empty() && !exists)
{
if(s.top() == val) exists = true;
s.pop();
}
if(exists==true)
{
return true;
}
Else
{
return false;
}
}
Reverse Array Using Stack
3. You are given an array arr[] of size N, the task is to reverse the array elements in-place by using
a stack.
Example 1:
Input: N = 5, arr[] = {1, 2, 3, 4, 5}
Output: 5 4 3 2 1
Explanation: After the reverse, array will look like {5, 4, 3, 2, 1}.
Example 2:
Input: N = 1, arr[] = {1}
Output: 1
Explanation: After the reverse, array will look like {1}.
Your Task: You don't need to read any input or print anything. Complete the
function reverseArray() which takes an array size N and array arr[] as parameters and reverses the
array elements in-place using a stack.
Expected Time Complexity: O(N)
Expected Auxilliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^5
class Solution
{
public:
void reverseArray(int n, int* arr)
{
//Reverse the array
if(n == 0)
return;
stack<int>s;
for(int i =0;i< n;i++)
{
s.push(arr[i]);
}
for(int i =0;i< n;i++)
{
arr[i] = s.top();
s.pop();
}
}
};
Parenthesis Checker
4. Given an expression string x. Examine whether the pairs and the orders of {,},(,),[,] are correct in
exp. For example, the function should return 'true' for exp = [()]{}{[()()]()} and 'false' for exp = [(]).
Note: The drive code prints "balanced" if function return true, otherwise it prints "not balanced".
Example 1:
Input:
{([])}
Output:
True
Explanation: { ( [ ] ) }.
Same colored brackets can form balanced pairs, with 0 number of unbalanced bracket.
Example 2:
Input:
()
Output:
True
Explanation: (). Same bracket can form balanced pairs, and here only 1 type of bracket is present and
in balanced way.
Example 3:
Input:
([]
Output:
False
Explanation: ([]. Here square bracket is balanced but the small bracket is not balanced and Hence , the
output will be unbalanced.
Your Task:
This is a function problem. You only need to complete the function ispar() that takes a string as
a parameter and returns a boolean value true if brackets are balanced else returns false.
The printing is done automatically by the driver code.
Expected Time Complexity: O(|x|)
Expected Auixilliary Space: O(|x|)
Constraints:
1 ≤ |x| ≤ 32000
class Solution
{
public:
//Function to check if brackets are balanced or not.
bool ispar(string x)
{
// Your code here
stack<char>st;
for(int i=0; i<x.size();i++)
{
if(x[i]=='('|| x[i]=='{'|| x[i]=='[')
{
st.push(x[i]);
}
else if(x[i]==')')
{
if(!st.empty()&&st.top()=='(')
{
st.pop();

}
Else { return false; }
}
else if(x[i]=='}')
{
if(!st.empty()&& st.top()=='{')
{
st.pop();
}
else { return false; }
}
else if(x[i]==']')
{
if(!st.empty()&& st.top()=='[')
{
st.pop();
}
else { return false; }
}
}
if(st.empty())
{
return true;
}
 else
{
return false;
}
}
};
Queue Push & Pop
5. Given an array arr[] of size N, enqueue the elements of the array into a queue and then dequeue
them.
Example 1:
Input:N = 5
arr[] = 1 2 3 4 5
Output:
12345
Example 2:
Input:
N=7
arr[] = 1 6 43 1 2 0 5
Output:
1 6 43 1 2 0 5
Your Task:
You don't need to read any input. Your task is to complete the functions push() and _pop(). The
function push() takes the array and its size as the input parameters and returns the queue formed,
and the function _pop(), takes the queue as the input parameter and prints the elements of the
queue.
Expected time complexity: O(n)
Expected space complexity: O(n)
Constraints:
1 <= Ai <= 10^7

queue<int>_push(int arr[],int n)
{
//return a queue with all elements of arr inserted in it
queue<int>q;
for(int i=0;i<n;i++)
{
int a = arr[i];
q.push(a);
 }
return q;
}
void _pop(queue<int>q)
{
//print front and dequeue for each element until it becomes empty
while(!q.empty())
{
cout << q.front() << " ";
q.pop();
}
}

Operations on Queue

6. Given a queue of integers and Q queries. The task is to perform operations on queue according to
the query.
Queries are as:
i x : (adds element x in the queue from rear).
r : (Removes the front element of queue).
h : (Returns the front element).
f y : (check if the element y is present or not in the queue). Return "Yes" if present, else "No".
Example 1:
Input:Q = 6
Queries = i 2 i 4 i 3 i 5 h f 8
Output:
2
No
Explanation: Inserting 2, 4, 3, and 5 on to the queue: 2 4 3 5. h means front So front is 2. f is find. 8 is
not in queue so No.
Example 2:
Input:Q = 4
Queries = i 3 i 4 r f 3
Output: No
Explanation: Inserting 3 and 4 . When we return and remove 3 and then when we find 3 , it will return
NO as output as 3 is not present in the queue.
Your Task:
Your task is to complete functions enqueue(), dequeue(), front() and find() which performs the
operations described above in the problem description.
Expected Time Complexity: O(1) for enqueue(), dequeue() and front(); O(N) for find().
Expected Auxiliary Space: O(1) for all the 4 functions.
Constraints:
1 <= Q <= 10^3
class Solution
{
public:
//Function to push an element in queue.
void enqueue(queue<int> &q,int x)
{
q.push(x);
}
//Function to remove front element from queue.
void dequeue(queue<int> &q)
{
q.pop();
}
//Function to find the front element of queue.
int front(queue<int> &q)
{
return q.front();
}
//Function to find an element in the queue.
string find(queue<int> q, int x)
{
while (!q.empty())
{
if (q.front() == x)
return "Yes";
q.pop();
}
return "No";
}
};
Queue Reversal
7. Given a Queue Q containing N elements. The task is to reverse the Queue. Your task is to
complete the function rev(), that reverses the N elements of the queue.
Example 1:
Input:6
4 3 1 10 2 6
Output: 6 2 10 1 3 4
Explanation: After reversing the given elements of the queue , the resultant queue will be 6 2 10 1 3 4.
Example 2:
Input:4
4321
Output: 1 2 3 4
Explanation: After reversing the given elements of the queue , the resultant queue will be 1 2 3 4.
Your Task: You need to complete the function rev that takes a queue as parameter and returns the
reversed queue. The printing is done automatically by the driver code.
Expected Time Complexity : O(n)
Expected Auxilliary Space : O(n)
Constraints:
1 ≤ N ≤ 10^5
1 ≤ elements of Queue ≤ 10^5
class Solution
{
public:
queue<int> rev(queue<int> q)
{
stack<int>st;
//first step-take elemenr fromt queue and push it int staack
while(!q.empty())
{
st.push(q.front());
q.pop();
}
//push all elem from stack to queue
while(!st.empty())
{
q.push(st.top());
st.pop();
}
return q;
}
 };
Queue Traversal
8. You are given a queue. You need to print all the elements in the queue.
Input Format:
The first line of input contains T denoting the number of test cases. The T test cases follow. Each test
case contains a line of input. The line contains n denoting the number of elements in the queue.
Output Format:
For each test case, print all the elements only.
Task:
Since this is a function problem, you don't need to take any input. Just complete the
function TraveseMe that takes the queue. The printing is done by you only.
Constraints:
1 <= T <= 100
1 <= n <= 100
Example:
Input:
1
5
Output:
12345
void TraveseMe(std::queue<int> myqueue)
{
// Traverse through the queue
while (!myqueue.empty())
{
// Print the front element
std::cout << myqueue.front() ;
// Remove the front element
myqueue.pop();
}
}

Deque Implementations
9. A deque is a double-ended queue that allows enqueue and dequeue operations from both the
ends. Given a deque and Q queries. The task is to perform some operation on dequeue according to
the queries as given below:
1. pb: query to push back the element x.
2. pf: query to push element x(given with query) to the front of the deque.
3. pp_b(): query to delete element from the back of the deque.
4. f: query to return a front element from the deque.
Example 1:
Input:
5
pf 5
pf 10
pb 6
f
pp_b
Output:
10
Explanation:
1. After push front deque will be {5}
2. After push front deque will be {10, 5}
3. After push back deque will be {10, 5, 6}
4. Return front element which is 10
5. After pop back deque will be {10, 5}
Example 2:
Input:
2
pf 5
f
Output:
5
Explanation:
1. After push front deque will be {5}
2. Return front element which is 5
Your Task:
Your task is to complete the following functions:
push_back_pb(): Push back the given element and then driver code prints that element.
push_front_pf(): Push front the given element and then driver code prints that element.
pop_back_ppb(): Pop the back element (if exists) and then the driver code prints the size of the
deque.
front_dq(): Return the front elements if it exists, else return -1. The driver code prints the return
value.
Expected Time Complexity: O(1)
Expected Auxilliary Space: O(1)
Constraints:
1 ≤ Number of queries ≤ 10^5
void push_back_pb(deque<int> &dq, int x)
{
dq.push_back(x);
}
// Function to pop element from back of the deque.void pop_back_ppb(deque<int> &dq)
{
if (!dq.empty())
dq.pop_back();
else return;
}
// Function to return element from front of the deque.int front_dq(deque<int> &dq)
{
if (!dq.empty())
return dq.front();
else return -1;
}
// Function to push element x to the front of the deque.void push_front_pf(deque<int> &dq, int x)
{
dq.push_front(x);
}
Dequeue Traversal
10. Given a Deque Deq containing N elements, the task is to traverse the Deq and print its elements
of it.
Note: The output must be printed on different lines for multiple test cases.
Example 1:
Input:
5
12345
Output:
12345
Explanation:
Dqe will look like
{1, 2, 3, 4, 5}.
Example 2:
Input:
1
1
Output:
1
Explanation:
Dqe will look like {1}.
Your task: You don't have to worry about the input. You just have to complete the
function printDeque() which takes a Deque as an input parameter and prints all its elements of it.
Expected Time Complexity: O(N)
Expected Auxilliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^5
void printDeque(deque<int> Deq)
{
for(auto x : Deq)
cout << x << ' ';
cout << "\n";
}
11. Reverse a string using Stack
You are given a string S, the task is to reverse the string using stack.
Constraints:
1 ≤ length of the string ≤ 100
Example:-
Input: S="According"
Output: gnidroccA
Ans:-
stack<char> st;
for(int i=0;i<len;i++)
{
st.push(S[i]);
}
int i=0;
while(!st.empty())
{
S[i++]=st.top();
st.pop();
}
return S;