Question

Write code to reverse the order of elements on a stack S.c++

ii. Using one additional queue.

iii. using an additional stack and a non array variable

c++ .

Answer 1

THE CODE FOR THE ABOVE QUESTION IS :

#include<iostream>

#include<stack>

#include<queue>

using namespace std;

/*
   A stack is a data structure based on the concept of last come first out.
   A queue is a data structure based on the concept of first come first out.
**/

/*
    The principle behind reversing a stack using a queue :
   We first empty the stack by transferring the top element in the stack to
the queue one element at a time. Then we transfer one element at a time
   from the front of the queue to the top of the stack again.
   Since the queue is first come first out based therefore the first element from the queue to go
   into the stack is actually the first element which was popped out from the stack originally.
   And this process continues until the queue is empty. Voila! There is our reversed stack.
**/

/*
    The principle behind reversing a stack using a stack:
A stack is last come first out based. Therefore to reverse a stack using a stack, we pop out
the top element from the original stack and push it into the additional stack. Thus the first
element to be popped out will be the last element for the additional stack. This will
continue till the original stack is empty, and then we return the additional stack obtained.
**/

// using template to make our reverse functions generic i.e.
// it can reverse a stack with any data type. You can check out the main function for a demo.
template < typename T >
stack < T > reverseStackUsingQueue(stack < T > S) {
   // declaring the additional queue
    queue < T > Q;

       // transferring one element at a time to the queue until the stack is emptied
    while (!S.empty()) {
      Q.push(S.top());
      S.pop();
    }

       // transferring one element at a time to the stack until the queue is emptied
    while (!Q.empty()) {
      S.push(Q.front());
      Q.pop();
    }

       // returning the new reversed stack
    return S;
} // end reverseStackUsingQueue

// using template to make our reverse functions generic i.e.
// it can reverse a stack with any data type. You can check out the main function for a demo.
template < typename T >
stack < T > reverseStackUsingStack(stack < T > S) {
   // declaring the additional stack and a non array variable
    stack < T > S1;
    T temp;

       // transferring one element at a time from the original stack to the additional stack
    while (!S.empty()) {
      temp = S.top();
      S.pop();
      S1.push(temp);
    }

       // returning the new reversed stack
    return S1;
} // end reverseStackUsingStack

// utility function to print a stack from top to bottom
template < typename T >
void printStack(stack < T > S) {
    // cout << "The stack is : ";
    while (!S.empty()) {
      T temp;
      temp = S.top();
      S.pop();
      cout << temp << " ";
    }
    cout << "\n";
} // end printStack

// driver function
int main() {
   // creating a stack of type integer
stack < int > S1, reverseS1queue, reverseS1stack;
S1.push(1);
S1.push(2);
S1.push(3);
S1.push(4);
S1.push(5);

   // creating a stack of type character
stack < char > S2, reverseS2queue, reverseS2stack;
S2.push('a');
S2.push('b');
S2.push('c');
S2.push('d');
S2.push('e');

   // displaying the original stacks
cout << "Original stacks in the order top to bottom:\n";
cout << "S1: ";
printStack(S1);
cout << "S2 :";
printStack(S2);
cout << "\n";

cout << "Reversed stacks in the order top to bottom:\n";

reverseS1queue = reverseStackUsingQueue(S1);      // reverse stack S1 using queue
reverseS1stack = reverseStackUsingStack(S1);      // reverse stack S1 using stack

cout << "ReverseS1 using additional queue:";
printStack(reverseS1queue);
cout << "ReverseS1 using additional stack:";
printStack(reverseS1stack);

cout << "\n";

reverseS2queue = reverseStackUsingQueue(S2);      // reverse stack S2 using queue
reverseS2stack = reverseStackUsingStack(S2);      // reverse stack S2 using stack

cout << "ReverseS1 using additional queue:";
printStack(reverseS2queue);
cout << "ReverseS1 using additional stack:";
printStack(reverseS2stack);

return 0;
} // end main

SAMPLE OUTPUT :