Reverse Of Stack In C++

A stack represents a data structure in C++ that adheres to the Last In First Out (LIFO) concept. This principle dictates that the element added last is the first to be removed. The following content will explore the process of reversing a stack in C++ through various illustrations.

Methods for Stack handling:

Some methods, which are often used while handling with stack, are:

• ✅ Push: This method is used to add the element to the top of the stack
• ✅ Pop: This method is used to remove the top element in the stack
• ✅ Top: This method will return the most recently added element in the stack. The recently added element will be the top of the element
• ✅ Empty: This method is used to check whether the stack is empty or not
• ✅ Size: This method will give the total number of elements present in the stack

Example:

• ✅ Let's say there is a stack named my stack, which is empty initially.
• ✅ After that, two elements are added that are 10, 20 so here, and the top element is 20
• ✅ Next, another element is pushed into the stack so the top becomes 30.
• ✅ Now, we use another auxiliary stack named auxStack to reverse the stack.

Initially, remove the topmost item from myStack and insert it into auxStack. Repeat this process for all items in myStack, transferring them to auxStack. Ultimately, auxStack will represent the inverse order of myStack. This process essentially involves manipulating the stack to achieve the desired reversal.

myStack

30 ← Top

Reverse of Stack

myStack Empty

auxStack

10 ← Top

Example 1:

Let's consider an example to demonstrate reversing a stack by utilizing an additional temporary stack in C++.

#include <stack>
#include <iostream>
using namespace std;
void reverseStack(stack<int>& s) {
    stack<int> aux;
    while (!s.empty()) {
        int temp = s.top();
        s.pop();
        aux.push(temp);
    }
    s = aux;
}
int main() {
    stack<int> myStack;
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);
    reverseStack(myStack);
    cout << "Reversed Stack: " << endl;
    while (!myStack.empty()) {
        cout << myStack.top() << " ";
        myStack.pop();
    }
    return 0;
}

Output:

Explanation:

A stack named myStack is first created and initialized in the preceding steps. Subsequently, three elements are statically inserted into the stack, with the current top element being 30. Following this, the myStack is passed as an argument to the reverseStack function. The primary purpose of this function is to invert the order of elements within the stack. Within this function, an auxiliary stack named aux is employed. A while loop is utilized to pop all elements from myStack and push them onto the aux stack concurrently. Upon completion of the while loop, the contents of Aux are reassigned to the original myStack.

Example 2:

Let's consider a scenario to demonstrate the reversal of a stack utilizing recursion in C++.

#include <stack>
#include <iostream>
using namespace std;
void insertAtBottom(stack<int>& s, int data) {
    if (s.empty()) {
        s.push(data);
    } else {
        int temp = s.top();
        s.pop();
        insertAtBottom(s, data);
        s.push(temp);
    }
}
void reverseStack(stack<int>& s) {
    if (!s.empty()) {
        int temp = s.top();
        s.pop();
        reverseStack(s);
        insertAtBottom(s, temp);
    }
}
int main() {
    stack<int> myStack;
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);
    reverseStack(myStack);
    while (!myStack.empty()) {
        cout << myStack.top() << " ";
        myStack.pop();
    }
    return 0;
}

Output:

Explanation:

The provided C++ code showcases the reversal of a stack utilizing recursion. Within the code, there are two key functions: insertBottom and reverseStack.

The insertBottom function plays a crucial role in inserting an element at the bottom of the stack. It achieves this by recursively removing elements and then reinstating them in the stack.

On the other hand, the reverseStack function is invoked within the main function, which in turn calls the insertBottom function. This recursive process continues until the entire stack has been reversed. Ultimately, the reversed stack is passed back to the main function for further processing.

Example 3:

Utilizing a vector instead of an auxiliary stack for reversing the stack in C++.

#include <iostream>
using namespace std;
void reverseStack(stack<int>& s) {
    vector<int> tempVec;
    while (!s.empty()) {
        tempVec.push_back( s.top() );
        s.pop();
    }
    for (int i = tempVec.size() - 1; i >= 0; --i) {
        s.push(tempVec[i]);
    }
}
int main() {
    stack<int> myStack;
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    reverseStack(myStack);
    while ( !myStack.empty() ) {
        cout << myStack.top() << " ";
        myStack.pop();
    }
    return 0;
}

Output:

Explanation:

The preceding example showcases the process of reversing a stack. In this case, a stack named myStack is initialized. Several elements are pushed into myStack, following which the reverseStack function is invoked with myStack as an argument. Within the reverseStack function, a temporary vector is employed. Subsequently, a while loop is utilized to pop each element from the stack and append it to the vector until the stack becomes empty. Then, a for loop is implemented to traverse the vector in reverse order. Each element is then pushed back into the stack, effectively reversing its order. Finally, a while loop serves as the primary mechanism for displaying the elements in the reversed stack.