Implement Stack Using Linked List

by

Objective: Write an algorithm to implement Stack using Linked List.

If you do not know about then for starters its abstract data type in which follows the principle of LIFO (Last-In-First-Out) which means the data goes in last comes out first to read about in detail please read this link Stack

Approach:

Solution is quite simple, Earlier we have seen an article  “Linked List Implementation“, we need to make some changes to make it work as Stack.

Stack Operations:

Push() : Insert the element into linked list at the beginning and increase the size of the list. O(1) operation.

Pop() : Return the element first node from the linked list and move the head pointer to the second node. Decrease the size of the list. O(1) operation.

getSize(): Return the size of linked list.

displayStack(): Print the linked list.

Complete Code:

public class StackUsingLinkedList {
Node head= null;
int size =0;
public void push(int data){
Node x = new Node(data);
if(getSize()==0){
head = x;
}else{
//add the Node at the start of a Linked List
Node temp = head;
x.next = temp;
head = x;
}
System.out.println("Element "+ data + " is pushed into Stack");
size++;
}
public int pop(){
if(getSize()==0){
System.out.println("Stack is Empty");
return –1;
}else{
Node temp = head;
head = head.next;
size—;
return temp.data;
}
}
public void printStack(){
Node curr = head;
while(curr!=null){
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
public int getSize(){
return size;
}
public static void main(String[] args) {
StackUsingLinkedList stck = new StackUsingLinkedList();
stck.push(1);
stck.push(2);
stck.push(4);
stck.printStack();
System.out.println("Pop out element " + stck.pop());
stck.printStack();
}
}
class Node{
int data;
Node next;
public Node(int data){
this.data = data;
}
}

view raw
StackUsingLinkedList.java
hosted with ❤ by GitHub


Output:

Element 1 is pushed into Stack
Element 2 is pushed into Stack
Element 4 is pushed into Stack
4 2 1
Pop out element 4
2 1

Note: Also read, Track the Maximum Element in a Stack. This problem was asked in Yahoo in Software Engineer position.

Related Posts: