Posted on by Kalkicode
Code Queue

Implement queue using doubly linked list

In this program, we implement a queue data structure using a doubly linked list in Java,c,c++,python,c#,php etc. A doubly linked list is a data structure where each element (node) in the list contains two references, one pointing to the previous node and the other pointing to the next node. Using a doubly linked list allows us to efficiently add elements to the rear of the queue and remove elements from the front of the queue.

Problem Statement

The problem is to implement a queue data structure using a doubly linked list. The queue should support standard queue operations like enqueue (add element to the rear), dequeue (remove element from the front), and peek (get the front element) efficiently.

Example

Let's consider the following example to demonstrate the implementation of a queue using a doubly linked list.

Input

  • Enqueue 1
  • Enqueue 2
  • Enqueue 3
  • Enqueue 4
  • Enqueue 5

Output

  • Queue Element: 1 2 3 4 5
  • Size: 5
  • Dequeue Node: 1
  • Dequeue Node: 2
  • Dequeue Node: 3
  • Queue Element: 4 5
  • Size: 2

Explanation

  1. We start by creating an empty queue using the MyQueue class.
  2. We enqueue five elements (1, 2, 3, 4, 5) using the enqueue method. The elements are added to the rear of the queue.
  3. We print the elements of the queue using the printQdata method, which displays "Queue Element: 1 2 3 4 5" and the size using the isSize method, which displays "Size: 5".
  4. We dequeue three elements from the front of the queue using the dequeue method. The elements are removed from the front, and we print the updated elements of the queue and its size.
  5. After dequeuing three elements, the queue contains two elements (4, 5), and the output is "Queue Element: 4 5" and "Size: 2".

Idea to Solve the Problem

To implement the queue using a doubly linked list, we define a QNode class representing each node in the doubly linked list. Each node contains data, a reference to the next node (next), and a reference to the previous node (prev). The MyQueue class has a front pointer to the front of the queue and a rear pointer to the rear of the queue. We also keep track of the size of the queue using the size variable.

We implement standard queue operations using these pointers and variables. The enqueue operation adds a new node to the rear of the queue, the dequeue operation removes a node from the front of the queue, and the peek operation returns the front element of the queue.

Pseudocode

// Define QNode class for each node in the doubly linked list
class QNode
    data
    next
    prev

    QNode(data, prev)
        this.data = data
        this.next = null
        this.prev = prev

// Define MyQueue class for the queue
class MyQueue
    front
    rear
    size

    MyQueue()
        this.front = null
        this.rear = null
        this.size = 0

    function enqueue(data)
        // Create a new node with the given data and the current rear as its prev
        node = new QNode(data, this.rear)
        
        // Update the rear pointer to the new node
        this.rear = node
        
        // If the queue is empty (front is null), update the front pointer to the new node
        if this.front == null
            this.front = node
        
        // Increment the size by 1
        this.size = this.size + 1

    function dequeue()
        // Check if the queue is empty, if yes, return -1 (indicating empty queue)
        if this.isEmpty()
            return -1
        
        // Get the data from the front node
        data = this.front.data
        
        // Update the front pointer to the next node
        this.front = this.front.next
        
        // If the front becomes null, update the rear to null as well (indicating empty queue)
        if this.front == null
            this.rear = null
        
        // Decrement the size by 1
        this.size = this.size - 1
        
        // Return the data of the dequeued node
        return data

    function peek()
        // Check if the queue is empty, if yes, return -1 (indicating empty queue)
        if this.isEmpty()
            return -1
        
        // Otherwise, return the data from the front node
        return this.front.data

    function isEmpty()
        // Check if the size is 0, if yes, return true; otherwise, return false
        return this.size == 0

    function size()
        // Return the value of the size variable
        return this.size

Algorithm

  1. Initialize the front and rear pointers as null and the size as 0 in the MyQueue constructor.
  2. Implement the enqueue method:
    • Create a new QNode with the given data and the current rear as its prev.
    • Update the rear pointer to the new node.
    • If the queue is empty (i.e., front is null), update the front pointer to the new node as well.
    • Increment the size by 1.
  3. Implement the dequeue method:
    • Check if the queue is empty. If yes, return -1 (indicating an empty queue).
    • Otherwise, get the data from the front node.
    • Update the front pointer to the next node.
    • If the front becomes null, update the rear to null as well (indicating an empty queue).
    • Decrement the size by 1.
    • Return the data of the dequeued node.
  4. Implement the peek method:
    • Check if the queue is empty. If yes, return -1 (indicating an empty queue).
    • Otherwise, return the data from the front node.
  5. Implement the isEmpty method:
    • Check if the size is 0. If yes, return true; otherwise, return false.
  6. Implement the size method:
    • Return the value of the size variable.

Code Solution

Time Complexity

The time complexity of the enqueue, dequeue, peek, isEmpty, and size operations in this implementation of a queue using a doubly linked list is O(1) since all these operations involve constant-time pointer manipulations and updates.

Finally

The implementation of a queue using a doubly linked list provides an efficient data structure for queue operations with constant-time complexity for enqueue, dequeue, peek, and other operations. The doubly linked list allows for easy management of the front and rear of the queue, making

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.

New Comment







Naeem     678 Day ago
good