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.
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;
}
}
// Java program to Implement a stack
// using singly linked list
// import package
import static java.lang.System.exit;
// Create Stack Using Linked list
class StackUsingLinkedlist {
// A linked list node
private class Node {
int data; // integer data
Node link; // reference variavle Node type
}
// create globle top reference variable
Node top;
// Constructor
StackUsingLinkedlist()
{
this.top = null;
}
// Utility function to add an element x in the stack
public void push(int x) // insert at the beginning
{
// create new node temp and allocate memory
Node temp = new Node();
// check if stack (heap) is full. Then inserting an
// element would lead to stack overflow
if (temp == null) {
System.out.print("\nHeap Overflow");
return;
}
// initialize data into temp data field
temp.data = x;
// put top reference into temp link
temp.link = top;
// update top reference
top = temp;
}
// Utility function to check if the stack is empty or not
public boolean isEmpty()
{
return top == null;
}
// Utility function to return top element in a stack
public int peek()
{
// check for empty stack
if (!isEmpty()) {
return top.data;
}
else {
System.out.println("Stack is empty");
return -1;
}
}
// Utility function to pop top element from the stack
public void pop() // remove at the beginning
{
// check for stack underflow
if (top == null) {
System.out.print("\nStack Underflow");
return;
}
// update the top pointer to point to the next node
top = (top).link;
}
public void display()
{
// check for stack underflow
if (top == null) {
System.out.printf("\nStack Underflow");
exit(1);
}
else {
Node temp = top;
while (temp != null) {
// print node data
System.out.printf("%d->", temp.data);
// assign temp link to temp
temp = temp.link;
}
}
}
}
// main class
public class GFG {
public static void main(String[] args)
{
// create Object of Implementing class
StackUsingLinkedlist obj = new StackUsingLinkedlist();
// insert Stack value
obj.push(11);
obj.push(22);
obj.push(33);
obj.push(44);
// print Stack elements
obj.display();
// pritn Top element of Stack
System.out.printf("\nTop element is %d\n", obj.peek());
// Delete top element of Stack
obj.pop();
obj.pop();
// pritn Stack elements
obj.display();
// print Top element of Stack
System.out.printf("\nTop element is %d\n", obj.peek());
}
}