Write a program to implement Stack and linear queue adt using linked list

Queue – Linked List Implementation

In the previous post, we introduced Queue and discussed array implementation. In this post, linked list implementation is discussed. The following two main operations must be implemented efficiently.
In a Queue data structure, we maintain two pointers, front and rear. The front points the first item of queue and rear points to last item.
enQueue() This operation adds a new node after rear and moves rear to the next node.
deQueue() This operation removes the front node and moves front to the next node.

Table of Contents Show

Queue – Linked List Implementation
Implement a stack using singly linked list
Linked List implementation of Queue
C program to Implement a Queue using Linked List
Queue using linked list

Implement a stack using singly linked list

To implement a stack using singly linked list concept , all the singly linked list operations are performed based on Stack operations LIFO(last in first out) and with the help of that knowledge we are going to implement a stack using single linked list. Using singly linked lists , we implement stack by storing the information in the form of nodes and we need to follow the stack rules and implement using singly linked list nodes . So we need to follow a simple rule in the implementation of a stack which is last in first out and all the operations can be performed with the help of a top variable .Let us learn how to perform Pop , Push , Peek ,Display operations in the following article .

A stack can be easily implemented using the linked list. In stack Implementation, a stack contains a top pointer. which is “head” of the stack where pushing and popping items happens at the head of the list. First node have null in link field and second node link have first node address in link field and so on and last node address in “top” pointer.
The main advantage of using linked list over an arrays is that it is possible to implement a stack that can shrink or grow as much as needed. In using array will put a restriction to the maximum capacity of the array which can lead to stack overflow. Here each new node will be dynamically allocate. so overflow is not possible.
Stack Operations:

push() : Insert a new element into stack i.e just inserting a new element at the beginning of the linked list.
pop() : Return top element of the Stack i.e simply deleting the first element from the linked list.
peek(): Return the top element.
display(): Print all elements in Stack.

Below is the implementation of the above approach:

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;

Node* link;
};
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 in heap

Node* temp = new Node();

// Check if stack (heap) is full.

// Then inserting an element would

// lead to stack overflow

if (!temp)

{

cout << "\nStack 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()
{

//If top is NULL it means that

//there are no elements are in stack

return top == NULL;
}
// Utility function to return top element in a stack

int peek()
{

// If stack is not empty , return the top element

if (!isEmpty())

return top->data;

else

exit(1);
}
// Utility function to pop top
// element from the stack

void pop()
{

Node* temp;

// Check for stack underflow

if (top == NULL)

{

cout << "\nStack Underflow" << endl;

exit(1);

}

else

{

// Assign top to temp

temp = top;

// Assign second node to top

top = top->link;

//This will automatically destroy

//the link between first node and second node

// Release memory of top node

//i.e delete the node

free(temp);

}
}
// Function to print all the
// elements of the stack

void display()
{

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;
}

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 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();

// 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());

}
}

Python3

'''Python supports automatic garbage collection so deallocation of memory
is done implicitly. However to force it to deallocate each node after use,
add the following code:

import gc #added at the start of program

gc.collect() #to be added wherever memory is to be deallocated
'''

class Node:

# Class to create nodes of linked list

# constructor initializes node automatically

def __init__(self,data):

self.data = data

self.next = None

class Stack:

# head is default NULL

def __init__(self):

self.head = None

# Checks if stack is empty

def isempty(self):

if self.head == None:

return True

else:

return False

# Method to add data to the stack

# adds to the start of the stack

def push(self,data):

if self.head == None:

self.head=Node(data)

else:

newnode = Node(data)

newnode.next = self.head

self.head = newnode

# Remove element that is the current head (start of the stack)

def pop(self):

if self.isempty():

return None

else:

# Removes the head node and makes

#the preceding one the new head

poppednode = self.head

self.head = self.head.next

poppednode.next = None

return poppednode.data

# Returns the head node data

def peek(self):

if self.isempty():

return None

else:

return self.head.data

# Prints out the stack

def display(self):

iternode = self.head

if self.isempty():

print("Stack Underflow")

else:

while(iternode != None):

print(iternode.data,"->",end = " ")

iternode = iternode.next

return

# Driver code

MyStack = Stack()

MyStack.push(11)

MyStack.push(22)

MyStack.push(33)

MyStack.push(44)
# Display stack elements 
MyStack.display()
# Print top element of stack 

print("\nTop element is ",MyStack.peek())
# Delete top elements of stack 
MyStack.pop()
MyStack.pop()
# Display stack elements
MyStack.display()
# Print top element of stack 

print("\nTop element is ", MyStack.peek())
# This code is contributed by Mathew George

// C# program to Implement a stack 
// using singly linked list 
// import package

using System;
// Create Stack Using Linked list 

