Thursday, 15 November 2018

how to implement stack using dynamic array


public class StackWithArray {

private int capacity = 2;
private int stack[] = new int[capacity];
private int top = 0;

public void push(int data) {

if (size() == capacity)
expand();

stack[top] = data;
top++;

}

private void expand() {
int length = size();

int[] newStack = new int[capacity * 2];
System.arraycopy(stack, 0, newStack, 0, length);
stack = newStack;
capacity *= 2;

}

private int size() {
return top;
}

public int pop() {
int data = 0;
if (isEmpty()) {
System.out.println("stack is empty");
} else {
top--;
data = stack[top];
stack[top] = 0;
shrink();

}
return data;
}

public int peek() {
int data;
data = stack[top - 1];
return data;

}

private void shrink() {
int length = size();
if (length <= (capacity / 2) / 2)
capacity = capacity / 2;

int newStack[] = new int[capacity];
System.arraycopy(stack, 0, newStack, 0, length);
stack = newStack;
}

public boolean isEmpty() {
return top <= 0;
}

public void displayData() {
for (int n : stack) {
System.out.print(n + " ");
}
System.out.println();

}

public static void main(String[] args) {

StackWithArray st = new StackWithArray();
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
st.pop();
st.displayData();
st.pop();
st.displayData();
st.pop();
st.displayData();
st.pop();
st.displayData();

}

}

No comments:

Post a Comment