Dequeue using Linked List in Java

Write a program to implement the dequeue (double-ended queue) data structure using linked list.

Note that each node in this dequeue should store an integer.

A dequeue is a linear data structure in which insertion and deletion can be done from either ends.

Perform the following operations on this dequeue:

  • To push an element from the front.
  • To push an element from rear.
  • To pop an element from the front.
  • To pop an element from rear.
import java.io.*;
class Node{
    int data;
    Node next;
    public Node(){
        data = 0;
        next = null;
    }
    public Node(int d){
        data = d;
        next = null;
    }
}
class Dequeue{
    Node front;
    Node rear;
    public Dequeue(){
        front = null;
        rear = null;
    }
    public void pushFront(int d){
        Node n = new Node(d);
        if(front == null){
            front = n;
            rear = n;
        }
        else{
            n.next = front;
            front = n;
        }
    }
    public void pushRear(int d){
        Node n = new Node(d);
        if(rear == null){
            front = n;
            rear = n;
        }
        else{
            rear.next = n;
            rear = n;
        }
    }
    public void popFront(){
        if(front == null)
            System.out.println("Dequeue empty!");
        else{
            int d = front.data;
            front = front.next;
            if(front == null)
                rear = null;
            System.out.println(d + " popped from front.");
        }
    }
    public void popRear(){
        if(rear == null)
            System.out.println("Dequeue empty!");
        else{
            int d = rear.data;
            if(front == rear){
                front = null;
                rear = null;
            }
            else{
                Node n = front;
                while(n.next != rear)
                    n = n.next;
                rear = n;
                rear.next = null;
            }
            System.out.println(d + " popped from rear.");
        }
    }
    public void display(){
        if(front == null)
            System.out.println("Dequeue empty!");
        else{
            Node n = front;
            System.out.println("Dequeue contents:");
            while(n != null){
                System.out.print(n.data + "\t");
                n = n.next;
            }
            System.out.println();
        }
    }
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Dequeue q = new Dequeue();
        while(true){
            System.out.println("1. Push from front");
            System.out.println("2. Push from rear");
            System.out.println("3. Pop from front");
            System.out.println("4. Pop from rear");
            System.out.println("5. Display");
            System.out.print("Enter your choice: ");
            int choice = Integer.parseInt(br.readLine());
            switch(choice){
                case 1:
                System.out.print("Enter data to be pushed from the front: ");
                int d = Integer.parseInt(br.readLine());
                q.pushFront(d);
                break;
                case 2:
                System.out.print("Enter data to be pushed from rear: ");
                d = Integer.parseInt(br.readLine());
                q.pushRear(d);
                break;
                case 3:
                q.popFront();
                break;
                case 4:
                q.popRear();
                break;
                case 5:
                q.display();
                break;
                default:
                System.out.println("Bye...");
                return;
            }
        }
    }
}
%d bloggers like this: