Tuesday, September 10, 2013

Resizing Array implementation of stack

We have already seen the array implementation of stack, which had one limitation of what happens if data size is bigger than array size, i.e. over flow occurs. To solve this we have to grow our array. But how?

Growing the Array
Approach 1 - Repeated Doubling i.e. Doubling the array every time it is full
We can grow the array by doubling it size, and copying the elements in older array to newer one.
Here is how:
public class ResizingArrayStackOfString {
 String[] s;
 int N;
 public ResizingArrayStackOfString()
 {
  s = new String[1];
 }
 
 public void push(String item)
 {
  if(N==s.length)
   resize(2*s.length);
  s[N++] = item;
 }
 public void resize(int capacity)
 {
  String[] copy = new String[capacity];
  for (int i=0;i<N;i++)
   copy[i]=s[i];
  s = copy;
  
 }
}

Resizing of array takes O(n) time extra, for n elements already inserted.

Shrinking the array
How to shrink the array? Can repeated halving work here. Answer is no.
Suppose the array size is almost full, so we double the array, and again due to some reason stack shrinked, and we shrinked the array by 2, and again only few elements are added such that stack again is full, and again we have to double. So, we have to do it again and again.
    But if we shrink the array size by 4, then atleast we dont have to worry again and again for array size.
Here is how:
 public String pop()
 {
  String item = s[--N];
  s[N] = null;
  if(N>0 && N==s.length/4)
   resize(s.length/2);
  return item;
 }

So we have to make sure that array is between 25% to 100% full.

Time complexity
Push
best case - O(1), worst case - O(N), amortized - O(1)

Pop
best case - O(1), worst case - O(N), amortized - O(1)

size 
O(1) in any case

Memory usage in java
Size varies between 8N to 32N bytes for N elements in stack.

Resizing array vs linked list
Linked list implementationResizing array implementation
Every operation takes constant time in worst caseEvery operation takes constant amortized time
Extra space and time as we have to deal with linksLess wasted space

Thanks.

0 comments:

Post a Comment