Skip to main content

Reverse stack using another stack

The problem of Reverse Stack using Another Stack involves reversing the elements of a given stack using only one additional auxiliary stack. The task is to implement a function that takes an original stack as input and reverses its elements so that the top element becomes the bottom element and vice versa.

Problem Statement

Given a stack, implement a function reverseStack() that reverses the order of its elements using another auxiliary stack. The original stack should be modified in-place, and the auxiliary stack should be used to achieve the reversal.

Example

Consider the following stack:

11 <- Top 
9  
6  
5  
4  
2  
1

After reversing the stack using another stack, the result should be:

1 <- Top 
2  
4  
5  
6  
9  
11

Idea to Solve the Problem

To reverse the stack using another stack, we can use the following approach:

  1. Create an auxiliary stack to store the reversed elements.
  2. While the original stack is not empty, perform the following steps:
    • Pop the top element data from the original stack.
    • Push data onto the auxiliary stack.
  3. After all elements are processed, the auxiliary stack will contain the elements of the original stack in reversed order.
  4. Set the original stack to be equal to the auxiliary stack. Now, the original stack contains the elements in the reversed order.

Pseudocode

Function reverseStack():
    Create a new MyStack called auxiliary
    While stack is not empty:
        Pop the top element data from stack
        Push data onto auxiliary
    Set stack to be equal to auxiliary

Code Solution

// C program 
// Reverse stack using another stack
#include <stdio.h>
#include <stdlib.h>

// Define stack node
struct StackNode
{
	int element;
	struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
	struct StackNode *top;
	int size;
};
struct MyStack *newStack()
{
	//Make a stack
	struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
	if (stack != NULL)
	{
		//Set node values
		stack->top = NULL;
		stack->size = 0;
	}
	else
	{
		printf("\nMemory overflow when create new stack\n");
	}
}
//Create a new node of stack
struct StackNode *newNode(int element, struct StackNode *next)
{
	//Make a new node
	struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
	if (node == NULL)
	{
		printf("\nMemory overflow when create new stack Node \n");
	}
	else
	{
		node->element = element;
		node->next = next;
	}
	return node;
}
int isEmpty(struct MyStack *stack)
{
	if (stack->size > 0 && stack->top != NULL)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
// Add node at the top of stack
void push(struct MyStack *stack, int element)
{
	// Add stack element
	stack->top = newNode(element, stack->top);
	stack->size++;
}
// return top element of stack
int peek(struct MyStack *stack)
{
	return stack->top->element;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
	if (isEmpty(stack) == 0)
	{
		struct StackNode *temp = stack->top;
		// Change top element of stack
		stack->top = temp->next;
		// remove previous top
		free(temp);
		temp = NULL;
		stack->size--;
	}
}
// This is reverse the stack elements by using of another stack
void reverseStack(struct MyStack *stack)
{
	// Create auxiliary stack
	struct MyStack *auxiliary = newStack();
	int data;
	// Executing the loop until when input element are not empty
	while (isEmpty(stack) == 0)
	{
		// Get the top element of input stack
		data = peek(stack);
		// Remove top of current input stack
		pop(stack);
		// Add data to auxiliary stack
		push(auxiliary, data);
	}
	// Set auxiliary stack as new stack
	stack->top = auxiliary->top;
}
// Print element of stack
void printData(struct MyStack *stack)
{
	struct StackNode *temp = stack->top;
	while (temp != NULL)
	{
		// Display element value
		printf("  %d", temp->element);
		temp = temp->next;
	}
	printf("\n");
}
int main()
{
	struct MyStack *stack = newStack();
	// Add the stack element
	push(stack, 1);
	push(stack, 2);
	push(stack, 4);
	push(stack, 5);
	push(stack, 6);
	push(stack, 9);
	push(stack, 11);
	printf("\n Before Reverse \n");
	printData(stack);
	// reverse operation
	reverseStack(stack);
	printf("\n After Reverse \n");
	printData(stack);
	return 0;
}

Output

 Before Reverse
  11  9  6  5  4  2  1

 After Reverse
  1  2  4  5  6  9  11
/*
   Java Program
   Reverse stack using another stack
*/
// Define stack node
class StackNode
{
	public int element;
	public StackNode next;
	public StackNode(int element, StackNode next)
	{
		this.element = element;
		this.next = next;
	}
}
// Define a custom stack
class MyStack
{
	public StackNode top;
	public int size;
	public MyStack()
	{
		//Set node values
		this.top = null;
		this.size = 0;
	}
	// Add node at the top of stack
	public void push(int element)
	{
		this.top = new StackNode(element, this.top);
		this.size++;
	}
	public Boolean isEmpty()
	{
		if (this.size > 0 && this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	public void pop()
	{
		if (this.size > 0 && this.top != null)
		{
			StackNode temp = this.top;
			// Change top element of stack
			this.top = temp.next;
			// remove previous top
			temp = null;
			this.size--;
		}
	}
	// return top element of stack
	public int peek()
	{
		return this.top.element;
	}
}
public class SortStackElement
{
	public MyStack stack;
	public SortStackElement()
	{
		this.stack = new MyStack();
	}
	// Print element of stack
	public void printData()
	{
		StackNode temp = this.stack.top;
		while (temp != null)
		{
			// Display element value
			System.out.print("   " + temp.element);
			temp = temp.next;
		}
		System.out.print("\n");
	}
	// This is reverse the stack elements by using of another stack
	public void reverseStack()
	{
		// Create auxiliary stack
		MyStack auxiliary = new MyStack();
		int data = 0;
		// Executing the loop until when input element are not empty
		while (this.stack.isEmpty() == false)
		{
			// Get the top element of input stack
			data = this.stack.peek();
			// Remove top of current input stack
			this.stack.pop();
			// Add data to auxiliary stack
			auxiliary.push(data);
		}
		// Set auxiliary stack as new stack
		this.stack = auxiliary;
	}
	public static void main(String[] args)
	{
		SortStackElement task = new SortStackElement();
		// Add the stack element
		task.stack.push(1);
		task.stack.push(2);
		task.stack.push(4);
		task.stack.push(5);
		task.stack.push(6);
		task.stack.push(9);
		task.stack.push(11);
		/*
		Before Reverse
		=============
		11  <- Top 
		9  
		6  
		5  
		4  
		2  
		1
		*/
		System.out.print("\n Before Reverse \n");
		task.printData();
		// reverse operation
		task.reverseStack();
		/*
		After Reverse
		=============
		1  <- Top 
		2  
		4  
		5  
		6  
		9  
		11
		*/
		System.out.print("\n After Reverse \n");
		task.printData();
	}
}

Output

 Before Reverse
   11   9   6   5   4   2   1

 After Reverse
   1   2   4   5   6   9   11
// Include header file
#include <iostream>

using namespace std;
/*
   C++ Program
   Reverse stack using another stack
*/
// Define stack node
class StackNode
{
    public: 
    int element;
    StackNode *next;
    StackNode(int element, StackNode *next)
    {
        this->element = element;
        this->next = next;
    }
};
// Define a custom stack
class MyStack
{
    public: 
    StackNode *top;
    int size;
    MyStack()
    {
        //Set node values
        this->top = NULL;
        this->size = 0;
    }
    // Add node at the top of stack
    void push(int element)
    {
        this->top = new StackNode(element, this->top);
        this->size++;
    }
    bool isEmpty()
    {
        if (this->size > 0 && this->top != NULL)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Remove top element of stack
    void pop()
    {
        if (this->size > 0 && this->top != NULL)
        {
            StackNode *temp = this->top;
            // Change top element of stack
            this->top = temp->next;
            // remove previous top
            delete temp;
            temp = NULL;
            this->size--;
        }
    }
    // return top element of stack
    int peek()
    {
        return this->top->element;
    }
};
class SortStackElement
{
    public: 
    MyStack stack;
    SortStackElement()
    {
        this->stack = MyStack();
    }
    // Print element of stack
    void printData()
    {
        StackNode *temp = this->stack.top;
        while (temp != NULL)
        {
            // Display element value
            cout << "   " << temp->element;
            temp = temp->next;
        }
        cout << "\n";
    }
    // This is reverse the stack elements by using of another stack
    void reverseStack()
    {
        // Create auxiliary stack
        MyStack auxiliary = MyStack();
        int data = 0;
        // Executing the loop until when input element are not empty
        while (this->stack.isEmpty() == false)
        {
            // Get the top element of input stack
            data = this->stack.peek();
            // Remove top of current input stack
            this->stack.pop();
            // Add data to auxiliary stack
            auxiliary.push(data);
        }
        // Set auxiliary stack as new stack
        this->stack = auxiliary;
    }
};
int main()
{
    SortStackElement task = SortStackElement();
    // Add the stack element
    task.stack.push(1);
    task.stack.push(2);
    task.stack.push(4);
    task.stack.push(5);
    task.stack.push(6);
    task.stack.push(9);
    task.stack.push(11);
    /*
    Before Reverse
    =============
    11  <- Top 
    9  
    6  
    5  
    4  
    2  
    1
    */
    cout << "\n Before Reverse \n";
    task.printData();
    // reverse operation
    task.reverseStack();
    /*
    After Reverse
    =============
    1  <- Top 
    2  
    4  
    5  
    6  
    9  
    11
    */
    cout << "\n After Reverse \n";
    task.printData();
    return 0;
}

Output

 Before Reverse
   11   9   6   5   4   2   1

 After Reverse
   1   2   4   5   6   9   11
// Include namespace system
using System;
/*
   C# Program
   Reverse stack using another stack
*/
// Define stack node
public class StackNode
{
    public int element;
    public StackNode next;
    public StackNode(int element, StackNode next)
    {
        this.element = element;
        this.next = next;
    }
}
// Define a custom stack
public class MyStack
{
    public StackNode top;
    public int size;
    public MyStack()
    {
        //Set node values
        this.top = null;
        this.size = 0;
    }
    // Add node at the top of stack
    public void push(int element)
    {
        this.top = new StackNode(element, this.top);
        this.size++;
    }
    public Boolean isEmpty()
    {
        if (this.size > 0 && this.top != null)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Remove top element of stack
    public void pop()
    {
        if (this.size > 0 && this.top != null)
        {
            StackNode temp = this.top;
            // Change top element of stack
            this.top = temp.next;
            // remove previous top
            temp = null;
            this.size--;
        }
    }
    // return top element of stack
    public int peek()
    {
        return this.top.element;
    }
}
public class SortStackElement
{
    public MyStack stack;
    public SortStackElement()
    {
        this.stack = new MyStack();
    }
    // Print element of stack
    public void printData()
    {
        StackNode temp = this.stack.top;
        while (temp != null)
        {
            // Display element value
            Console.Write("   " + temp.element);
            temp = temp.next;
        }
        Console.Write("\n");
    }
    // This is reverse the stack elements by using of another stack
    public void reverseStack()
    {
        // Create auxiliary stack
        MyStack auxiliary = new MyStack();
        int data = 0;
        // Executing the loop until when input element are not empty
        while (this.stack.isEmpty() == false)
        {
            // Get the top element of input stack
            data = this.stack.peek();
            // Remove top of current input stack
            this.stack.pop();
            // Add data to auxiliary stack
            auxiliary.push(data);
        }
        // Set auxiliary stack as new stack
        this.stack = auxiliary;
    }
    public static void Main(String[] args)
    {
        SortStackElement task = new SortStackElement();
        // Add the stack element
        task.stack.push(1);
        task.stack.push(2);
        task.stack.push(4);
        task.stack.push(5);
        task.stack.push(6);
        task.stack.push(9);
        task.stack.push(11);
        /*
        Before Reverse
        =============
        11  <- Top 
        9  
        6  
        5  
        4  
        2  
        1
        */
        Console.Write("\n Before Reverse \n");
        task.printData();
        // reverse operation
        task.reverseStack();
        /*
        After Reverse
        =============
        1  <- Top 
        2  
        4  
        5  
        6  
        9  
        11
        */
        Console.Write("\n After Reverse \n");
        task.printData();
    }
}

Output

 Before Reverse
   11   9   6   5   4   2   1

 After Reverse
   1   2   4   5   6   9   11
<?php
/*
   Php Program
   Reverse stack using another stack
*/
// Define stack node
class StackNode
{
    public $element;
    public $next;

    function __construct($element, $next)
    {
        $this->element = $element;
        $this->next = $next;
    }
}
// Define a custom stack
class MyStack
{
    public $top;
    public $size;

    function __construct()
    {
        // Set node values
        $this->top = null;
        $this->size = 0;
    }
    // Add node at the top of stack
    public  function push($element)
    {
        $this->top = new StackNode($element, $this->top);
        $this->size++;
    }
    public  function isEmpty()
    {
        if ($this->size > 0 && $this->top != null)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Remove top element of stack
    public  function pop()
    {
        if ($this->size > 0 && $this->top != null)
        {
            $temp = $this->top;
            // Change top element of stack
            $this->top = $temp->next;
            // remove previous top
            $temp = null;
            $this->size--;
        }
    }
    // return top element of stack
    public  function peek()
    {
        return $this->top->element;
    }
}
class SortStackElement
{
    public $stack;

    function __construct()
    {
        $this->stack = new MyStack();
    }
    // Print element of stack
    public  function printData()
    {
        $temp = $this->stack->top;
        while ($temp != null)
        {
            // Display element value
            echo "   ". $temp->element;
            $temp = $temp->next;
        }
        echo "\n";
    }
    // This is reverse the stack elements by using of another stack
    public  function reverseStack()
    {
        // Create auxiliary stack
        $auxiliary = new MyStack();
        $data = 0;
        // Executing the loop until when input element are not empty
        while ($this->stack->isEmpty() == false)
        {
            // Get the top element of input stack
            $data = $this->stack->peek();
            // Remove top of current input stack
            $this->stack->pop();
            // Add data to auxiliary stack
            $auxiliary->push($data);
        }
        // Set auxiliary stack as new stack
        $this->stack = $auxiliary;
    }
}

function main()
{
    $task = new SortStackElement();
    // Add the stack element
    $task->stack->push(1);
    $task->stack->push(2);
    $task->stack->push(4);
    $task->stack->push(5);
    $task->stack->push(6);
    $task->stack->push(9);
    $task->stack->push(11);
    /*
    Before Reverse
    =============
    11  <- Top 
    9  
    6  
    5  
    4  
    2  
    1
    */
    echo "\n Before Reverse \n";
    $task->printData();
    // reverse operation
    $task->reverseStack();
    /*
    After Reverse
    =============
    1  <- Top 
    2  
    4  
    5  
    6  
    9  
    11
    */
    echo "\n After Reverse \n";
    $task->printData();
}
main();

Output

 Before Reverse
   11   9   6   5   4   2   1

 After Reverse
   1   2   4   5   6   9   11
/*
   Node Js Program
   Reverse stack using another stack
*/
// Define stack node
class StackNode
{
	constructor(element, next)
	{
		this.element = element;
		this.next = next;
	}
}
// Define a custom stack
class MyStack
{
	constructor()
	{
		//Set node values
		this.top = null;
		this.size = 0;
	}
	// Add node at the top of stack
	push(element)
	{
		this.top = new StackNode(element, this.top);
		this.size++;
	}
	isEmpty()
	{
		if (this.size > 0 && this.top != null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	// Remove top element of stack
	pop()
	{
		if (this.size > 0 && this.top != null)
		{
			var temp = this.top;
			// Change top element of stack
			this.top = temp.next;
			// remove previous top
			temp = null;
			this.size--;
		}
	}
	// return top element of stack
	peek()
	{
		return this.top.element;
	}
}
class SortStackElement
{
	constructor()
	{
		this.stack = new MyStack();
	}
	// Print element of stack
	printData()
	{
		var temp = this.stack.top;
		while (temp != null)
		{
			// Display element value
			process.stdout.write("   " + temp.element);
			temp = temp.next;
		}
		process.stdout.write("\n");
	}
	// This is reverse the stack elements by using of another stack
	reverseStack()
	{
		// Create auxiliary stack
		var auxiliary = new MyStack();
		var data = 0;
		// Executing the loop until when input element are not empty
		while (this.stack.isEmpty() == false)
		{
			// Get the top element of input stack
			data = this.stack.peek();
			// Remove top of current input stack
			this.stack.pop();
			// Add data to auxiliary stack
			auxiliary.push(data);
		}
		// Set auxiliary stack as new stack
		this.stack = auxiliary;
	}
}

function main()
{
	var task = new SortStackElement();
	// Add the stack element
	task.stack.push(1);
	task.stack.push(2);
	task.stack.push(4);
	task.stack.push(5);
	task.stack.push(6);
	task.stack.push(9);
	task.stack.push(11);
	/*
			Before Reverse
			=============
			11  <- Top 
			9  
			6  
			5  
			4  
			2  
			1
			*/
	process.stdout.write("\n Before Reverse \n");
	task.printData();
	// reverse operation
	task.reverseStack();
	/*
			After Reverse
			=============
			1  <- Top 
			2  
			4  
			5  
			6  
			9  
			11
			*/
	process.stdout.write("\n After Reverse \n");
	task.printData();
}
main();

Output

 Before Reverse
   11   9   6   5   4   2   1

 After Reverse
   1   2   4   5   6   9   11
#  Python 3 Program
#  Reverse stack using another stack

#  Define stack node
class StackNode :
	
	def __init__(self, element, next) :
		self.element = element
		self.next = next
	

#  Define a custom stack
class MyStack :
	
	def __init__(self) :
		# Set node values
		self.top = None
		self.size = 0
	
	#  Add node at the top of stack
	def push(self, element) :
		self.top = StackNode(element, self.top)
		self.size += 1
	
	def isEmpty(self) :
		if (self.size > 0 and self.top != None) :
			return False
		else :
			return True
		
	
	#  Remove top element of stack
	def pop(self) :
		if (self.size > 0 and self.top != None) :
			temp = self.top
			#  Change top element of stack
			self.top = temp.next
			#  remove previous top
			temp = None
			self.size -= 1
		
	
	#  return top element of stack
	def peek(self) :
		return self.top.element
	

class SortStackElement :
	
	def __init__(self) :
		self.stack = MyStack()
	
	#  Print element of stack
	def printData(self) :
		temp = self.stack.top
		while (temp != None) :
			#  Display element value
			print("   ", temp.element, end = "")
			temp = temp.next
		
		print(end = "\n")
	
	#  This is reverse the stack elements by using of another stack
	def reverseStack(self) :
		#  Create auxiliary stack
		auxiliary = MyStack()
		data = 0
		#  Executing the loop until when input element are not empty
		while (self.stack.isEmpty() == False) :
			#  Get the top element of input stack
			data = self.stack.peek()
			#  Remove top of current input stack
			self.stack.pop()
			#  Add data to auxiliary stack
			auxiliary.push(data)
		
		#  Set auxiliary stack as new stack
		self.stack = auxiliary
	

def main() :
	task = SortStackElement()
	task.stack.push(1)
	task.stack.push(2)
	task.stack.push(4)
	task.stack.push(5)
	task.stack.push(6)
	task.stack.push(9)
	task.stack.push(11)
	# 
	# 		Before Reverse
	# 		=============
	# 		11  <- Top 
	# 		9  
	# 		6  
	# 		5  
	# 		4  
	# 		2  
	# 		1
	# 		
	
	print("\n Before Reverse ")
	task.printData()
	#  reverse operation
	task.reverseStack()
	# 
	# 		After Reverse
	# 		=============
	# 		1  <- Top 
	# 		2  
	# 		4  
	# 		5  
	# 		6  
	# 		9  
	# 		11
	# 		
	
	print("\n After Reverse ")
	task.printData()

if __name__ == "__main__": main()

Output

 Before Reverse
    11    9    6    5    4    2    1

 After Reverse
    1    2    4    5    6    9    11
#  Ruby Program
#  Reverse stack using another stack

#  Define stack node
class StackNode  
	# Define the accessor and reader of class StackNode  
	attr_reader :element, :next
	attr_accessor :element, :next
 
	
	def initialize(element, nextNode) 
		self.element = element
		self.next = nextNode
	end

end

#  Define a custom stack
class MyStack  
	# Define the accessor and reader of class MyStack  
	attr_reader :top, :size
	attr_accessor :top, :size
 
	
	def initialize() 
		# Set node values
		self.top = nil
		self.size = 0
	end

	#  Add node at the top of stack
	def push(element) 
		self.top = StackNode.new(element, self.top)
		self.size += 1
	end

	def isEmpty() 
		if (self.size > 0 && self.top != nil) 
			return false
		else 
			return true
		end

	end

	#  Remove top element of stack
	def pop() 
		if (self.size > 0 && self.top != nil) 
			temp = self.top
			#  Change top element of stack
			self.top = temp.next
			#  remove previous top
			temp = nil
			self.size -= 1
		end

	end

	#  return top element of stack
	def peek() 
		return self.top.element
	end

end

class SortStackElement  
	# Define the accessor and reader of class SortStackElement  
	attr_reader :stack
	attr_accessor :stack
 
	
	def initialize() 
		self.stack = MyStack.new()
	end

	#  Print element of stack
	def printData() 
		temp = self.stack.top
		while (temp != nil) 
			#  Display element value
			print("   ", temp.element)
			temp = temp.next
		end

		print("\n")
	end

	#  This is reverse the stack elements by using of another stack
	def reverseStack() 
		#  Create auxiliary stack
		auxiliary = MyStack.new()
		data = 0
		#  Executing the loop until when input element are not empty
		while (self.stack.isEmpty() == false) 
			#  Get the top element of input stack
			data = self.stack.peek()
			#  Remove top of current input stack
			self.stack.pop()
			#  Add data to auxiliary stack
			auxiliary.push(data)
		end

		#  Set auxiliary stack as new stack
		self.stack = auxiliary
	end

end

def main() 
	task = SortStackElement.new()
	task.stack.push(1)
	task.stack.push(2)
	task.stack.push(4)
	task.stack.push(5)
	task.stack.push(6)
	task.stack.push(9)
	task.stack.push(11)
	# 
	# 		Before Reverse
	# 		=============
	# 		11  <- Top 
	# 		9  
	# 		6  
	# 		5  
	# 		4  
	# 		2  
	# 		1
	# 		
	
	print("\n Before Reverse \n")
	task.printData()
	#  reverse operation
	task.reverseStack()
	# 
	# 		After Reverse
	# 		=============
	# 		1  <- Top 
	# 		2  
	# 		4  
	# 		5  
	# 		6  
	# 		9  
	# 		11
	# 		
	
	print("\n After Reverse \n")
	task.printData()
end

main()

Output

 Before Reverse 
   11   9   6   5   4   2   1

 After Reverse 
   1   2   4   5   6   9   11

/*
   Scala Program
   Reverse stack using another stack
*/
// Define stack node
class StackNode(var element: Int , var next: StackNode)
{
}
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
    def this()
    {
        this(null, 0);
    }
    // Add node at the top of stack
    def push(element: Int): Unit = {
        this.top = new StackNode(element, this.top);
        this.size += 1;
    }
    def isEmpty(): Boolean = {
        if (this.size > 0 && this.top != null)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Remove top element of stack
    def pop(): Unit = {
        if (this.size > 0 && this.top != null)
        {
            var temp: StackNode = this.top;
            // Change top element of stack
            this.top = temp.next;
            // remove previous top
            temp = null;
            this.size -= 1;
        }
    }
    // return top element of stack
    def peek(): Int = {
        return this.top.element;
    }
}
class SortStackElement(var stack: MyStack)
{
    def this()
    {
        this(new MyStack());
    }
    // Print element of stack
    def printData(): Unit = {
        var temp: StackNode = this.stack.top;
        while (temp != null)
        {
            // Display element value
            print("   " + temp.element);
            temp = temp.next;
        }
        print("\n");
    }
    // This is reverse the stack elements by using of another stack
    def reverseStack(): Unit = {
        // Create auxiliary stack
        var auxiliary: MyStack = new MyStack();
        var data: Int = 0;
        // Executing the loop until when input element are not empty
        while (this.stack.isEmpty() == false)
        {
            // Get the top element of input stack
            data = this.stack.peek();
            // Remove top of current input stack
            this.stack.pop();
            // Add data to auxiliary stack
            auxiliary.push(data);
        }
        // Set auxiliary stack as new stack
        this.stack = auxiliary;
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var task: SortStackElement = new SortStackElement();
        // Add the stack element
        task.stack.push(1);
        task.stack.push(2);
        task.stack.push(4);
        task.stack.push(5);
        task.stack.push(6);
        task.stack.push(9);
        task.stack.push(11);
        /*
        Before Reverse
        =============
        11  <- Top 
        9  
        6  
        5  
        4  
        2  
        1
        */
        print("\n Before Reverse \n");
        task.printData();
        // reverse operation
        task.reverseStack();
        /*
        After Reverse
        =============
        1  <- Top 
        2  
        4  
        5  
        6  
        9  
        11
        */
        print("\n After Reverse \n");
        task.printData();
    }
}

Output

 Before Reverse
   11   9   6   5   4   2   1

 After Reverse
   1   2   4   5   6   9   11
/*
   Swift 4 Program
   Reverse stack using another stack
*/
// Define stack node
class StackNode
{
    var element: Int;
    var next: StackNode? ;
    init(_ element: Int, _ next: StackNode? )
    {
        self.element = element;
        self.next = next;
    }
}
// Define a custom stack
class MyStack
{
    var top: StackNode? ;
    var size: Int;
    init()
    {
        //Set node values
        self.top = nil;
        self.size = 0;
    }
    // Add node at the top of stack
    func push(_ element: Int)
    {
        self.top = StackNode(element, self.top);
        self.size += 1;
    }
    func isEmpty()->Bool
    {
        if (self.size > 0 && self.top != nil)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Remove top element of stack
    func pop()
    {
        if (self.size > 0 && self.top != nil)
        {
            var temp: StackNode? = self.top;
            // Change top element of stack
            self.top = temp!.next;
            // remove previous top
            temp = nil;
            self.size -= 1;
        }
    }
    // return top element of stack
    func peek()->Int
    {
        return self.top!.element;
    }
}
class SortStackElement
{
    var stack: MyStack;
    init()
    {
        self.stack = MyStack();
    }
    // Print element of stack
    func printData()
    {
        var temp: StackNode? = self.stack.top;
        while (temp != nil)
        {
            // Display element value
            print("   ", temp!.element, terminator: "");
            temp = temp!.next;
        }
        print(terminator: "\n");
    }
    // This is reverse the stack elements by using of another stack
    func reverseStack()
    {
        // Create auxiliary stack
        let auxiliary: MyStack = MyStack();
        var data: Int = 0;
        // Executing the loop until when input element are not empty
        while (self.stack.isEmpty() == false)
        {
            // Get the top element of input stack
            data = self.stack.peek();
            // Remove top of current input stack
            self.stack.pop();
            // Add data to auxiliary stack
            auxiliary.push(data);
        }
        // Set auxiliary stack as new stack
        self.stack = auxiliary;
    }
}
func main()
{
    let task: SortStackElement = SortStackElement();
    // Add the stack element
    task.stack.push(1);
    task.stack.push(2);
    task.stack.push(4);
    task.stack.push(5);
    task.stack.push(6);
    task.stack.push(9);
    task.stack.push(11);
    /*
    Before Reverse
    =============
    11  <- Top 
    9  
    6  
    5  
    4  
    2  
    1
    */
    print("\n Before Reverse ");
    task.printData();
    // reverse operation
    task.reverseStack();
    /*
    After Reverse
    =============
    1  <- Top 
    2  
    4  
    5  
    6  
    9  
    11
    */
    print("\n After Reverse ");
    task.printData();
}
main();

Output

 Before Reverse
    11    9    6    5    4    2    1

 After Reverse
    1    2    4    5    6    9    11
/*
   Kotlin Program
   Reverse stack using another stack
*/
// Define stack node
class StackNode
{
    var element: Int;
    var next: StackNode ? ;
    constructor(element: Int, next: StackNode ? )
    {
        this.element = element;
        this.next = next;
    }
}
// Define a custom stack
class MyStack
{
    var top: StackNode ? ;
    var size: Int;
    constructor()
    {
        //Set node values
        this.top = null;
        this.size = 0;
    }
    // Add node at the top of stack
    fun push(element: Int): Unit
    {
        this.top = StackNode(element, this.top);
        this.size += 1;
    }
    fun isEmpty(): Boolean ?
    {
        if (this.size>0 && this.top != null)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Remove top element of stack
    fun pop(): Unit
    {
        if (this.size>0 && this.top != null)
        {
            var temp: StackNode ? = this.top;
            // Change top element of stack
            this.top = temp?.next;
            this.size -= 1;
        }
    }
    // return top element of stack
    fun peek(): Int
    {
        return this.top!!.element;
    }
}
class SortStackElement
{
    var stack: MyStack;
    constructor()
    {
        this.stack = MyStack();
    }
    // Print element of stack
    fun printData(): Unit
    {
        var temp: StackNode ? = this.stack.top;
        while (temp != null)
        {
            // Display element value
            print("   " + temp.element);
            temp = temp.next;
        }
        print("\n");
    }
    // This is reverse the stack elements by using of another stack
    fun reverseStack(): Unit
    {
        // Create auxiliary stack
        var auxiliary: MyStack = MyStack();
        var data: Int ;
        // Executing the loop until when input element are not empty
        while (this.stack.isEmpty() == false)
        {
            // Get the top element of input stack
            data = this.stack.peek();
            // Remove top of current input stack
            this.stack.pop();
            // Add data to auxiliary stack
            auxiliary.push(data);
        }
        // Set auxiliary stack as new stack
        this.stack = auxiliary;
    }
}
fun main(args: Array<String>): Unit
{
    var task: SortStackElement = SortStackElement();
    // Add the stack element
    task.stack.push(1);
    task.stack.push(2);
    task.stack.push(4);
    task.stack.push(5);
    task.stack.push(6);
    task.stack.push(9);
    task.stack.push(11);
    /*
    Before Reverse
    =============
    11  <- Top 
    9  
    6  
    5  
    4  
    2  
    1
    */
    print("\n Before Reverse \n");
    task.printData();
    // reverse operation
    task.reverseStack();
    /*
    After Reverse
    =============
    1  <- Top 
    2  
    4  
    5  
    6  
    9  
    11
    */
    print("\n After Reverse \n");
    task.printData();
}

Output

 Before Reverse
   11   9   6   5   4   2   1

 After Reverse
   1   2   4   5   6   9   11

Time Complexity

The time complexity of the reverseStack function is O(N), where N is the number of elements in the original stack. This is because we need to perform N operations (pop and push) to reverse the stack. Therefore, the overall time complexity of the reversal process is O(N).

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment