Feb 14, 2015

Reverse elements of a stack using stack operations and without using any extra space (In place)

Problem statement:- Given a stack filled with elements, write a program to reverse the elements of stack without using any extra space.

Algorithm:-

1. Do pop() operation and recursively call the same method until stack is empty and keep track of popped elements.
2. While returning from recursive method call, push popped elements in the stack and call method recursively to add elements at the bottom.
3. Since, stack follows LIFO protocol and so last popped element is push back in stack it bubble up to top of stack and elements of stack gets reversed.

Below is the sample code which reverse elements of linked list:- 
/* Recursive method to reverse elements of stack */
public void reverseStackElemetsWithStackOperations(CustomStack stack) {
if (stack.isEmplty()) {
return;
}
int temp = stack.pop();
/* call recursively to reach at bottom of stack */
reverseStackElemetsWithStackOperations(stack);
/* Call another recursive method to bubble up the bottom elements */
pushElementAtBottom(stack, temp);
}

/* Recursive call to this method - to bubble up the bottom most element to top*/
private void pushElementAtBottom(CustomStack stack, int data) {
if (stack.isEmplty()) {
stack.push(data);
return;
}
int temp = stack.pop();
/* recursive call with data to be inserted */
pushElementAtBottom(stack, data);
stack.push(temp);
}

Complete sample program to reverse elements of a stack without using any extra space and just stack operations:-

package com.devinline.stacks;

import com.devinline.stacks.SinglyLinkedListCustom.Node;

public class ReverseStackElements {
CustomStack stack;

public ReverseStackElements() {
stack = new CustomStack();
}

/* Recursive method to reverse elements of stack */
public void reverseStackElemetsWithStackOperations(CustomStack stack) {
if (stack.isEmplty()) {
return;
}
int temp = stack.pop();
/* call recursively to reach at bottom of stack */
reverseStackElemetsWithStackOperations(stack);
/* Call another recursive method to bubble up the bottom elements */
pushElementAtBottom(stack, temp);
}

/*
* Recursive call to this method - to bubble up the bottom most element to
* top
*/
private void pushElementAtBottom(CustomStack stack, int data) {
if (stack.isEmplty()) {
stack.push(data);
return;
}
int temp = stack.pop();
/* recursive call with data to be inserted */
pushElementAtBottom(stack, data);
stack.push(temp);
}

public static void main(String[] args) {
CustomStack stack = new CustomStack();
stack.push(20);
stack.push(21);
stack.push(24);
stack.push(40);
stack.push(111);
stack.push(784);
System.out.println("Stack before reversing its elements "
+ stack.toString());
new ReverseStackElements()
.reverseStackElemetsWithStackOperations(stack);
System.out.println("Stack after reversing its elements "
+ stack.toString());
}
}

class SinglyLinkedListCustom {
Node head = null;

public static Node createNewNode(int data) {
return new SinglyLinkedListCustom().new Node(data);
}

/* get first element */
public Node getFistNode() {
if (head == null)
return null;
else
return head;
}

/* Delete First node,return new head */
public Node deleteFirstNode() {
if (head == null)
return null;
Node temp = head.next;
Node delNode = head;
head.next = null;// garbage collected
head = temp;
return delNode;
}

/* Display data of nodes/iterate linked list */
public String iterateLinkedList() {
StringBuffer sbf = new StringBuffer();
Node current = head;
if (head != null) {
sbf.append("[");
while (current != null) {
sbf.append(current.data + " ");
current = current.next;
}
sbf.append(" ]");
} else {
System.out.println("Linked list is empty.");
}
return sbf.toString();

}

/* Add New node at start of linked list */
public void insertFirst(int data) {
Node newNode = createNewNode(data);
if (head == null) {
head = newNode;
} else {
newNode.next = head;
head = newNode;
}
}

class Node {
public int data;
public Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

}

class CustomStack {
Node node = null;
int top = -1;
SinglyLinkedListCustom list;

public CustomStack() {
createStack();
}

void createStack() {
top = -1;
list = new SinglyLinkedListCustom();
}

int pop() {
if (list.getFistNode() != null) {
top--;
return list.deleteFirstNode().data;
} else
return -1;
}

void push(int data) {
list.insertFirst(data);
++top;
}

int peek() {
return list.getFistNode().data;
}

boolean isEmplty() {
return (top == -1) ? true : false;
}

public String toString() {
return list.iterateLinkedList();
}

public int getSize() {
return top + 1;
}
}

============Sample output===============
Stack before reversing its elements [784 111 40 24 21 20 ]
Stack after reversing its elements [20 21 24 40 111 784 ] ======================================
Location: Hyderabad, Telangana, India