Array-Based Stack Implementation in Java
A stack operates on the Last-In-First-Out (LIFO) principle, resembling a container where the most recently added element is the first to be removed.
public class FixedSizeStack {
private final int capacityLimit;
private int topIndex;
private final int[] storage;
public FixedSizeStack(int limit) {
this.capacityLimit = limit;
this.topIndex = -1;
this.storage = new int[limit];
}
public void insert(int value) {
if (topIndex >= capacityLimit - 1) {
throw new IllegalStateException("Storage capacity exceeded");
}
storage[++topIndex] = value;
}
public int remove() {
if (isEmpty()) {
throw new IllegalStateException("No elements present");
}
return storage[topIndex--];
}
public int getTop() {
if (isEmpty()) {
throw new IllegalStateException("No elements present");
}
return storage[topIndex];
}
public boolean isEmpty() {
return topIndex < 0;
}
public int getElementCount() {
return topIndex + 1;
}
}
public class StackDemo {
public static void main(String[] args) {
FixedSizeStack myStack = new FixedSizeStack(10);
myStack.insert(10);
myStack.insert(20);
myStack.insert(30);
System.out.println("Current Top: " + myStack.getTop()); // 30
System.out.println("Total Elements: " + myStack.getElementCount()); // 3
System.out.println("Removed: " + myStack.remove()); // 30
System.out.println("New Top: " + myStack.getTop()); // 20
System.out.println("Remaining Elements: " + myStack.getElementCount()); // 2
}
}
For scenarios where the maximum size is unpredictable, a dynamic resizing mechanism can be introduced:
public class ResizableStack {
private int headPointer;
private int currentCapacity;
private int[] internalArray;
public ResizableStack() {
this.currentCapacity = 10;
this.headPointer = -1;
this.internalArray = new int[currentCapacity];
}
public void add(int item) {
if (headPointer + 1 >= currentCapacity) {
expandCapacity();
}
internalArray[++headPointer] = item;
}
public int fetch() {
if (hasData()) {
return internalArray[headPointer--];
}
throw new IllegalStateException("Container is empty");
}
public boolean hasData() {
return headPointer != -1;
}
private void expandCapacity() {
this.currentCapacity *= 2;
int[] expandedArray = new int[currentCapacity];
System.arraycopy(internalArray, 0, expandedArray, 0, internalArray.length);
this.internalArray = expandedArray;
}
}
When the maximum threshold is reached, the internal storage expands to twice its original size. This expansion mechanism involves allocating a new, larger array and transferring all existing elements into it using System.arraycopy(internalArray, 0, expandedArray, 0, internalArray.length);.
In Java, System.arraycopy serves as a high-performance method for copying arrays. It is typically implemanted as a native method within the JVM, leveraging underlying operating system or hardware instructions to opitmize the copying process.
Since the JVM core is largely written in C/C++, the actual implementation relies on native code. Below is a simplified representation of the JVM antry point for this method, showing how it distinguishes between primitive and object arrays for efficient cloning:
JVM_ENTRY(void, JVM_SystemArraycopy(JNIEnv* env, jclass ignored, jobject src, jint src_pos, jobject dest, jint dest_pos, jint length))
// omitted checks...
if (src->is_primitive_array() && dest->is_primitive_array()) {
arraycopy_unchecked(src, src_pos, dest, dest_pos, length, CHECK);
} else {
arraycopy_unchecked_objArray(src, src_pos, dest, dest_pos, length, CHECK);
}
JVM_END