public class StackUsingLinkedlist
{ 

// A linked list node

private class Node

{

// integer data

public int data;

// reference variable Node type

public Node link;

}

// create global top reference variable

Node top;

// Constructor

public StackUsingLinkedlist()

{

this.top = null;

}

// Utility function to add

// an element x in the stack

// insert at the beginning

public void push(int x)

{

// 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)

{

Console.Write("\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 bool 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

{

Console.WriteLine("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)

{

Console.Write("\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)

{

Console.Write("\nStack Underflow");

return;

}

else

{

Node temp = top;

while (temp != null)

{

// print node data

Console.Write("{0}->", temp.data);

// assign temp link to temp

temp = temp.link;

}

}

}
} 
// Driver code 

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();

// print Top element of Stack

Console.Write("\nTop element is {0}\n", obj.peek());

// Delete top element of Stack

obj.pop();

obj.pop();

// print Stack elements

obj.display();

// print Top element of Stack

Console.Write("\nTop element is {0}\n", obj.peek());

}
}
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program to Implement a stack
// using singly linked list
// import package
// A linked list node
class Node
{

constructor()

{

this.data=0;

this.link=null;

}
}
// Create Stack Using Linked list
class StackUsingLinkedlist
{

constructor()

{

this.top=null;

}

// Utility function to add an element x in the stack

push(x)

{

// create new node temp and allocate memory

let temp = new Node();

// check if stack (heap) is full. Then inserting an

// element would lead to stack overflow

if (temp == null) {

document.write("<br>Heap Overflow");

return;

}

// initialize data into temp data field

temp.data = x;

// put top reference into temp link

temp.link = this.top;

// update top reference

this.top = temp;

}

// Utility function to check if the stack is empty or not

isEmpty()

{

return this.top == null;

}

// Utility function to return top element in a stack

peek()

{

// check for empty stack

if (!this.isEmpty()) {

return this.top.data;

}

else {

document.write("Stack is empty<br>");

return -1;

}

}

// Utility function to pop top element from the stack

pop() // remove at the beginning

{

// check for stack underflow

if (this.top == null) {

document.write("<br>Stack Underflow");

return;

}

// update the top pointer to point to the next node

this.top = this.top.link;

}

display()

{

// check for stack underflow

if (this.top == null) {

document.write("<br>Stack Underflow");

}

else {

let temp = this.top;

while (temp != null) {

// print node data

document.write(temp.data+"->");

// assign temp link to temp

temp = temp.link;

}

}

}
}
// main class
// create Object of Implementing class

let 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

document.write("<br>Top element is ", obj.peek()+"<br>");
// Delete top element of Stack
obj.pop();
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack

document.write("<br>Top element is ", obj.peek()+"<br>");
// This code is contributed by rag2127
</script>

Output:

44->33->22->11-> Top element is 44 22->11-> Top element is 22

Time Complexity:

The time complexity for all push(), pop(), and peek() operations is O(1) as we are not performing any kind of traversal over the list. We perform all the operations through the current pointer only.

Article Tags :

Linked List

Stack

Technical Scripter

Technical Scripter 2018

Practice Tags :

Linked List

Stack

Read Full Article

Linked List implementation of Queue

Due to the drawbacks discussed in the previous section of this tutorial, the array implementation can not be used for the large scale applications where the queues are implemented. One of the alternative of array implementation is linked list implementation of queue.

The storage requirement of linked representation of a queue with n elements is o(n) while the time requirement for operations is o(1).

In a linked queue, each node of the queue consists of two parts i.e. data part and the link part. Each element of the queue points to its immediate next element in the memory.

In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer. The front pointer contains the address of the starting element of the queue while the rear pointer contains the address of the last element of the queue.

Insertion and deletions are performed at rear and front end respectively. If front and rear both are NULL, it indicates that the queue is empty.

The linked representation of queue is shown in the following figure.

C program to Implement a Queue using Linked List

/* * C Program to Implement Queue Data Structure using Linked List */ #include <stdio.h> #include <stdlib.h> struct node { int data; struct node *next; } *front, *back; /* Create an empty queue */ void initialize() { front = back = NULL; } /* Returns queue size */ int getQueueSize() { struct node *temp = front; int count = 0; if(front == NULL && back == NULL) return 0; while(temp != back){ count++; temp = temp->next; } if(temp == back) count++; return count; } /* Returns Frnt Element of the Queue */ int getFrontElement() { return front->data; } /* Returns the Rear Element of the Queue */ int getBackElement() { return back->data; } /* Check's if Queue is empty or not */ void isEmpty() { if (front == NULL && back == NULL) printf("Empty Queue\n"); else printf("Queue is not Empty\n"); } /* Adding elements in Queue */ void enqueue(int num) { struct node *temp; temp = (struct node *)malloc(sizeof(struct node)); temp->data = num; temp->next = NULL; if (back == NULL) { front = back = temp; } else { back->next = temp; back = temp; } } /* Removes an element from front of the queue */ void dequeue() { struct node *temp; if (front == NULL) { printf("\nQueue is Empty \n"); return; } else { temp = front; front = front->next; if(front == NULL){ back = NULL; } printf("Removed Element : %d\n", temp->data); free(temp); } } /* Print's Queue */ void printQueue() { struct node *temp = front; if ((front == NULL) && (back == NULL)) { printf("Queue is Empty\n"); return; } while (temp != NULL) { printf("%d", temp->data); temp = temp->next; if(temp != NULL) printf("-->"); } } int main() { /* Initializing Queue */ initialize(); /* Adding elements in Queue */ enqueue(1); enqueue(3); enqueue(7); enqueue(5); enqueue(10); /* Printing Queue */ printQueue(); /* Printing size of Queue */ printf("\nSize of Queue : %d\n", getQueueSize()); /* Printing front and rear element of Queue */ printf("Front Element : %d\n", getFrontElement()); printf("Rear Element : %d\n", getBackElement()); /* Removing Elementd from Queue */ dequeue(); dequeue(); dequeue(); dequeue(); dequeue(); dequeue(); return 0; } Output
1-->3-->7-->5-->10 Size of Queue : 5 Front Element : 1 Rear Element : 10 Removed Element : 1 Removed Element : 3 Removed Element : 7 Removed Element : 5 Removed Element : 10 Queue is Empty