Skip to content

Instantly share code, notes, and snippets.

@anoited007
Last active February 4, 2019 16:58
Show Gist options
  • Save anoited007/77b5f8a89d0bcd8f1ded2826d6d2523a to your computer and use it in GitHub Desktop.
Save anoited007/77b5f8a89d0bcd8f1ded2826d6d2523a to your computer and use it in GitHub Desktop.
Implementation of Stack Using both arrays and singly LinkedList
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;
}
}
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();
}
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