Stack Using Array Resizing - Coursera Algorithms

When implementing stacks using arrays, we may run into overflow and underflow problems. We can resize the array on need basis by doubling the array in push op when the array has reached it's limit and by halving the array in pop op when the array is just 25% utilized. 

This will result in constant amortized time operations, but ~N in worst case.

Linked list on the other hand has constant time even in worst case. But still, linked list may take more time and memory because of the links. 

If occasional slow ops are bearable, then arrays would be a better option than linked lists. 

Following is the complete program:

	package stacks;
	public class StackResizeArray {
	String[] stack;
	int index=0;
	public StackResizeArray(int cap) {
	stack = new String[cap];
	}
	public void push(String s) {
	int l = stack.length;
	if(index==l) {//full array-double size
	resize(2*l);
	}
	stack[index++] = s;
	}
	public int size() {
	return index;
	}
	public int length() {
	return stack.length;
	}
	public boolean isEmpty() {
	return (index==0);
	}
	public String pop() {
	if(isEmpty()) {
	System.out.println("stack empty");
	return "";
	}
	int l = stack.length;
	if(index<=l/4) {//25% of array is filled-half the array
	resize(l/2);
	}
	String s = stack[--index];
	stack[index] = null;
	return s;
	}
	public void print() {
	System.out.println("============================");
	for(int i=0;i<index;i++) {
	System.out.println(stack[i]);
	}
	}
	public void resize(int cap) {
	String copy[] = new String[cap];
	for(int i=0;i<index;i++) {
	copy[i]=stack[i];
	}
	stack = copy;
	}
	public static void main(String[] args) {
	StackResizeArray stack = new StackResizeArray(5);
	stack.push("to");
	stack.push("be");
	stack.push("or");
	stack.push("not");
	stack.push("to");
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.push("be");
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.print();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	stack.pop();
	stack.print();
	System.out.println("stack util is "+stack.size()+" out of "+stack.length());
	}
	}

view raw StackResizeArray.java hosted with ❤ by GitHub

Related Posts:  

Stack Using Linked List - Coursera Algorithms

Stack Using Array - Coursera Algorithms