Do you know, How to reverse a number using stack?

Do you know, How to reverse a number using stack?

Stack  

Given a number, write a program to reverse this number using stack operations like push(), and pop() in Java. For example

Input: 123456

Output: 654321

Input: 900

Output: 9

Lets see simple java program to reverse a number using stack operation 

import java.util.Stack;

public class ReverseNumber {

 public static void main(String[] args) {
  
  int number = 123456;
  
  System.out.println(reverseNum(number));
 }
 
 public static int reverseNum(int number) {
  Stack<Integer> stack = new Stack<Integer>();
  int counter = 1;
  while(number >0) {
   stack.push(number%10);
   number = number/10;
  }
  number = 0;
  while(stack.size() > 0) {
   number = number + (stack.pop() * counter);
   counter *= 10;
  }
  return number;
 }
}

OUTPUT:

654321

Stack implementation using Linked List

Stack implementation using Linked List

Stack using Linked List  

We have seen Stack implementation using array in our earlier tutorials. Now lets see same stack implementation using Linked List and how to push() and pop() values in Stack. Below is the simple example to push() integers into Stack internally having Linked List nodes with total stack size of 10.

class NODE {
 
 NODE link;
 int data;
 
 public NODE() {
 }
 
 public NODE(int data) {
  this.data = data;
 } 
}

public class StackUsingLinkedList {

 NODE root;
 int stackSize = 0;
 int stackLimit = 10;
 
 public static void main(String[] args) {
  
  StackUsingLinkedList obj = new StackUsingLinkedList();
  
  for(int i =0;i<11;i++){
   obj.push(i+10);
  }
  
  for(int i =0;i<11;i++){
   System.out.println(obj.pop());
  }
 }
 
 private int pop(){
  if(stackSize == 0){
   System.out.println("Stack empty ....");
   return -1;   
  }
  NODE tmp = root;
  root = root.link;
  stackSize--;
  return tmp.data;
  
 }
 
 private void push(int val){
  if(stackLimit == stackSize) {
   System.out.println("Stack Full ....");
   return;
  }
  if(root == null){
   root = new NODE(val);
   root.link = null;   
  }else{
   NODE tmp = new NODE(val);
   tmp.link = root;
   root = tmp;
  }
  System.out.println("PUSH ::: "+stackSize + " :: "+val);
  stackSize++;
 }
}

OUTPUT:

PUSH ::: 0 :: 10
PUSH ::: 1 :: 11
PUSH ::: 2 :: 12
PUSH ::: 3 :: 13
PUSH ::: 4 :: 14
PUSH ::: 5 :: 15
PUSH ::: 6 :: 16
PUSH ::: 7 :: 17
PUSH ::: 8 :: 18
PUSH ::: 9 :: 19
Stack Full ....
19
18
17
16
15
14
13
12
11
10
Stack empty ....
-1

Implement Stack in Java

Implement Stack in Java

Stack  

In our earlier tutorial we have seen how to use default Stack class in Java and their methods like push, pop, peek etc., Suppose in any of the interview if interviewer asked us to implement our own Stack class which holds any type of data like Integer, String or even other datatypes. Then we need to go with Generics and need to implement our Stack class.

Lets see simple example to implement Stack using ArrayList and using Generics for holding any datatype.

import java.util.ArrayList;

public class MyStack <E> {

 ArrayList<E> list = null;
 
 public MyStack() {
  list = new ArrayList<E>();
 }
 
 public E push(E val){
  list.add(val);
  return val;
 }
 
 public E pop(){
  E val = list.get(list.size()-1);
  list.remove(list.size()-1);
  return val;
 }
 
 public E peek(){
  E val = list.get(list.size()-1);
  return val;
 }

 public int size(){
  return list.size();
 }
 
 public int search(E val){
  int id = -1;
  if(list.contains(val)){
   id = list.indexOf(val);
  }
  return id;
 }
 
 public boolean empty(){
  if(list.size() == 0) return true;
  else return false;
 }
 
 @Override
 public String toString() {
  return list.toString();
 }
}

Our Stack class is ready and we can test with below code.

public class TestMyStack {

 public static void main(String[] args) {
  
  MyStack<Integer> stack = new MyStack<Integer>();
  
  int stkSize = stack.size();
  System.out.println("STACK SIZE : "+stkSize);
  
  //PUSH
  stack.push(11);
  stack.push(21);
  stack.push(31);
  stack.push(41);
  stack.push(51);
  
  stkSize = stack.size();
  System.out.println("STACK SIZE : "+stkSize);
  
  //STACK
  System.out.println("STACK      : "+stack);
  
  //PEEK
  System.out.println("PEEK       : "+stack.peek());
  
  //POP
  System.out.println("POP        : "+stack.pop());
  
  
  stkSize = stack.size();
  System.out.println("STACK SIZE : "+stkSize);
  
  //PEEK
  System.out.println("PEEK       : "+stack.peek());
  
  //EMPTY
  System.out.println("EMPTY      : "+stack.empty());
  
  //SEARCH
  System.out.println("SEARCH     : "+stack.search(21));
  
  //SEARCH
  System.out.println("SEARCH     : "+stack.search(700));
 }
}

OUTPUT:

