Program opened below. You can scroll through the algorithm, Java code and output.
Program 57
Insert and Delete Elements in a Deque
Question
Implement deque operations using an array, including insertion and deletion at the ends and display.
Algorithm
Step 1: Start the program and declare a fixed-size array for the deque.
Step 2: Initialise front and rear to -1 to indicate an empty deque.
Step 3: Display a menu for insertion, deletion, display and exit.
Step 4: Accept the user's choice.
Step 5: For insertion at the rear, check whether the rear has reached the final array index.
Step 6: If the deque is empty, set front and rear to zero; otherwise increment rear.
Step 7: Store the new value at the rear position.
Step 8: For deletion at the front, check whether the deque is empty.
Step 9: If it is empty, display an underflow message; otherwise display the front value.
Step 10: If front equals rear, reset both pointers; otherwise increment front.
Step 11: For display, print the elements from front to rear, each on a separate line.
Step 12: Repeat the menu until EXIT is selected, then stop.
Java program
Javaimport 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);
}
}Sample output
Input: Insert rear 5; insert rear 9; display
Output: Deque elements:
5
9