Home Misc Given a stack, how will you reverse it using only stack operations PUSH and POP?

Given a stack, how will you reverse it using only stack operations PUSH and POP?

by nikoo28
0 comment

Question: You are given a stack and you have to reverse it, using only stack operations push and pop.

The algorithm for the above problem can be given in this way:-

  • First POP all elements of the stack till it becomes empty
  • Now for each upward step in the recursion, push the elements at the bottom of the stack.
void reverseStack(struct stackNode * top)
{
	int data;

	if(isStackEmpty(top))
		return;

	//get the top data
	data = POP(top);

	//recursive call for the next top element
	reverseStack(top);

	//after the recursion ends, we need to insert the numbers at the Bottom
	insertAtBottom(top, data);
}

void insertAtBottom(struct stackNode * top, int data)
{
	int temp;

	//check for terminating condition of recursive call
	if(isStackEmpty(top))
	{
		//when the stack is empty, just add the data
		//this will be the last data of original stack
		top = push(top,data);
		return;
	}

	//again we get the top elements one by one
	temp = POP(top);

	//a recursive call
	insertAtBottom(top, data);

	top = push(top, temp);
}

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More