Posted on by Kalkicode
Code Queue

# 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 First-In-First-Out (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 tail
Integer count
MyQueue()
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
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()
Print "Empty Queue"
Return -1
Decrement count
Set tail to null
Return data of temp

Integer peek()
Print "Empty Queue"
Return -1

Main function
Create an instance of MyQueue called task
Enqueue elements 10, 20, 30, 40, 50 into the queue
``````

## Algorithm

1. 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.
2. 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.
3. Define a constructor for the `MyQueue` class to initialize the head and tail as `null` and the count as 0.
4. Implement the `size()` method to return the count of elements in the queue.
5. Implement the `isEmpty()` method to check if the queue is empty by checking if the count is 0.
6. Implement the `enqueue(Integer value)` method to add a new element to the queue. Create a new `QNode` with the given value, and if the head is `null`, 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.
7. Implement the `dequeue()` method to remove and return the front element of the queue. If the head is `null`, print "Empty Queue" and return -1. Otherwise, set a temporary variable `temp` to the head, set the head to the next of the head, decrement the count, and if the head is `null`, set the tail to `null`. Return the data of the `temp` node.
8. Implement the `peek()` method to return the front element of the queue without removing it. If the head is `null`, print "Empty Queue" and return -1. Otherwise, return the data of the head node.
9. In the main function, create an instance of `MyQueue` called `task`.
10. Print "isEmpty: " + `task.isEmpty()` to check if the queue is initially empty.
11. Enqueue elements 10, 20, 30, 40, and 50 into the queue using the `enqueue` method.
12. Print "size: " + `task.size()` to get the number of elements in the queue.
13. Print "peek: " + `task.peek()` to view the front element of the queue.
14. Print "dequeue: " + `task.dequeue()` to remove and return the front element of the queue.
15. Print "size: " + `task.size()` to get the updated number of elements in the queue.
16. Print "peek: " + `task.peek()` to view the front element of the queue after dequeueing.
17. Print "isEmpty: " + `task.isEmpty()` to check if the queue is empty after dequeueing.

## 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.

## Comment

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.

Categories
Relative Post