Last active
February 4, 2019 16:58
-
-
Save anoited007/77b5f8a89d0bcd8f1ded2826d6d2523a to your computer and use it in GitHub Desktop.
Implementation of Stack Using both arrays and singly LinkedList
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package Stackpkg; | |
public class ArrStack<T> implements IStack<T> { | |
//the length property specifies the length of the array | |
private int length; | |
//the size property gives the number of elements in the stack | |
private int size ; | |
private T[] data; | |
private boolean empty; | |
private int topIndex; | |
public ArrStack(){ | |
length = 30; | |
empty = true; | |
// the topIndex is incremented by 1 anytime an object is added so starting at -1 will make it possible to start | |
// counting at 0 when an object is added. | |
topIndex = -1; | |
data = (T[]) new Object[length]; | |
size = 0; | |
} | |
public ArrStack(int length) { | |
this.length = length; | |
empty = true; | |
size = 0; | |
topIndex = -1; | |
data = (T[]) new Object[length]; | |
} | |
public int getLength() { | |
return length; | |
} | |
public int getSize() { | |
return size; | |
} | |
public int getTopIndex() { | |
return topIndex; | |
} | |
public void setTopIndex(int topIndex) { | |
this.topIndex = topIndex; | |
} | |
@Override | |
public T pop() { | |
if(isEmpty()) return null; | |
else{ | |
T popped = data[topIndex]; | |
data[topIndex] = null; | |
topIndex--; | |
size--; | |
empty = size == 0; //always check if after popping, size is not 0 so that empty can be updated. | |
return popped; | |
} | |
} | |
@Override | |
public T peek() { | |
if(isEmpty()) return null; | |
else return data[topIndex]; | |
} | |
@Override | |
public T push(T element) { | |
if(isFull()) return null; | |
else{ | |
data[topIndex+1] = element; | |
topIndex++; | |
//ensure empty is false after adding to stack. @Stephen is it necessary? | |
empty = false; | |
size++; | |
} | |
return element; | |
} | |
private boolean isFull(){ | |
return size == data.length; | |
} | |
@Override | |
public boolean isEmpty() { | |
return empty; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package Stackpkg; | |
// Interface for Dynamic implementation of Stack | |
public interface IStack<T> { | |
// remove an object from the top of the stack and return the removed object | |
T pop(); | |
//return the object at the top of the stack but do not remove the object | |
T peek(); | |
//add object to the top of the stack | |
T push(T object); | |
//return true if stack is empty or false if otherwise | |
boolean isEmpty(); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package Stackpkg; | |
import LinkedListPkg.LinkedList; | |
import LinkedListPkg.Node; | |
/* Stack implementation using singly linked list */ | |
public class LinkedListStack<T> implements IStack<T> { | |
private LinkedList<T> data; | |
public LinkedListStack(){ | |
data = new LinkedList<>(); | |
} | |
public LinkedListStack(T element){ | |
Node<T> node = new Node<>(element); | |
data = new LinkedList<>(node); | |
} | |
@Override | |
public T pop() { | |
//check if the size of the stack is 0 return null or return the data in the node after calling remove last method | |
return data.size() == 0 ? null : data.removeLast().getData(); | |
} | |
@Override | |
public T peek() { | |
T topElement = null; | |
if(data.size() == 0) return topElement; | |
else { | |
Node<T> temp = data.getHead(); | |
while(temp.hasNext()){ | |
temp = temp.getNext(); | |
if(temp.getNext() == null) topElement = temp.getData(); | |
} | |
} | |
return topElement; | |
} | |
@Override | |
public T push(T element) { | |
Node<T> node = new Node<>(element); | |
data.addFirst(node); | |
return element; | |
} | |
@Override | |
public boolean isEmpty() { | |
return data.size() == 0; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment