# Stack Reversal using Recursion Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Stack Reversal using Recursion”.

1. Which of the following statement is true about stack?
a) Pop operation removes the top most element
b) Pop operation removes the bottom most element
c) Push operation adds new element at the bottom
d) Push operation removes the top most element

Explanation: As stack is based on LIFO(Last In First Out) principle so the deletion takes place from the topmost element. Thus pop operator removes topmost element.

2. What is the space complexity of program to reverse stack recursively?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)

Explanation: The recursive program to reverse stack uses memory of the order n to store function call stack.

3. Stack can be reversed without using extra space by _____________
a) using recursion
b) using linked list to implement stack
c) using an extra stack
d) it is not possible

Explanation: If linked list is used for implementing stack then it can be reversed without using any extra space.

4. Which of the following is considered as the top of the stack in the linked list implementation of the stack?
a) Last node
b) First node
c) Random node
d) Middle node

Explanation: First node is considered as the top element when stack is implemented using linked list.

5. What is the time complexity of the program to reverse stack when linked list is used for its implementation?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)

Explanation: As a linked list takes O(n) time for getting reversed thus linked list version of stack will also take the same time.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Which of the following takes O(n) time in worst case in array implementation of stack?
a) pop
b) push
c) isEmpty
d) pop, push and isEmpty takes constant time

Explanation: Functions pop, push and isEmpty all are implemented in constant time in worst case.

7. What will be the time complexity of the code to reverse stack recursively?
a) O(n)
b) O(n log n)
c) O(log n)
d) O(n2)

Explanation: The recurrence relation for the recursive code to reverse stack will be given by-T(n)=T(n-1)+n.This is calculated to be equal to O(n2).

8. Which of the following functions correctly represents the recursive approach to reverse a stack?
a)

```int reverse()
{
if(s.size()<0)
{
int x = s.top();
s.pop();
reverse();
BottomInsert(x);
}
}```

b)

```int reverse()
{
if(s.size()>=0)
{
int x = s.top();
s.pop();
reverse();
BottomInsert(x);
}
}```

c)

```int reverse()
{
if(s.size()>0)
{
int x = s.top();
s.pop();
reverse();
BottomInsert(x);
}
}```

d)

```int reverse()
{
if(s.size()>0)
{
int x = s.top();
BottomInsert(x);
s.pop();
reverse();
}
}```
Explanation: We keep on holding the elements in call stack until we reach the bottom of the stack.Then we insert elements at the bottom.This reverses our stack.

9. Which of the following correctly represents the function to insert elements at the bottom of stack?
a)

``` int BottomInsert(int x)
{
if(s.size()!=0) s.push(x);
else
{
int a = s.top();
s.pop();
BottomInsert(x);
s.push(a);
}
}```

b)

```int BottomInsert(int x)
{
if(s.size()==0) s.push(x);
else
{
int a = s.top();
s.pop();
s.push(a);
BottomInsert(x);
}
}```

c)

```int BottomInsert(int x)
{
if(s.size()==0) s.push(x);
else
{
int a = s.top();
s.pop();
BottomInsert(x);
s.push(a);
}
}```

d)

```int BottomInsert(int x)
{
if(s.size()==0) s.push(x);
else
{
s.pop();
int a = s.top();
BottomInsert(x);
s.push(a);
}
}```
Explanation: We hold all the elements in the call stack until we reach the bottom of stack and then the first if statement is executed as the stack is empty at this stage.Finally we push back all the elements held in the call stack.

10. Which of the following code correctly represents the function to reverse stack without using recursion?
a)

``` #include <stack>
void reverseStack(stack<int> &input, stack<int> &extra)
{
while(input.size()!=0)
{
extra.push(input.top());
input.pop();
}
input.swap(extra);
}```

b)

``` #include <stack>
void reverseStack(stack<int> &input, stack<int> &extra)
{
while(input.size()!=0)
{
extra.push(input.top());
input.pop();
}
extra.swap(input);
}```

c)

``` #include <stack>
void reverseStack(stack<int> &input, stack<int> &extra)
{
while(input.size()!=0)
{
input.pop();
extra.push(input.top());
}
extra.swap(input);
}```

d)

```#include <stack>
void reverseStack(stack<int> &input, stack<int> &extra)
{
while(input.size()==0)
{
input.pop();
extra.push(input.top());
}
extra.swap(input);
}```
Explanation: We are using one extra stack to reverse the given stack. First the elements of the original stack are pushed into the other stack which creates a reversed version of the original stack. Then we swap this stack with the original stack.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]