Background:
As we know array is used to store data in sequential manner in memory. Here accessing of elements is based on array index. But in case of Stack accessing of elements is not based on index it is based on last inserted value.
So to implement stack using array we need a wrapper class around the array which will implement stack operation using array as storage medium.
Strategy:
We need following instance variables and methods in wrapper class StackUsingArray to implement the Stack.
1. top pointer - It will always point to the last inserted element in the array.
2. size - Since array is a static data type so it is required to have size variable of array to check overflow condition of the stack.
3. push() - This operation will add elements in the array fulfilling all the constraints of the stack.
4. pop() - This operation will fetch and remove an element from the stack pointed by the top pointer fulfilling all the constraints of stack.
5. peek() - This operation will fetch an element from the stack pointed by the top pointer fulfilling all the constraints of stack.
6. getSize() - It will return number of elements present in the stack.
7. isEmpty() - It will return true if the stack is empty otherwise false.
8. isFull()- It will return true if the stack is full otherwise false.
9. storage - This is the array which will store all the elements of the stack.
Below is the class diagram for the implementation of the stack mentioned above:
Here we are going to write algorithm for all operations of stack mentioned in above diagram.
push( item )- Below is the algorithm for push() operation.
push(item)
{
1. if (top < size-1)
2. top++
3. storage[top]=item
4. else
5. throw exception "Stack overflow"
}
pop( item )- Conceptually pop() operation fetches the element pointed by top pointer and removes it from the stack. Since array is static data type where physical removal is not allowed. If we use alternate methods for removal it is very costly. So here we just ignore the element(making them garbage for future use) which is popped by decrementing top pointer. Below is algorithm for pop() operation.
pop():item
{
1. if (top ==-1)
2. throw exception "Stack is Empty"
3. else
5. return storage[top]
6. top--
}
peek()- It returns the item pointed by head pointer.
peek():item
{
1. if (top ==-1)
2. throw exception "Stack is Empty"
3. else
5. return storage[top]
}
getSize() - Using top pointer size of stack is also known because top pointer always points to the index of last inserted element. So size of stack=top+1. Below is the implementation of getSize() method.
getSize()
{
return top+1;
}
isEmpty() - Below is the implementation of isEmpty() method.
isEmpty()
{
return top==-1;
}
isFull()- Below is the implementation of isFull() method.
isFull()
{
return top==size-1;
}
Below is the java code implementation of above discussed algorithms
import java.io.*;
import java.util.Stack;
public class StackUsingArrayTest {
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
StackUsingArray<String> strStack=new StackUsingArray<String>(5);
strStack.push("Ram");
strStack.push("Shyam");
strStack.push("Meena");
strStack.push("Alfred");
System.out.println("Stack size="+strStack.getSize());
System.out.println("is Stack empty="+strStack.isEmpty());
System.out.println("============================================");
System.out.println("Peek element is="+strStack.peek());
System.out.println("1st Poped element is="+strStack.pop());
System.out.println("2nd Poped element is="+strStack.pop());
System.out.println("3rd Poped element is="+strStack.pop());
System.out.println("Stack size="+strStack.getSize());
System.out.println("is Stack empty="+strStack.isEmpty());
System.out.println("4th Poped element is="+strStack.pop());
System.out.println("is Stack empty="+strStack.isEmpty());
}
}
class StackUsingArray<T>
{
private int size;
private int top;
private T[] storage;
public StackUsingArray(int size)
{
this.size=size;
storage=(T[]) new Object[size];
top=-1;
}
public boolean push(T item) throws Exception
{
if(top<size-1)
{
top++;
storage[top]=item;
}
else
{
throw new Exception("Stack Overflow");
}
return true;
}
public T pop() throws Exception
{
T item;
if(top>=0)
{
item= storage[top];
top--;
}
else
{
throw new Exception("Stack Underflow");
}
return item;
}
public T peek() throws Exception
{
T item;
if(top>=0)
{
item= storage[top];
}
else
{
throw new Exception("Stack Underflow");
}
return item;
}
public int getSize()
{
return top+1;
}
public boolean isEmpty()
{
return top==-1;
}
public boolean isFull()
{
return top==size-1;
}
}