STACK SIZE : 0
STACK SIZE : 5
STACK        : [11, 21, 31, 41, 51]
PEEK          : 51
POP            : 51
STACK SIZE : 4
PEEK          : 41
EMPTY        : false
SEARCH      : 1
SEARCH      : -1

Stack class in java

Stack class in java

Stack  

Basically Stack represents last-in-first-out (LIFO) ordering of objects. In Java Stack extends Vector and defines its own five methods along with default methods which allow a vector to be treated as a stack and those methods are

push()
- Pushes the element or object into the stack and it returns the same element. 

pop()
- Removes the first element from the stack and it returns the same element. 
empty()

- Checks whether the stack is empty or not. Returns true if stack is empty else false.

peek()
- Similar to pop(), return first element from the stack but it won't remove the element. 

search()
- Searches for the element from the stack and returns the offset of the element if found else returns -1. 

Lets see simple example in java how to use Stack class.

import java.util.Stack;

public class StackTest {

 public static void main(String[] args) {
  
  Stack<Integer> stack = new Stack<Integer>();
  
  int stkSize = stack.size();
  System.out.println("STACK SIZE : "+stkSize);
  
  //PUSH
  stack.push(11);
  stack.push(21);
  stack.push(31);
  stack.push(41);
  stack.push(51);
  
  stkSize = stack.size();
  System.out.println("STACK SIZE : "+stkSize);
  
  //STACK
  System.out.println("STACK      : "+stack);
  
  //PEEK
  System.out.println("PEEK       : "+stack.peek());
  
  //POP
  System.out.println("POP        : "+stack.pop());
  
  
  stkSize = stack.size();
  System.out.println("STACK SIZE : "+stkSize);
  
  //PEEK
  System.out.println("PEEK       : "+stack.peek());
  
  //EMPTY
  System.out.println("EMPTY      : "+stack.empty());
  
  //SEARCH
  System.out.println("SEARCH     : "+stack.search(21));
  
  //SEARCH
  System.out.println("SEARCH     : "+stack.search(700));
 } 
}

OUTPUT:

STACK SIZE  : 0
STACK SIZE  : 5
STACK         : [11, 21, 31, 41, 51]
PEEK           : 51
POP            : 51
STACK SIZE : 4
PEEK          : 41
EMPTY        : false
SEARCH      : 3
SEARCH      : -1

Heap and Stack in Java

Heap and Stack in Java

Stack  

We are discussing few interview questions from our earlier tutorials and its a follow-up with same interview questions in Java. Questions are 

How memory managed in java? 
What is Heap and Stack memory? 
What will be stored in Heap and Stack?
Determine the size of Heap and Stack?
Stack vs Heap Pros and Cons?
When to use Heap and Stack?

This is one of the important questions which asked in most of the Java interviews and later interviewer may jump into asking question in Operating System(OS) level memory management also. Lets see above questions one by one and finally its a simple programs where we all can discuss about the memory allocated for it in Java.

How memory managed in Java?
Stack and Heap are the memories allocated by OS to JVM and they both are stored in the computer's RAM (Random Access Memory). 

What is Heap and Stack memory?
Stack:
It's a special region of computer's memory that stores temporary variables created by each functions. Stack uses "FILO" (First In Last Out) data structure, where its managed and optimized by CPU closely.

Heap:
Heap is a region of computer's memory that is not managed automatically by programmer, and is not as tightly managed by the CPU. It is a more free-floating region of memory.


What will be stored in Heap and Stack memory?
Stack:
Methods and the local variables are stored in stack. Also it is to be remembered that the variable references primitive or object references will be stored in Stack.  

Heap:
Objects and its instance variable are stored in Heap. In Java 6 due to "escape analysis" optimization, sometimes objects will be stores in Stack also.


Determine the size of Heap and Stack?
Stack:
Stack is usually pre-allocated and limited in size, because by definition it must be contiguous memory. Also depends on the language, compiler, operating system and architecture. 

Heap:
In general Heap will be dynamically allocated and constantly changing in size. 


Stack vs Heap Pros and Cons?
Stack:
Very fast in access.
Explicitly can't de-allocate variables allocated in Stack.
Memory fragmentation will not happen in Stack, since its managed efficiently by CPU.
Stack size is limited depending on OS.
If Stack runs out of memory, then this leeds to stack overflow could cause program to crash.

Heap:
Slower in access compared to Stack.
No limited on memory size which will be dynamically allocated. 
Heap could cause fragmentation problem, which occurs when memory on the heap is being stored as non-contiguous blocks. 

When to use Heap and Stack?
Its better to choice Stack when we use less memory or small amount of data in usage. Suppose if we don't know about the size or application uses large amount of memory like dynamic array or collections then we need to go for Heap. 


Lets discuss:

public class MyProgram {
 
 private static int value = 10;
 private String str = new String("Java Discover");
 private String name = "Heap and Stack";
 
 public void sayHello(){
  System.out.println("Hello, Java Discover !!!");
 }
 
 public static void main(String[] args) {
  
  String country = "India";
  
  MyProgram obj1;
  
  MyProgram obj2 = new MyProgram();
  obj2.sayHello();
 }
}

Lets comment on the memory usage on above program as what will be stored in Stack and Heap?