Linked List Implementation of Stack
A Stack is an ordered list. Insertion and deletion of element is done at top. The last element inserted will the first element for delete or traversal. Hence it is Last In First Out (LIFO) list. The basic stack functionality includes push and pop. Depending on the requirement you can add functionality like top , deleteStack , etc.
We will have an interface to specify the requirements of the stack.
Note: We are implementing a stack which stores integer values.
A Stack is an ordered list. Insertion and deletion of element is done at top. The last element inserted will the first element for delete or traversal. Hence it is Last In First Out (LIFO) list. The basic stack functionality includes push and pop. Depending on the requirement you can add functionality like top , deleteStack , etc.
As we are using the linked list implementation , we have the Node class which is representation of singly linked list. It has data and next attribute.
class Node {
private Integer data;
private Node next;
public Node(Integer data) {
super();
this.data = data;
}
public Integer getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return "Node [data=" + data + ", next=" + next + "]";
}
}
private Integer data;
private Node next;
public Node(Integer data) {
super();
this.data = data;
}
public Integer getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return "Node [data=" + data + ", next=" + next + "]";
}
}
Note: We are implementing a stack which stores integer values.
interface Stack {
public void push(int data);
public Node pop();
public Node top();
public boolean isEmpty();
public void deleteStack();
}
Now based on the interface we have the below class MyStack which has the implementation of Stack.public void push(int data);
public Node pop();
public Node top();
public boolean isEmpty();
public void deleteStack();
}
class MyStack implements Stack {
private Node headNode;
public void push(int data) {
if (headNode == null) {
headNode = new Node(data);
} else {
Node node = new Node(data);
node.setNext(headNode);
headNode = node;
}
}
public Node top() {
if (headNode == null) {
return null;
} else {
return headNode;
}
}
public Node pop() {
Node node = null;
if (headNode == null) {
System.out.println("stack empty");
} else {
node = headNode;
headNode = headNode.getNext();
}
return node;
}
public boolean isEmpty() {
if (headNode == null) {
return true;
} else {
return false;
}
}
public void deleteStack() {
headNode = null;
}
@Override
public String toString() {
return "MyStack [headNode=" + headNode + "]";
}
}
private Node headNode;
public void push(int data) {
if (headNode == null) {
headNode = new Node(data);
} else {
Node node = new Node(data);
node.setNext(headNode);
headNode = node;
}
}
public Node top() {
if (headNode == null) {
return null;
} else {
return headNode;
}
}
public Node pop() {
Node node = null;
if (headNode == null) {
System.out.println("stack empty");
} else {
node = headNode;
headNode = headNode.getNext();
}
return node;
}
public boolean isEmpty() {
if (headNode == null) {
return true;
} else {
return false;
}
}
public void deleteStack() {
headNode = null;
}
@Override
public String toString() {
return "MyStack [headNode=" + headNode + "]";
}
}
MyStack class contains headNode which is used for operations of push , pop,etc.
Below is the MainClass which contaions the main method.
public class MainClass {
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push(55);
stack.push(12);
stack.push(5);
stack.push(18);
System.out.println(stack);
System.out.println("Top is :" + stack.top().getData());
System.out.println("Pop :" + stack.pop().getData());
System.out.println("Top after one pop :" + stack.top().getData());
}
}
public static void main(String[] args) {
MyStack stack = new MyStack();
stack.push(55);
stack.push(12);
stack.push(5);
stack.push(18);
System.out.println(stack);
System.out.println("Top is :" + stack.top().getData());
System.out.println("Pop :" + stack.pop().getData());
System.out.println("Top after one pop :" + stack.top().getData());
}
}
Output:
MyStack [headNode=Node [data=18, next=Node [data=5, next=Node [data=12, next=Node [data=55, next=null]]]]]
Top is :18
Pop :18
Top after one pop :5
In the main method we are inserting 55 , 12 , 5 and 18. The top method will return the top Node having data as 18. Pop will remove 18 from stack. The top will be Node with value 5 after one pop.
Conclusion: Singly Linked List implementation of Stack is very simple.
Excellent explanation...very helpful
ReplyDelete