How to implement a stack using linked list in Java & C++

Hello Coders! Welcome to codingbroz and our Data Structures and algorithm interview series.

Today, we are going to see an interesting problem commonly asked in coding interviews is How to implement a stack using linked list ? We will also implement the code in Java as well as C++ programming language.

How to implement a stack using linked list in Java & C++

Problem : 

The problem statement says that, you have to implement a stack using linked list.

You have to implement the LIFO property of stack using the linked list data structure.

You have to implement the following functions using a linked list which follows the LIFO property of stack :

  • push() : This function should accept data in LIFO manner.
  • pop() : This function should return and remove data in LIFO manner.
  • peek() : This function should return the data in LIFO manner.

Also Read : How to implement a queue using linked list – Java & C++

Solution – How to implement a stack using linked list

Java

// 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 variable Node type
	}
	// create global top reference variable global
	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 CB {
	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();

		// print Top element of Stack
		System.out.printf("\nTop element is %d\n", obj.peek());

		// Delete top element of Stack
		obj.pop();
		obj.pop();

		// print Stack elements
		obj.display();

		// print Top element of Stack
		System.out.printf("\nTop element is %d\n", obj.peek());
	}
}

C++

// C++ program to Implement a stack 
//using singly linked list 
#include <bits/stdc++.h> 
using namespace std; 
 
// Declare linked list node 
 
struct Node 
{ 
    int data; 
    struct Node* link; 
}; 
 
struct Node* top; 
 
// Utility function to add an element 
// data in the stack insert at the beginning 
void push(int data) 
{ 
     
    // Create new node temp and allocate memory 
    struct Node* temp; 
    temp = new Node(); 
 
    // Check if stack (heap) is full. 
    // Then inserting an element would 
    // lead to stack overflow 
    if (!temp)
    { 
        cout << "\nHeap Overflow"; 
        exit(1); 
    } 
 
    // Initialize data into temp data field 
    temp->data = data; 
 
    // Put top pointer reference into temp link 
    temp->link = top; 
 
    // Make temp as top of Stack 
    top = temp; 
} 
 
// Utility function to check if 
// the stack is empty or not 
int isEmpty() 
{ 
    return top == NULL; 
} 
 
// Utility function to return top element in a stack 
int peek() 
{ 
     
    // Check for empty stack 
    if (!isEmpty()) 
        return top->data; 
    else
        exit(1); 
} 
 
// Utility function to pop top 
// element from the stack 
void pop() 
{ 
    struct Node* temp; 
 
    // Check for stack underflow 
    if (top == NULL) 
    { 
        cout << "\nStack Underflow" << endl; 
        exit(1); 
    } 
    else
    { 
         
        // Top assign into temp 
        temp = top; 
 
        // Assign second node to top 
        top = top->link; 
 
        // Destroy connection between
        // first and second 
        temp->link = NULL; 
 
        // Release memory of top node 
        free(temp); 
    } 
} 
 
// Function to print all the 
// elements of the stack 
void display() 
{ 
    struct Node* temp; 
 
    // Check for stack underflow 
    if (top == NULL)
    { 
        cout << "\nStack Underflow"; 
        exit(1); 
    } 
    else
    { 
        temp = top; 
        while (temp != NULL)
        { 
 
            // Print node data 
            cout << temp->data << "-> "; 
 
            // Assign temp link to temp 
            temp = temp->link; 
        } 
    } 
} 
 
// Driver Code 
int main() 
{ 
     
    // Push the elements of stack 
    push(11); 
    push(22); 
    push(33); 
    push(44); 
 
    // Display stack elements 
    display(); 
 
    // Print top element of stack 
    cout << "\nTop element is "
         << peek() << endl; 
 
    // Delete top elements of stack 
    pop(); 
    pop(); 
 
    // Display stack elements 
    display(); 
 
    // Print top element of stack 
    cout << "\nTop element is "
         << peek() << endl; 
          
    return 0; 
} 

More Problems related to Linked List –

Leave a Comment

Your email address will not be published.