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

We can grow the array by doubling it size, and copying the elements in older array to newer one.

Here is how:

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:

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

Time complexity

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

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

O(1) in any case

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

Resizing array vs linked list

Thanks.

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 implementation | Resizing array implementation |
---|---|

Every operation takes constant time in worst case | Every operation takes constant amortized time |

Extra space and time as we have to deal with links | Less wasted space |

Thanks.

## 0 comments:

## Post a Comment