Fading Coder

One Final Commit for the Last Sprint

Home > Tech > Content

Array-Based Stack Implementation in Java

Tech 1

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

Related Articles

Understanding Strong and Weak References in Java

Strong References Strong reference are the most prevalent type of object referencing in Java. When an object has a strong reference pointing to it, the garbage collector will not reclaim its memory. F...

Comprehensive Guide to SSTI Explained with Payload Bypass Techniques

Introduction Server-Side Template Injection (SSTI) is a vulnerability in web applications where user input is improper handled within the template engine and executed on the server. This exploit can r...

Implement Image Upload Functionality for Django Integrated TinyMCE Editor

Django’s Admin panel is highly user-friendly, and pairing it with TinyMCE, an effective rich text editor, simplifies content management significantly. Combining the two is particular useful for bloggi...

Leave a Comment

Anonymous

◎Feel free to join the discussion and share your thoughts.