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;
            }
        }
    }
}

2 thoughts on “Dequeue using Linked List in Java”

  1. Sir,a program is given which states that:
    Design a class change to convert a decimal number to its equivalent in base 16 and to convert it back to its decimal form. Eg.(i) The decimal number 35 is 23 in base 16. ii) The decimal number 107 is 6B in base 16. Some of the members of the class are given below:
    Class name : change
    Data members a[] : integer type array. n : integer to be converted to base 16.
    Member functions
    change() : constructor to assign 0 to instance variables.
    void input() : accepts integer to be converted to base 16. voidhexadeci(int) : to convert decimal integer to hexadecimal form. voiddecihexa() : to convert hexadecimal number back to decimal form.
    Specify the class change giving the details of the constructor and the functions void input(), void hexadeci(int) and void decihexa(). The main function need not be written.

    Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: