Implement Stack in Java using Generic Arrays
Array Based Implementation of Stack in Java
Before talking of stack implementation in Java using array of generics see that stack is a container to which objects are added and removed by following last-in-first-out strategy. To insert objects into and remove from stack a pointer usually called top is maintained that points to last inserted item.
Web browsers do use stack data structure to remember the list of visited sites. Every time when a new web-page is visited its address is added to the stack. The browser then allows visiting the previous page again by clicking on 'back' button.
A stack by definition supports two methods, one method, push for adding objects to the stack, and second, pop for removing the latest added object from the stack. To point the last item, stack uses a special pointer called top. The following methods we plan to implement as part of our stack implementation in Java.
push(): Adds an item to the stack
pop(): Return the top object from the stack, and remove as well.
In addition to push and pop methods we can also define a few supporting but optional methods, such as,
size(): Return the number of objects the stack contains right now.
isEmpty(): Returns true if stack is empty, false otherwise.
getTop(): Return the top object from the stack but does not remove it, return null, if stack is empty.
Implementation of Stack in Java
While implementing stack in Java, there are two choices: one is array based implementation, and second is linked implementation. Here we will implement stack in Java using arrays in object oriented way.
Stack Interface
As Java is an object oriented programming language so we will harness object oriented features of the language during implementation of stack in Java. In order to make end user independent from implementation details of the stack implementation in Java whether it is implemented using array or linked list, we define an interface Stack as follows. The following Stack interface can be assigned any object that implements this interface no matter the underlying implementation uses Array based or linked list based implementation.
/* Stack.java */ public interface Stack <Item> { Item getTop(); // return the top item without removing it from stack Item pop(); // return the top item and removes it from stack void push(Item itm); // adds an item to the stack boolean isEmpty(); // returns true if stack is empty, false otherwise int size(); // returns the number of items in stack right now }
If you look at the above definition of Stack interface, you will see that the interface is passed a parameter Item enclosed in angular brackets. This feature facilitates the generic use of Stack data structure. It allows programmers to pass the object type the stack will store at run time. A special feature of Java called generics brings us this capability. Now define the class ArrayStack that implements Stack interface as follows:
/* ArrayStack.java */ public class ArrayStack <Item> implements Stack <Item> { private Item container[]; private int top; private final static int DEFAULT_SIZE = 10; public ArrayStack () { this(DEFAULT_SIZE); } public ArrayStack (int initSize) { container = (Item[]) new Object [initSize]; top = -1; } public Item getTop() { if (top == -1) return null; return container[top]; } public boolean isEmpty() { return (top == -1); } public Item pop() { if (top == -1) return null; return container[top--]; } public void push(Item itm) { container[++top] = itm; } public int size() { return (top + 1); } }
Let's examine the implementation of ArrayStack class. The very first thing you will notice is that ArrayStack takes a type parameter Item which would be replaced with concrete type by the client code when the ArrayStack object will be created. For example,
Stack <Integer> s = new ArrayStack <Integer>();
Array of Generics in Stack Data Structure
During stack implementation in Java, inside the ArrayStack() constructor you will find that an array of ten items of type Object is being created and then it is casted to generic type Item. Could we have created generics array as container = new Item[10]; rather than the way we implemented in ArrayStack? The answer is NO; Java does not allow generic array creation. Now, you may be interested to know that why does Java not allow creation of generic array? This is left unanswered for your exercise.
Fixed Sized Array and Memory Loitering Issues in Stack Data Structure
You will also notice that inside the ArrayStack() constructor we create container array of 10 objects. In real life situations this stack implementation in Java will soon be failed because you will not be able to place more than 10 elements in stack. This issue will be addressed by resizing array at run time. Java provides a nice mechanism of resizing array at run time, not straightforwardly but you can create another array of bigger size and then assign the newly created array object to the existing reference of previously created array.
A very important aspect of any data structure implementation is that it should use memory very prudently. The above implementation of stack in Java has a hidden flaw, where memory would not be offered to garbage collector for adding it to the free memory pool even after popping an item from the stack. This is because when the item is popped the top pointer of stack data structure is decremented by one but the object still is there in container, though this item would never be accessed again. If a reference to an object that is no longer needed is kept into memory aimlessly, it is called loitering. We can stop loitering by modifying the code of pop() method as follows:
public Item pop() { if (top == -1) return null; Item itm = container[top]; container[top--] = null; // avoid loitering return itm; }
Resizing container Array at Run-time
It is nicer idea to resize container array for stack data structure on run time if it is about to be full, rather than to create a very big array initially. When the container array is resized at run time, it should be sufficiently large to hold all of the existing items plus some free space but, not so large to waste excessive amount of space. To achieve this goal we implement a new method resize() private to ArrayStack. This new method will be declared private because it will be called only by push() and pop() methods of stack data structure. The resize() method goes as follows:
private void resize (int newSize) { Item t[] = (Item[]) new Object[newSize]; for (int i = 0; i <= top; i++) t[i] = container[i]; container = t; }
We will call above method two times, once before pushing an item to stack to check whether there is space to accommodate the new item. And second, after popping an item to check if there is much space left vacant, if so, resize the container to a smaller size. Modified versions of push() and pop() are as follows:
/* Modified versions of push() and pop() */ public Item pop() { if (top == -1) return null; Item itm = container[top]; container[top--] = null; if(top > 0 && top == container.length / 4) resize (container.length/2); return itm; } /*-------------------------------------------*/ public void push(Item itm) { if (top == container.length - 1) resize(2 * container.length); container[++top] = itm; }
By above implementation (resizing container at run time) the ArrayStack will not result into overflow and not become less than one quarter full (except when the stack is empty).
Iterating through Stack Items - Java Program Code
By definition of stack data structure you would use it as a container where items are added to and removed from one end. But, if you like to make the Stack a usual collection where you can iterate through the stack items, you should implement Iterable and Iterator interfaces as part of your ArrayStack implementation.
Java provides a special syntax of for loop (also called for-each loop) to process arrays and iterable collections. Any iterable collection has to implement an iterator() method that returns an Iterator object. And the class implements Iterator has to implement two methods: hasNext() (returns true if there are more items to process, false otherwise) and next() (returns an item from the collection).
To make our Stack data structure iterable, we first extends the Stack<Item> interface by Iterable<Item>. Interface Iterable is already defined as part of java.lang.Iterable. As soon as we extend Stack<Item> interface by Iterable<Item> we have to add a new method iterator() to class ArrayStack that will return an object of type Iterator<Item>
Generally, an iterator is an object of a class that implements hasNext(), and next() as they are declared in Iterator interface. The Iterator interface also declares a remove() method but we will not specify anything in its body.
The interface Iterator<Item> we will implement by an inner class ArrayStackIterator to ArrayStack. To complete the code first modify the existing signature of interface Stack in Stack.java as follows, no change required in interface's body.
public interface Stack <Item> extends Iterable <Item>
Thereafter modifying Stack interface, we need to modify ArrayStack class as follows:
/* ArrayStack.java */ import java.lang.Iterable; import java.util.*; public class ArrayStack <Item> implements Stack <Item> { private Item container[]; private int top; private final static int DEFAULT_SIZE = 10; public ArrayStack () { this(DEFAULT_SIZE); } public ArrayStack (int initSize) { container = (Item[]) new Object [initSize]; top = -1; } public Item getTop() { if (top == -1) return null; return container[top]; } public boolean isEmpty() { return (top == -1); } public Item pop() { if (top == -1) return null; Item itm = container[top]; container[top--] = null; if(top > 0 && top == container.length / 4) resize (container.length/2); return itm; } public void push(Item itm) { if (top == container.length - 1) resize(2 * container.length); container[++top] = itm; } public int size() { return (top + 1); } private void resize (int newSize) { Item t[] = (Item[]) new Object[newSize]; for (int i = 0; i <= top; i++) t[i] = container[i]; container = t; } public Iterator<Item> iterator() { return new ArrayStackIterator(); } private class ArrayStackIterator implements Iterator <Item> { private int i = top; public boolean hasNext() { return (i > -1); } public Item next() { return container[i--]; } public void remove() { // not needed } } }
To test the above implementation define a driver class as follows:
/* ArrayStackDriver.java */ class ArrayStackDriver { public static void main (String a[]) { Stack <Integer> s = new ArrayStack<Integer>(); s.push(20); s.push(30); s.push(40); s.push(50); s.push(60); s.push(70); System.out.println("Size of the stack: " + s.size()); // iterate through stack System.out.println("Following items pushed to Stack as of now:"); for (Integer i : s) System.out.println(i); } } OUTPUT ====== Size of the stack: 6 Following items pushed to Stack as of now: 70 60 50 40 30 20
If you observe the output generated by ArrayStackDriver class, you will find that stack items are processed in reverse order of their insertion. It is because we processed all the items with help of top pointer.
In array implementation of the stack data structure you will not result into overflow after implementing resizing at run time. But you still cannot claim the efficient use of memory. For example, you have an array of 16384 elements, and it runs out of space then you will expand it by double of 16384 that is 32768. Now if you have a few items to store e.g., 10, then space of 16374 elements is occupied by the array aimlessly.
Last Word
In this tutorial we talked of implementation of stack in Java using array of generics. We saw what issues could rise while array based stack implementation in Java. We implemented generic stack in Java using arrays to create a stack of any user defined type. In this implementation of stack in Java we also discussed array resizing, memory loitering, and iteration through stack items. Hope you have enjoyed reading this tutorial. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!
Share this page on WhatsApp