// Program 57: Insert and Delete Elements in a Deque

import java.util.*;

class DeQueue
{
    int size = 5;
    int[] ar = new int[size];
    int front = -1;
    int rear = -1;

    void insertFront(int value)
    {
        if (front == 0)
        {
            System.out.println("Deque overflow at front");
        }
        else if (front == -1)
        {
            front = 0;
            rear = 0;
            ar[front] = value;
        }
        else
        {
            front--;
            ar[front] = value;
        }
    }

    void insertRear(int value)
    {
        if (rear == size - 1)
        {
            System.out.println("Deque overflow at rear");
        }
        else if (rear == -1)
        {
            front = 0;
            rear = 0;
            ar[rear] = value;
        }
        else
        {
            rear++;
            ar[rear] = value;
        }
    }

    void deleteFront()
    {
        if (front == -1)
        {
            System.out.println("Deque underflow");
        }
        else
        {
            System.out.println("Deleted from front: " + ar[front]);

            if (front == rear)
            {
                front = -1;
                rear = -1;
            }
            else
            {
                front++;
            }
        }
    }

    void deleteRear()
    {
        if (rear == -1)
        {
            System.out.println("Deque underflow");
        }
        else
        {
            System.out.println("Deleted from rear: " + ar[rear]);

            if (front == rear)
            {
                front = -1;
                rear = -1;
            }
            else
            {
                rear--;
            }
        }
    }

    void display()
    {
        if (front == -1)
        {
            System.out.println("Deque is empty");
        }
        else
        {
            System.out.println("Deque elements:");
            for (int i = front; i <= rear; i++)
            {
                System.out.println(ar[i]);
            }
        }
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        DeQueue q = new DeQueue();
        int choice;

        do
        {
            System.out.println("1. Insert front");
            System.out.println("2. Insert rear");
            System.out.println("3. Delete front");
            System.out.println("4. Delete rear");
            System.out.println("5. Display");
            System.out.println("6. Exit");
            System.out.print("Enter choice: ");
            choice = sc.nextInt();

            if (choice == 1)
            {
                System.out.print("Enter value: ");
                q.insertFront(sc.nextInt());
            }
            else if (choice == 2)
            {
                System.out.print("Enter value: ");
                q.insertRear(sc.nextInt());
            }
            else if (choice == 3)
            {
                q.deleteFront();
            }
            else if (choice == 4)
            {
                q.deleteRear();
            }
            else if (choice == 5)
            {
                q.display();
            }
            else if (choice != 6)
            {
                System.out.println("Invalid choice");
            }
        }
        while (choice != 6);
    }
}