What's the best way to implement a stack using linked lists in Java?
EDIT: I would define best as most efficient using clean code. I have already used an array to implement a stack, but am not familiar with link lists so was wondering if anyone could help me implement something similar to below:
public class StackArray{
private Object [] objArray;
private int stackSize;
public StackArray(){
objArray = new Object[50];
stackSize = 0;
}
public StackArray(int size){
objArray = new Object[size];
stackSize = 0;
}
//public interface methods - push, pop, top, empty & clear
public void push(Object o)throws StackArrayException{
if(stackSize < objArray.length){
objArray[stackSize] = o;
stackSize ++;
}else{
throw new StackArrayException("Stack Overflow");
}
}
public Object pop()throws StackArrayException{
if(stackSize != 0){
stackSize--;
return(objArray[stackSize]);
}else{
throw new StackArrayException("Stack Underflow");
}
}
public void top() throws StackArrayException{
if(stackSize != 0){
return(objArray[stackSize-1]);
}else{
throw new StackArrayException("Stack Underflow");
}
}
public boolean empty(){
return (stackSize == 0):
}
public void clear(){
stackSize = 0;
}
}
EDIT: Here is the linked list implementation if anyone is interested..
public class StackList{
private Node listHead;
protected class Node{
protected Object datum;
protected Node next;
public Node(Object o, Node n){
datum = o;
next = n;
}
public StackList(){
listHead = null;
}
//public interface methods - push pop top empty clear
public void push(Object o){
listHead = new Node(o, listHead);
}
public Object pop() throws StackListException{
if(listHead!=null){
Object top = listHead.datum;
listHead = listHead.next;
return top;
}else{
throw new StackListException("Stack Underflow");
}
}
public Object top()throws StackListException{
if(listHead != null){
return(listHead.datum);
}else{
throw new StackListException("Stack Underflow");
}
}
public boolean empty(){
return (listHead == null);
}
public void clear(){
listHead = null;
}
}
Stack supports various operations like push, pop, peek, empty, and size. It can be implemented using an array and linked list. The benefit of implementing a stack using a linked list in C over arrays is that it allows to grow of the stack as per the requirements, i.e., memory can be allocated dynamically.
In Stack, implementation using Linked-List, every new element inserted to the top of the Stack which means every new inserting element pointed by the top and whenever we want to delete element from the Stack which is pointing to the top of the Stack by moving the top by moving top to is the previous node in the linked ...
The first node has a null in the link field and second node-link has the first node address in the link field and so on and the last node address is in the “top” pointer. The main advantage of using a linked list over arrays is that it is possible to implement a stack that can shrink or grow as much as needed.
Assuming you genuinely want to do this from scratch rather than using one of the perfectly good existing stack implementations then I would recommend:
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With