Implement queue using linked list
In this problem, we need to implement a queue data structure using a linked list. A queue is a linear data structure that follows the FirstInFirstOut (FIFO) principle, meaning that the element added first will be removed first. In a queue, elements are added to the back (enqueue operation) and removed from the front (dequeue operation).
Problem Statement
The problem is to implement a queue data structure using a linked list and provide basic operations like enqueue, dequeue, peek (to view the front element), size (to get the number of elements in the queue), and isEmpty (to check if the queue is empty).
Idea to Solve the Problem
To implement the queue using a linked list, we can use a class QNode
to represent each node in the
linked list. The QNode
contains an integer data value and a reference to the next node in the
linked list. We also need a class MyQueue
to represent the queue, which contains a reference to the
head and tail of the linked list, as well as a count to keep track of the number of elements in the queue.
Pseudocode
Class QNode
Integer data
QNode next
QNode(value)
data = value
next = null
Class MyQueue
QNode head
QNode tail
Integer count
MyQueue()
head = null
tail = null
count = 0
Integer size()
Return count
Boolean isEmpty()
Return count == 0
Void enqueue(Integer value)
Create a new QNode with value as data
If head is null
Set head to the new node
Else
Set next of tail to the new node
Set tail to the new node
Increment count
Integer dequeue()
If head is null
Print "Empty Queue"
Return 1
Set temp to head
Set head to next of head
Decrement count
If head is null
Set tail to null
Return data of temp
Integer peek()
If head is null
Print "Empty Queue"
Return 1
Return data of head
Main function
Create an instance of MyQueue called task
Print "isEmpty: " + task.isEmpty()
Enqueue elements 10, 20, 30, 40, 50 into the queue
Print "size: " + task.size()
Print "peek: " + task.peek()
Print "dequeue: " + task.dequeue()
Print "size: " + task.size()
Print "peek: " + task.peek()
Print "isEmpty: " + task.isEmpty()
Algorithm
 Create a class
QNode
to represent each node in the linked list. The class contains an integer data value and a reference to the next node in the linked list.  Create a class
MyQueue
to represent the queue. The class contains references to the head and tail of the linked list, as well as a count to keep track of the number of elements in the queue.  Define a constructor for the
MyQueue
class to initialize the head and tail asnull
and the count as 0.  Implement the
size()
method to return the count of elements in the queue.  Implement the
isEmpty()
method to check if the queue is empty by checking if the count is 0.  Implement the
enqueue(Integer value)
method to add a new element to the queue. Create a newQNode
with the given value, and if the head isnull
, set it as the head. Otherwise, set the next of the tail to the new node. Set the tail to the new node and increment the count.  Implement the
dequeue()
method to remove and return the front element of the queue. If the head isnull
, print "Empty Queue" and return 1. Otherwise, set a temporary variabletemp
to the head, set the head to the next of the head, decrement the count, and if the head isnull
, set the tail tonull
. Return the data of thetemp
node.  Implement the
peek()
method to return the front element of the queue without removing it. If the head isnull
, print "Empty Queue" and return 1. Otherwise, return the data of the head node.  In the main function, create an instance of
MyQueue
calledtask
.  Print "isEmpty: " +
task.isEmpty()
to check if the queue is initially empty.  Enqueue elements 10, 20, 30, 40, and 50 into the queue using the
enqueue
method.  Print "size: " +
task.size()
to get the number of elements in the queue.  Print "peek: " +
task.peek()
to view the front element of the queue.  Print "dequeue: " +
task.dequeue()
to remove and return the front element of the queue.  Print "size: " +
task.size()
to get the updated number of elements in the queue.  Print "peek: " +
task.peek()
to view the front element of the queue after dequeueing.  Print "isEmpty: " +
task.isEmpty()
to check if the queue is empty after dequeueing.
Code Solution

1) Implement queue using linked list in java
2) Implement queue using linked list in c++
3) Implement queue using linked list in c
4) Implement queue using linked list in golang
5) Implement queue using linked list in c#
6) Implement queue using linked list in php
7) Implement queue using linked list in python
8) Implement queue using linked list in ruby
9) Implement queue using linked list in scala
10) Implement queue using linked list in swift
11) Implement queue using linked list in kotlin
12) Implement queue using linked list in vb.net
13) Implement queue using linked list in node js
14) Implement queue using linked list in typescript
Time Complexity
The time complexity of enqueue and dequeue operations in a queue implemented using a linked list is O(1) since adding or removing elements from the back or front of the linked list takes constant time. The time complexity of other operations like peek, size, and isEmpty is also O(1) as they involve simple operations on variables.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment