package Stack;
public class DynamicArrayStack {
public int capacity;
public static final int CAPACITY = 16;
public static int MINCAPACITY = 1 << 15;
public int[] stackRep;
public int top = -1;
public DynamicArrayStack(int cap) {
capacity = cap;
stackRep = new int[capacity];
}
public int size() {
return (top + 1);
}
public boolean isEmpty() {
return (top < 0);
}
public void push(int data) {
if (size() == capacity) {
expand();
}
stackRep[++top] = data;
}
public void expand() {
int length = size();
int[] newStack = new int[length << 1];
System.arraycopy(stackRep, 0, newStack, 0, length);
stackRep = newStack;
}
public void shrink() {
int length = top + 1;
if (length <= MINCAPACITY || top << 2 >= length) {
return;
}
length = length + (top << 1);
if (top < MINCAPACITY) {
length = MINCAPACITY;
}
int[] newStack = new int[length];
System.arraycopy(stackRep, 0, newStack, 0, top + 1);
stackRep = newStack;
}
public int top() throws Exception {
if (isEmpty()) {
throw new Exception("Stack is Empty");
}
return stackRep[top];
}
public int peek(){
return stackRep[top];
}
public int pop() throws Exception {
int data;
if (isEmpty()) {
throw new Exception("Stack is empty");
}
data = stackRep[top];
stackRep[top--] = Integer.MIN_VALUE;
return data;
}
public class DynamicArrayStack {
public int capacity;
public static final int CAPACITY = 16;
public static int MINCAPACITY = 1 << 15;
public int[] stackRep;
public int top = -1;
public DynamicArrayStack(int cap) {
capacity = cap;
stackRep = new int[capacity];
}
public int size() {
return (top + 1);
}
public boolean isEmpty() {
return (top < 0);
}
public void push(int data) {
if (size() == capacity) {
expand();
}
stackRep[++top] = data;
}
public void expand() {
int length = size();
int[] newStack = new int[length << 1];
System.arraycopy(stackRep, 0, newStack, 0, length);
stackRep = newStack;
}
public void shrink() {
int length = top + 1;
if (length <= MINCAPACITY || top << 2 >= length) {
return;
}
length = length + (top << 1);
if (top < MINCAPACITY) {
length = MINCAPACITY;
}
int[] newStack = new int[length];
System.arraycopy(stackRep, 0, newStack, 0, top + 1);
stackRep = newStack;
}
public int top() throws Exception {
if (isEmpty()) {
throw new Exception("Stack is Empty");
}
return stackRep[top];
}
public int peek(){
return stackRep[top];
}
public int pop() throws Exception {
int data;
if (isEmpty()) {
throw new Exception("Stack is empty");
}
data = stackRep[top];
stackRep[top--] = Integer.MIN_VALUE;
return data;
}
No comments:
Post a Comment