In this article, the Linked List implementation of the queue data structure is discussed and implemented. Print ‘-1’ if the queue is empty.
Approach: To solve the problem follow the below idea:
we maintain two pointers, front, and rear. The front points to the first item of the queue and rear points to the last item.
- enQueue(): This operation adds a new node after the rear and moves the rear to the next node.
- deQueue(): This operation removes the front node and moves the front to the next node.
Follow the below steps to solve the problem:
- Create a class QNode with data members integer data and QNode* next
- A parameterized constructor that takes an integer x value as a parameter and sets data equal to x and next as NULL
- Create a class Queue with data members QNode front and rear
- Enqueue Operation with parameter x:
- Initialize QNode* temp with data = x
- If the rear is set to NULL then set the front and rear to temp and return(Base Case)
- Else set rear next to temp and then move rear to temp
- Dequeue Operation:
- If the front is set to NULL return(Base Case)
- Initialize QNode temp with front and set front to its next
- If the front is equal to NULL then set the rear to NULL
- Delete temp from the memory
Below is the Implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct QNode {
int data;
QNode* next;
QNode( int d)
{
data = d;
next = NULL;
}
};
struct Queue {
QNode *front, *rear;
Queue() { front = rear = NULL; }
void enQueue( int x)
{
QNode* temp = new QNode(x);
if (rear == NULL) {
front = rear = temp;
return ;
}
rear->next = temp;
rear = temp;
}
void deQueue()
{
if (front == NULL)
return ;
QNode* temp = front;
front = front->next;
if (front == NULL)
rear = NULL;
delete (temp);
}
};
int main()
{
Queue q;
q.enQueue(10);
q.enQueue(20);
q.deQueue();
q.deQueue();
q.enQueue(30);
q.enQueue(40);
q.enQueue(50);
q.deQueue();
cout << "Queue Front : " << ((q.front != NULL) ? (q.front)->data : -1)<< endl;
cout << "Queue Rear : " << ((q.rear != NULL) ? (q.rear)->data : -1);
}
|
C
#include <stdio.h>
#include <stdlib.h>
struct QNode {
int key;
struct QNode* next;
};
struct Queue {
struct QNode *front, *rear;
};
struct QNode* newNode( int k)
{
struct QNode* temp
= ( struct QNode*) malloc ( sizeof ( struct QNode));
temp->key = k;
temp->next = NULL;
return temp;
}
struct Queue* createQueue()
{
struct Queue* q
= ( struct Queue*) malloc ( sizeof ( struct Queue));
q->front = q->rear = NULL;
return q;
}
void enQueue( struct Queue* q, int k)
{
struct QNode* temp = newNode(k);
if (q->rear == NULL) {
q->front = q->rear = temp;
return ;
}
q->rear->next = temp;
q->rear = temp;
}
void deQueue( struct Queue* q)
{
if (q->front == NULL)
return ;
struct QNode* temp = q->front;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
free (temp);
}
int main()
{
struct Queue* q = createQueue();
enQueue(q, 10);
enQueue(q, 20);
deQueue(q);
deQueue(q);
enQueue(q, 30);
enQueue(q, 40);
enQueue(q, 50);
deQueue(q);
printf ( "Queue Front : %d \n" , ((q->front != NULL) ? (q->front)->key : -1));
printf ( "Queue Rear : %d" , ((q->rear != NULL) ? (q->rear)->key : -1));
return 0;
}
|
Java
class QNode {
int key;
QNode next;
public QNode( int key)
{
this .key = key;
this .next = null ;
}
}
class Queue {
QNode front, rear;
public Queue() { this .front = this .rear = null ; }
void enqueue( int key)
{
QNode temp = new QNode(key);
if ( this .rear == null ) {
this .front = this .rear = temp;
return ;
}
this .rear.next = temp;
this .rear = temp;
}
void dequeue()
{
if ( this .front == null )
return ;
QNode temp = this .front;
this .front = this .front.next;
if ( this .front == null )
this .rear = null ;
}
}
public class Test {
public static void main(String[] args)
{
Queue q = new Queue();
q.enqueue( 10 );
q.enqueue( 20 );
q.dequeue();
q.dequeue();
q.enqueue( 30 );
q.enqueue( 40 );
q.enqueue( 50 );
q.dequeue();
System.out.println( "Queue Front : " + ((q.front != null ) ? (q.front).key : - 1 ));
System.out.println( "Queue Rear : " + ((q.rear != null ) ? (q.rear).key : - 1 ));
}
}
|
Python3
class Node:
def __init__( self , data):
self .data = data
self . next = None
class Queue:
def __init__( self ):
self .front = self .rear = None
def isEmpty( self ):
return self .front = = None
def EnQueue( self , item):
temp = Node(item)
if self .rear = = None :
self .front = self .rear = temp
return
self .rear. next = temp
self .rear = temp
def DeQueue( self ):
if self .isEmpty():
return
temp = self .front
self .front = temp. next
if ( self .front = = None ):
self .rear = None
if __name__ = = '__main__' :
q = Queue()
q.EnQueue( 10 )
q.EnQueue( 20 )
q.DeQueue()
q.DeQueue()
q.EnQueue( 30 )
q.EnQueue( 40 )
q.EnQueue( 50 )
q.DeQueue()
print ( "Queue Front : " + str (q.front.data if q.front ! = None else - 1 ))
print ( "Queue Rear : " + str (q.rear.data if q.rear ! = None else - 1 ))
|
C#
using System;
class QNode {
public int key;
public QNode next;
public QNode( int key)
{
this .key = key;
this .next = null ;
}
}
class Queue {
public QNode front, rear;
public Queue() { this .front = this .rear = null ; }
public void enqueue( int key)
{
QNode temp = new QNode(key);
if ( this .rear == null ) {
this .front = this .rear = temp;
return ;
}
this .rear.next = temp;
this .rear = temp;
}
public void dequeue()
{
if ( this .front == null )
return ;
this .front = this .front.next;
if ( this .front == null )
this .rear = null ;
}
}
public class Test {
public static void Main(String[] args)
{
Queue q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.dequeue();
q.dequeue();
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);
q.dequeue();
Console.WriteLine( "Queue Front : " + ((q.front != null ) ? (q.front).key : -1));
Console.WriteLine( "Queue Rear : " + ((q.rear != null ) ? (q.rear).key : -1));
}
}
|
Javascript
<script>
class QNode
{
constructor(key)
{
this .key = key;
this .next = null ;
}
}
let front = null , rear = null ;
function enqueue(key)
{
let temp = new QNode(key);
if (rear == null ) {
front = rear = temp;
return ;
}
rear.next = temp;
rear = temp;
}
function dequeue()
{
if (front == null )
return ;
let temp = front;
front = front.next;
if (front == null )
rear = null ;
}
enqueue(10);
enqueue(20);
dequeue();
dequeue();
enqueue(30);
enqueue(40);
enqueue(50);
dequeue();
document.write( "Queue Front : " + ((front != null ) ? (front).key : -1) + "<br>" );
document.write( "Queue Rear : " + ((rear != null ) ? (rear).key : -1) + "<br>" );
</script>
|
Output
Queue Front : 40
Queue Rear : 50
Time Complexity: O(1), The time complexity of both operations enqueue() and dequeue() is O(1) as it only changes a few pointers in both operations
Auxiliary Space: O(1), The auxiliary Space of both operations enqueue() and dequeue() is O(1) as constant extra space is required
Related Article:
Introduction and Array Implementation of Queue
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!