Implement queue using Double ended Linked List

 To implement a queue using Linkedlist we can use double ended Linkedlist.

A double ended Linkedlist has first and last node pointer. So we can insert item at last to implement enqueue operation  using last pointer. To implement dequeue operation we can remove item from the first using first node.

Below is the implementation:

class Link:

public class Link {
    public long data;
    public Link next;
    public Link(long data) {
        this.data = data;
    }
    public void displayLink() {
        System.out.println("data :"+ data);
    }
}

class FirstLastList:

public class FirstLastList {
    private Link first;
    private Link last;
    public FirstLastList() {
        first = null;
        last = null;
    }
    public boolean isEmpty() {
        return first == null;
    }
    public void insertLast(long data) {
        Link newLink = new Link(data);
        if (isEmpty()) {
            first = newLink;
        } else {
            last.next = newLink;
        }
        last = newLink;
    }
    public long removeFirst() {  
        Link temp = first;
        first = first.next;
        return temp.data;
    }
    public void display() {
        Link current = first;
        while (current != null) {
            System.out.print(current.data + "-->");
            current = current.next;
        }
    }
}

class LinkQueue:

public class LinkQueue {
    private FirstLastList firstLastList;
    public LinkQueue() {
        this.firstLastList = new FirstLastList();
    }
    public void enqueue(long data) {
        firstLastList.insertLast(data);
    }
    public void dequeue() {
        firstLastList.removeFirst();
    }
    public void displayQueue() {  
        firstLastList.display();
    }
}

class MainApp:
public class MainApp {
    public static void main(String[] args) {
        LinkQueue queue = new LinkQueue();
        queue.displayQueue();
        System.out.println("after enqueue new item");
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);
        queue.enqueue(50);
       
        queue.displayQueue();
        System.out.println("\n");
       
        queue.dequeue();
        System.out.println("after dequeue item");
        queue.displayQueue();
    }
}

Implemented Stack using LinkedList

Link class: 

public class Link {
    public long data;
    public Link next;
    public Link(long data) {
        this.data = data;
    }
    public void displayLink() {
        System.out.println("data :"+ data);
    }
}

 LinkedList class:

public class LinkedList {
    private Link first;
    public LinkedList() {
        first = null;
    }
    public boolean isEmpty() {
        return first == null;
    }
    public void insertFirst(long data) {
        Link newLink = new Link(data);
        newLink.next = first;
        first = newLink;
    }
    public long deleteFirst() {
        Link temp = first;
        first = first.next;
        return temp.data;
    }
    public void displayList() {
        Link current = first;
        while (current != null) {
            System.out.println(current.data + "----");
            current = current.next;
        }
    }
}

 LinkStack class:
public class LinkStack {
    private LinkedList theList;
    public LinkStack() {
        theList = new LinkedList();
    }
    public void push(long data) {
        theList.insertFirst(data);
    }
    public void pop() {
        theList.deleteFirst();
    }
    public boolean isEmpty() {
        return theList.isEmpty();
    }
    public void displayList() {
        System.out.println("displaying the stack---------------");
        theList.displayList();
    }
}

MainApp:

 public class MainApp {
    public static void main(String[] args) {
        LinkStack stack = new LinkStack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);
        stack.displayList();
        stack.pop();
        stack.displayList();
    }
}

Implementing queue

 package LinearDSA;

/**

 * @author lokman 17/09/2022

 *

 */

public class Queue {

private ListNode front;

private ListNode rear;

private int length = 0;

public Queue() {

this.front = null;

this.rear = null;

}

private class ListNode {

private int data;

private ListNode next;

public ListNode(int data) {

this.data = data;

this.next = null;

}

}

public int length() {

return length;

}

public boolean isEmpty() {

return length == 0;

}

public void enqueue(int data) {

ListNode temp = new ListNode(data);

if (isEmpty()) {

front = temp;

} else {

rear.next = temp;

}

rear = temp;

length++;

}

public int dequeue() {

if(isEmpty()) {

System.out.println("Queue is empty");

}

int data  = front.data;

front = front.next;

if(front == null) {

rear = null;

}

length--;

return data;

}

public void print() {

if (isEmpty()) {

return;

}

ListNode current = front;

while (current != null) {

System.out.print(current.data + "-->");

current = current.next;

}

System.out.println("null");

}

public static void main(String[] args) {

Queue queue = new Queue();

queue.enqueue(10);

queue.enqueue(20);

queue.enqueue(30);

queue.print();

queue.dequeue();

queue.print();

}

}