How To Implement Stack Inwards Coffee Using Array In Addition To Generics - Example

The stack is 1 of the pop information construction which supports LIFO (Last In First OUT) operation. Due to LIFO advantage, yous tin travel stack information construction to convert a recursive algorithm to an iterative one. Stack data construction is real tardily to implement using an array or linked list, but yous don't receive got to implement it past times your ain because Java already provides a Stack implementation in java.util.Stack class. This course of educational activity is a subclass of the Vector course of educational activity too yous should travel it whenever yous demand Stack for your production code, at that topographic point is no signal inventing the cycle in 1 lawsuit again when the focus is on developing your application. At the same time, equally a programmer too coder, yous should also know how to implement your ain stack past times using a basic information construction similar an array or linked list.

It's real of import for a programmer to acquire how to implement diverse information construction inward his favorite programming linguistic communication e.g. binary search tree, linked list, Stack, or Queue. They are also pop coding interview query too yous may come across them when yous to your side past times side project interview.

Here nosotros are implementing Stack inward Java solely from a coding interview perspective, if yous ever demand to travel a Stack inward your real-world Java application yous should travel the 1 from java.util parcel or from some 3rd political party library e.g. GS collection, FastUtil or Trove. They render the high-performance implementation of diverse collection classes inward Java.

How to implement Stack inward Java using array

Stack has next interface too supports operations similar push(), pop(), contains(), clear() too size(). The pop() method volition ever render the in conclusion chemical constituent added.

Since Java provides Generics to ensure type-safety, it's recommended to travel Generics whenever yous write a container course of educational activity i.e. a course of educational activity which holds objects of other classes e.g. this Stack course of educational activity which tin concur whatever type of object similar String or Integer etc. While using this course of educational activity yous exactly demand to say the course of educational activity that which sort of object volition travel stored too the compiler volition ensure that no other type of object volition travel stored inward this stack.

I receive got used Generics hither to present how yous tin write type-safe classes inward Java, but if yous demand a refresher yous tin read this article earlier trying the code instance given inward this article.

Now, let's come upwards to the crux of this example, the logic yous demand to build unopen to array to implement diverse Stack operations e.g. push, pop, contains, size, isEmpty, too clear. Since nosotros are using array information construction to implement Stack, nosotros volition travel an array to shop all elements. Since the size of the array needs to travel declared at the fourth dimension of creating the array, we'll travel a default capacity of 10. The user tin also do Stack of whatever capacity past times providing value inward the constructor.


One of the key divergence betwixt array too Stack, the quondam is a static information construction where size cannot travel changed in 1 lawsuit declared but Stack is a dynamic information structure, it tin resize itself, but nosotros are non implementing the same resize logic hither to decease along the programme simple. You tin banking concern jibe the code of Stack.java to see how it resize itself. It uses ensureCapacity() method to do a novel array alongside 1.5 capacity when threshold is breached, similar to the load factor of HashMap. After creating a novel array, it exactly copies content from the old array to novel array.

Coming dorsum to the implementation of Stack, the size(), clear() too isEmpty() implementation is direct forward. We decease along a variable size, which is incremented when an chemical constituent is added i.e. pushed into Stack too decrement it when an chemical constituent is removed i.e. popped from Stack. The value of size variable is returned past times the size() method too it shows how many elements are introduce inward Stack.

Many programmers brand a error hither past times returning the length of the array, which is wrong because the length of the array is genuinely the capacity of Stack. The stack could travel total or empty. So don't render the length of the array from size() method. Similarly, the isEmpty() method volition render true if size is zero.

The implementation of the clear() method is a trivial fleck tricky, some programmer brand the container array equally nada but clear is supposed to clearn the Stack, so that nosotros tin reuse the same array. So instead of exactly declaring array = null, yous should iterate over the array until the size too grade every chemical constituent equally null. You don't demand to iterate the array until length, exactly iterating until the size is plenty because remainder of the elements are already null.

Now, let's implement 2 of the most of import operations from the array, the push() too pop() operation. The offset thing, push() method does is it checks if Stack is total or not. If Stack is total i.e. size == length so it resizes the stack past times creating some other array of 1.5 times of master copy size too copying the content of old array into a novel array. I receive got used Arrays.copyOf() method to trim down the size of the array. This method copies the specified array, truncating or padding alongside nulls (if necessary) so the re-create has the specified length.

If nosotros receive got space, so nosotros exactly shop the chemical constituent inward the electrical flow index too increases the size. It's worth checking the clever travel of the postfix ++ operator here, which offset shop the chemical constituent at electrical flow slot too so increment the value. So, at the start, size is 0 so the offset chemical constituent volition travel stored at 0th index inward array too size volition decease 1.

On the other hand, the pop() functioning offset checks if the array is empty, if it is empty so it render null, otherwise it offset reduces the size too so render the value from the top of the stack i.e. electrical flow index. Instead of using postfix operator, hither I receive got used prefix -- operator because size is ever 1 to a greater extent than than the electrical flow index of the array. For example, if at that topographic point is 1 chemical constituent inward the array so size is 1 but the index of the chemical constituent is 0, so nosotros offset trim down the size too so retrieve the value from the array.

One of the key things yous should travel aware hither is of retentiveness leak caused past times keeping a reference of already popped out elements inward Stack equally shown inward Effective Java. To forestall that nosotros are assigning nada to the electrical flow slot inward the array e.g. array[size] == null. This volition ensure that array is non keeping whatever reference to the object too if that is solely referenced so object is right away eligible for garbage collection.

One to a greater extent than affair yous tin do inward the pop() method is to trim down the size of the array if it's besides big. We trim down the size of the array if it is larger than the capacity but decease along it 1.5 times of size to render plenty headroom for growth.

Finally, yous tin implement the contains() method past times doing a linear search inward Java. This method should render truthful if an chemical constituent passed to this method exists inward the Stack otherwise false. It only iterates through the array using enhanced for loop too compares each chemical constituent of Stack to the given object, if they equal using equals() method so it returns true.

Java Program to implement Generic Stack using Array

Here is 1 instance of implementing Stack using an array inward Java. In our example, nosotros receive got iii classes, first, the interface IStack to define functioning supported past times Stack implementation, minute the ArrayStack which implements this interface too back upwards all functioning past times storing elements inward array, too third, the StackDemo class, which is our examine course of educational activity to demonstrate how yous tin travel this Stack course of educational activity inward your Java program.

You tin salvage these classes inward split upwards files e.g. IStack.java, ArrayStack.java, and StackDemo.java or yous tin combine them inward 1 course of educational activity equally I receive got done. Just retrieve that when yous shop them inward split upwards files, the advert of the file must travel same equally the advert of the populace class.

StackDemo.java

import java.util.Arrays;  /**  * Java programme to examine our Stack implementation. In this programme  * nosotros add together dyad of elements too so impress the Stack.  *  * @author Javin Paul  */ public class StackDemo {      public static void main(String[] args) {         IStack<Integer> stackOfInteger = new ArrayStack<>();         stackOfInteger.push(10);         stackOfInteger.push(20);          System.out.println("Stack of Integers : " + stackOfInteger);     } }

beck.java

/**  * An interface to stand upwards for Stack information structure. We demand to advert it to  * something other than Stack because at that topographic point is already a course of educational activity named Stack inward  * java.util package.  *   * @author WINDOWS 8  *  * @param <T>  */ interface IStack<T> {     public boolean push(T value);      public T pop();      public boolean contains(T value);      public int size();      public void clear();      public boolean isEmpty();  }

ArrayStack.java

/**  * An implementation of Stack inward Java using array. This course of educational activity is generic,  * so yous tin do Stack of Integer or Stack of String.  *   * @author WINDOWS 8  *  * @param <T>  */ class ArrayStack<T> implements IStack<T> {      private static terminal int DEFAULT_CAPACITY = 10;     private T[] store;     private int size = 0;     private int capacity;      @SuppressWarnings("unchecked")     public ArrayStack() {         this.capacity = DEFAULT_CAPACITY;         shop = (T[]) new Object[DEFAULT_CAPACITY];     }      @SuppressWarnings("unchecked")     public ArrayStack(int capacity) {         this.capacity = capacity;         shop = (T[]) new Object[capacity];     }      @Override     public boolean push(T value) {         if (this.size >= store.length) {             int newSize = size + (size >> 1);             shop = Arrays.copyOf(store, newSize);         }          // non solely shop value inward Stack but also         // increases size of the array, a practiced use         // ++ operator which ensures that first         // yous shop at electrical flow index too than         // increment size.          store[size++] = value;         return true;     }      @Override     public T pop() {         if (size <= 0) {             return null;         }          // in 1 lawsuit again offset nosotros are reducing size too so getting value         // from Stack, because size is ever 1 to a greater extent than array index         // because index starts at 0. So if yous receive got exactly one         // chemical constituent inward Stack, so valid index is null but size         // would travel one.         T value = store[--size];          // brand certain yous dereference chemical constituent at top of the stack         // to forestall retentiveness leak inward Java         store[size] = null;          // shrinking array if its besides big         int reducedSize = size;         if (size >= capacity && size < (reducedSize + (reducedSize << 1))) {             System.arraycopy(store, 0, store, 0, size);         }         return value;     }      @Override     public boolean contains(T value) {         // banking concern jibe for an chemical constituent inward array using         // sequential search algorithm         boolean constitute = false;         for (int i = 0; i < size; i++) {             T chemical constituent = store[i];             if (element.equals(value)) {                 constitute = true;             }         }          return found;     }      @Override     public int size() {         return size;     }      @Override     public void clear() {         // brand certain yous unloosen reference of all         // chemical constituent to avoid retentiveness leak inward Java         for (int i = 0; i < size; i++) {             store[i] = null;         }         size = 0;     }      @Override     public boolean isEmpty() {         return size == 0;     }      /**      * returns String persuasion of Stack, fist chemical constituent      * is the top of stack      */     @Override     public String toString() {         StringBuilder sb = new StringBuilder();         sb.append("[");         for (int i = size - 1; i >= 0; i--) {             sb.append(this.pop());              if (i > 0) {                 sb.append(",");             }         }         sb.append("]");          return sb.toString();     } }  Output: Stack of Integers : [20,10]

JUnit tests for testing Stack information construction inward Java

Now, let's examine our Stack implementation past times writing some unit of measurement examine using JUnit. Well, I did write them earlier writing code, exactly because I follow examine driven evolution sometimes, but it's your choice. You are ever costless to add together to a greater extent than unit of measurement tests to encompass to a greater extent than scenarios. If yous are non familiar alongside examine driven evolution inward Java, I advise reading Test Driven: TDD too Acceptance TDD for Java developers, 1 of my favorite mass on this topic.

Let me know if yous discovery whatever põrnikas on this Stack implementation using an array.

import static org.junit.Assert.*;  import org.junit.Test;  public class StackTest {      @Test     public void size() {         IStack<Integer> myStack = new ArrayStack<Integer>();         assertTrue(myStack.size() == 0);          myStack.push(1);         assertEquals(1, myStack.size());     }      @Test     public void isEmpty() {         IStack<Integer> newStack = new ArrayStack<Integer>();         assertTrue(newStack.isEmpty());          newStack.push(2);         assertFalse(newStack.isEmpty());          newStack.pop();         assertTrue(newStack.isEmpty());     }      @Test     public void clear() {         IStack<Integer> aStack = new ArrayStack<Integer>();         assertTrue(aStack.isEmpty());          aStack.push(2);         assertFalse(aStack.isEmpty());          aStack.clear();         assertTrue(aStack.isEmpty());     }      @Test     public void pushAndPop() {         IStack<String> bStack = new ArrayStack<String>();         assertEquals(0, bStack.size());                  bStack.push("one");         assertEquals(1, bStack.size());         bStack.push("two");         assertEquals(2, bStack.size());                  assertEquals("two", bStack.pop());         assertEquals("one", bStack.pop());         assertEquals(0, bStack.size());     } }

That's all virtually how to implement Stack information construction inward Java using Array. It's also a practiced instance to amend your coding science because implementing primal too advanced information construction inward Java is non a trivial exercise, they brand yous mean value too also challenge your coding technique. You tin non solely acquire virtually information construction too algorithm but also prepare the coding feel which is the biggest forcefulness of a programmer. If yous desire to acquire to a greater extent than virtually Stack too other information structure, I advise yous reading Introduction to Algorithms past times Thomas H. Cormen. It contains a wealth of information virtually essential information structures, which yous won't discovery anywhere.

Further Learning
Data Structures too Algorithms: Deep Dive Using Java
answer)

How to discovery if a singly linked listing contains a loop? (solution)

How to contrary linked listing inward Java? (tutorial)

How to discovery the offset too in conclusion chemical constituent of linked listing inward Java? (solution)

How to take duplicate elements from the array inward Java? (tutorial)

How to discovery middle chemical constituent of linked listing inward 1 pass? (solution)

How to contrary an array inward house inward Java? (tutorial)

How to search chemical constituent within linked listing inward Java? (solution)

What is the divergence betwixt LinkedList too ArrayList inward Java? (answer)

How to implement pre-order traversal of a binary tree using iteration too recursion? (solution)

How to implement post-order traversal inward Java? (solution)

How to impress all leafage nodes of a binary tree inward Java? (solution)

How to discovery all pairs inward given array whose amount is equal to given number? (solution)

Thanks for reading this article. If yous similar this article so delight part alongside your friends too colleagues. If yous receive got whatever questions, feedback, or proffer so delight drib a comment too I'll endeavour to reply it. 

Share this post