« Reverse a Stack using another stack

You have been given two stacks that can store integers as the data. Out of the two given stacks, one is populated and the other one is empty. You are required to write a function that reverses the populated stack using the one which is empty.

Input Format :

The first line of input contains an integer N, denoting the total number of elements in the stack.

The second line of input contains N integers separated by a single space, representing the order in which the elements are pushed into the stack.

Output Format:

The only line of output prints the order in which the stack elements are popped, all of them separated by a single space.

Note:

You are not required to print the expected output explicitly, it has already been taken care of. Just make the changes in the input stack itself.

Constraints:

1 <= N <= 10^3 -2^31 <= data <= 2^31 - 1

Time Limit:

1sec

Sample Input 1:

6 1 2 3 4 5 10

Note:

Here, 10 is at the top of the stack. Sample Output 1: 1 2 3 4 5 10

Note:

Here, 1 is at the top of the stack.

Copy
1#include <iostream>
2#include <stack>
3using namespace std;
4
5void reverseStack(stack<int> &input, stack<int> &extra) {
6    //Write your code here
7    if(input.size() <= 1){
8        return;
9    }
10
11    int last = input.top();
12    input.pop();
13
14    reverseStack(input, extra);
15
16    while(!input.empty()){
17        extra.push(input.top());
18        input.pop();
19    }
20
21    input.push(last);
22
23    while(!extra.empty()){
24        input.push(extra.top());
25        extra.pop();
26    }
27
28}
29
30int main() {
31    stack<int> input, extra;
32    int size;
33    cin >> size;
34
35    for (int i = 0, val; i < size; i++) {
36        cin >> val;
37        input.push(val);
38    }
39
40    reverseStack(input, extra);
41
42    while (!input.empty()) {
43        cout << input.top() << " ";
44        input.pop();
45    }
46}