Double Ended Queue using Array

 

What is a Double Ended Queue (Deque)?

A Deque  stands for Double Ended Queue.
It is a linear data structure in which insertion and deletion operations can be performed from both front and rear ends.

🔵 Unlike a simple queue (where insert at rear and delete from front only), in Deque:

  • Insert front ✅

  • Insert rear ✅

  • Delete front ✅

  • Delete rear ✅

Types of Deques

There are two common types:

  1. Input Restricted Deque

    • Insertion at only one end .

    • Deletion from both ends.


  2. Output Restricted Deque

    • Deletion at only one end.

    • Insertion from both ends.


Basic Operations in a General Deque:

OperationDescription
Insert Front        Insert an element at the front end.
Insert Rear        Insert an element at the rear end.
Delete Front        Delete an element from the front end.
Delete Rear        Delete an element from the rear end.
Peek Front        Get the front element without removing it.
Peek Rear        Get the rear element without removing it.
isFull()        Check if the deque is full.
isEmpty()        Check if the deque is empty.




Algorithms (assuming circular array with front = -1, rear = -1 initially)

Algorithm Initialize Deque
    front = -1
    rear= -1


Algorithm for isEmpty()

1. If front ==-1 AND  rear== -1
       Return TRUE
2. Else
       Return FALSE

 Algorithm for isFull()

1. If (rear + 1) mod MAX = front then
      Return TRUE
2. Else
      Return FALSE


Algorithm for Insert Front-x is the element to be inserted

1. If Deque is Full
      Output "Deque Overflow"
      Exit
2. If Deque is Empty
      Set front ← 0
      Set rear ← 0
3. Else
     if front==0
        front=MAX-1
     else
      front ← front - 1 
4. Set deque[front] ← x


Algorithm for Insert Rear

1. If Deque is Full
      Output "Deque Overflow"
      Exit
2. If Deque is Empty
      Set front ← 0
      Set rear ← 0
3. Else
      Set rear ← (rear + 1) mod MAX
4. Set deque[rear] ← item


Algorithm for Delete Front

1. If Deque is Empty
      Output "Deque Underflow"
      Exit
2. Output deque[front] as deleted element
3. If front = rear
      Set front ← -1
      Set rear ← -1
4. Else
      Set front ← (front + 1) mod MAX

Algorithm for Delete Rear

1. If Deque is Empty
      Output "Deque Underflow"
      Exit
2. Output deque[rear] as deleted element
3. If front = rear
      Set front ← -1
      Set rear ← -1
4. Else
     if rear==0
         rear=MAX-1
    else
         rear ← rear - 1 

Display Deque Elements
1. If Deque is Empty
      Output "Deque is empty"
      Exit
2. Set i ← front
3. Repeat
      Output deque[i]
      Set i ← (i + 1) mod MAX
       if  i==rear
                break

Peek Front Element
1. If front = -1 then
      Output "Deque is empty"
      Exit
2. Else
      Output deque[front] as the front element

Peek Rear Element
1. If rear = -1 then
      Output "Deque is empty"
      Exit
2. Else
      Output deque[rear] as the rear element


Note:

  • Wrapping is handled using % MAX (modulus operator).

  • In Deque, we can move front and rear both ways (increment/decrement).

  • You can design Deque using Arrays (fixed size) or Linked Lists (dynamic size).

C Program Double Ended Queue using array
#include <stdio.h>
#include <stdlib.h>

#define MAX 5

int deque[MAX];
int front = -1, rear = -1;

// Function to check if deque is full
int isFull() {
    return ((rear + 1) % MAX == front);
}

// Function to check if deque is empty
int isEmpty() {
    return (front == -1);
}

// Insert element at front
void insertFront(int item) {
    if (isFull()) {
        printf("Deque Overflow! Cannot insert at front.\n");
        return;
    }
    if (isEmpty()) {
        front = rear = 0;
    } else {           //front = (front - 1 + MAX) % MAX; you can also use this
     if (front==0)
          front=MAX-1;
    else
        front=front-1;
       
    }
    deque[front] = item;
    printf("Inserted %d at front.\n", item);
}

// Insert element at rear
void insertRear(int item) {
    if (isFull()) {
        printf("Deque Overflow! Cannot insert at rear.\n");
        return;
    }
    if (isEmpty()) {
        front = rear = 0;
    } else {
        rear = (rear + 1) % MAX;
    }
    deque[rear] = item;
    printf("Inserted %d at rear.\n", item);
}

// Delete element from front
void deleteFront() {
    if (isEmpty()) {
        printf("Deque Underflow! Cannot delete from front.\n");
        return;
    }
    printf("Deleted element from front: %d\n", deque[front]);
    if (front == rear) {
        front = rear = -1; // Only one element was present
    } else {
        front = (front + 1) % MAX;
    }
}

// Delete element from rear
void deleteRear() {
    if (isEmpty()) {
        printf("Deque Underflow! Cannot delete from rear.\n");
        return;
    }
    printf("Deleted element from rear: %d\n", deque[rear]);
    if (front == rear) {
        front = rear = -1; // Only one element was present
    } else {     // rear = (rear - 1 + MAX) % MAX; you can also use this
       if (rear==0)
          rear=MAX-1;
       else
           rear=rear-1;
    }
}

// Display deque elements
void display() {
    int i;
    if (isEmpty()) {
        printf("Deque is empty.\n");
        return;
    }
    printf("Deque elements: ");
    i = front;
    while (1) {
        printf("%d ", deque[i]);
        if (i == rear)
            break;
        i = (i + 1) % MAX;
    }
    printf("\n");
}

// Main function
int main() {
    int choice, item;
    while (1) {
        printf("\n***** MENU *****\n");
        printf("1. Insert Front\n");
        printf("2. Insert Rear\n");
        printf("3. Delete Front\n");
        printf("4. Delete Rear\n");
        printf("5. Display\n");
        printf("6. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                printf("Enter the element to insert at front: ");
                scanf("%d", &item);
                insertFront(item);
                break;
            case 2:
                printf("Enter the element to insert at rear: ");
                scanf("%d", &item);
                insertRear(item);
                break;
            case 3:
                deleteFront();
                break;
            case 4:
                deleteRear();
                break;
            case 5:
                display();
                break;
            case 6:
                printf("Exiting program.\n");
                exit(0);
            default:
                printf("Invalid choice! Please try again.\n");
        }
    }
    return 0;
}




Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more