ساختار داده ها: صف ایمن ، عمومی و دوتایی را اجرا کنید.

package com.deque;


class Node{
    T data;
    Node prev;
    Node next;

    public Node(T data){
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

package com.deque;

// A custom Double Ended Queue (Deque) implementation:

public interface MyDeque {

    public  T addHead(T data);
    public  T addTail(T data);

    public T getHead();
    public T getTail();

    public  boolean contains(T data);

    public T removeHead();
    public T removeTail();

    public T peekHead();
    public T peekTail();

    public T pollHead();
    public T pollTail();

    public T pop();

    public int size();
    public void printDequq() ;

}

class MyDequeImpl implements MyDeque{
    private Node head;
    private Node tail;
    private int size;

    public MyDequeImpl(){
        head = null;
        tail = null;
        size = 0;
    }

    public  T addHead(T data) {
        Node current = new Node<>(data);
        if(head == null) {
            head = current;
            tail = current;
            size++;
            return data;
        }
        current.next = head;
        head.prev = current;
        head = current;
        size++;

        return data;
    }

    public  T addTail(T data) {
        Node current = new Node(data);

        if(tail == null) {
            head = current;
            tail = current;
            size++;
            return data;
        }
        tail.next = current;
        current.prev = tail;
        tail = current;
        size++;
        return data;
    }

    public T getHead() {
        if (head == null)
            return null;
        return head.data;
    }

    public T getTail() {
        if(tail == null)
            return null;
        return tail.data;
    }

    public  boolean contains(T data) {
        if(head == null)
            return false;

        if(head.data == data) {
            return true;
        }

        if(tail.data == data) {
            return true;
        }

        Node current = head;

        while(current != null) {
            if(current.data == data) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    public T removeHead() {
        if(head == null) {
            return null;
        }

        T removedData = head.data;

        head = head.next;

        if(head == null) {
            tail = null;
        } else {
            head.prev = null;
        }
        size--;
        return removedData;
    }

    public T removeTail() {
        if(tail == null) {
            return null;
        }
        if(tail.prev == null) {
            return null;
        }
        T removedData = tail.data;
        tail = tail.prev;
        if(tail == null) {
            head = null;
        } else {
            tail.next = null;
        }
        size--;
        return removedData;
    }

    public T peekHead() {
        if(head == null)
            return null;

        return head.data;
    }

    public T peekTail() {
        if(tail == null)
            return null;

        return tail.data;
    }

    public T pollHead() {
        if(head == null)
            return null;

        T polledData = head.data;

        head = head.next;

        if(head == null) {
            tail = null;
        } else {
            head.prev = null;
        }
        size--;

        return polledData;
    }

    @Override
    public T pollTail() {
        if(tail == null) {
            return null;
        }
        T pollData = tail.data;

        tail = tail.prev;

        if(tail == null)
            head = null;
        else {
            tail.next = null;
        }

        size--;
        return pollData;
    }

    public T pop() {
        if(tail == null)
            return null;

        T popedData = tail.data;

        tail = tail.prev;

        if(tail == null)
            head = null;
        else {
            tail.next = null;
        }
        size--;
        return popedData;
    }

    public int size() {
        return size;
    }
    public void printDequq() {
        System.out.println("Printing the deque of size: "+size());
        if (head == null) {
            System.out.println("Dequq is empty.");
        }
        Node current = head;
        while(current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }

}

package com.deque;

public class TestDeque{
    public static void main(String arg[]) {
        MyDeque deque = new MyDequeImpl<>();
        deque.addHead("cat");
        deque.printDequq();
        deque.addHead("dog");
        deque.printDequq();
        deque.addHead("rabbit");
        deque.printDequq();
        deque.addHead("elephant");
        deque.printDequq();
        deque.addTail("squirrel");
        deque.printDequq();

        System.out.println("=============");
        System.out.println(deque.getHead());
        System.out.println(deque.getTail());
        System.out.println(deque.contains("monkey"));
        System.out.println(deque.contains("rabbit"));
        System.out.println(deque.removeHead());
        System.out.println(deque.removeTail());
        System.out.println("=======");

        System.out.println(deque.getHead());
        System.out.println(deque.getTail());
        System.out.println("=======");
        System.out.println(deque.peekHead());
        System.out.println(deque.peekTail());
        System.out.println("========");
        System.out.println(deque.pollHead());
        System.out.println(deque.pollTail());
        deque.printDequq();

        System.out.println("========");
        System.out.println(deque.pop());
        deque.printDequq();

        deque.addHead("birds");

        deque.printDequq();
    }
}