Double Ended Queue

A double-ended queue, often abbreviated as deque, is a data structure that allows insertion and deletion of elements from both ends, front and rear. It is also sometimes referred to as an "deque".Deques can be thought of as a generalization of stacks and queues because it supports the operations of both.

Here are some key characteristics and operations associated with double-ended queues:

Unlike a regular queue, a deque allows insertion and deletion at both ends.


Types of Deque
Input Restricted Deque
In this deque, input is restricted at a single end but allows deletion at both the ends.
Output Restricted Deque
In this deque, output is restricted at a single end but allows insertion at both the ends.

Operations:
Enqueue Front: Add an element to the front of the deque.
Enqueue Rear: Add an element to the rear of the deque.
Dequeue Front: Remove and return an element from the front of the deque.
Dequeue Rear: Remove and return an element from the rear of the deque.


Applications:
Deques are useful in scenarios where elements need to be efficiently added or removed from both ends.
They can be used in algorithms that require access to elements at the beginning and end of a sequence.
Task scheduling, Memory management etc....

Implementation:
Deques can be implemented using arrays or linked lists. The choice of implementation depends on the specific requirements and the expected operations' time complexity.

Complexity:
The time complexity for inserting or removing an element from either end of a deque is O(1) in most implementations.

Implementing a double-ended queue (deque) using a circular array involves keeping track of both front and rear pointers and managing the circular nature of the array. Here's a step-by-step algorithm for each deque operation:

1. Initialization:
Algorithm InitializeDeque(size):
    Initialize front and rear pointers to -1 (indicating an empty deque).
    Set the size of the array to the given size.
2. Enqueue at the Front:
Algorithm EnqueueFront(deque, element):
    1. If the deque is full, return Queue is Full.
    2. If the deque is empty, set both front and rear pointers to 0. else
    3. Decrement the front pointer (wrap around if necessary based on the circular nature).
    4. Set the value of the element at the front pointer to the given element.
3. Enqueue at the Rear:
Algorithm EnqueueRear(deque, element):
    1. If the deque is full, return Queue is Full.
    2. If the deque is empty, set both front and rear pointers to 0. else
    3. Increment the rear pointer (wrap around if necessary based on the circular nature).
    4. Set the value of the element at the rear pointer to the given element.
4. Dequeue from the Front:
Algorithm DequeueFront(deque):
    1. If the deque is empty, return  underflow.
    2. Retrieve the value of the element at the front pointer.
    3. If front is equal to rear, set both front and rear pointers to -1 (indicating an empty deque). else
    4. Increment the front pointer (wrap around if necessary based on the circular nature).
    5. Return the retrieved value.
5. Dequeue from the Rear:
Algorithm DequeueRear(deque):
    1. If the deque is empty, return an error  underflow.
    2. Retrieve the value of the element at the rear pointer.
    3. If front is equal to rear, set both front and rear pointers to -1 (indicating an empty deque).else
    4. Decrement the rear pointer (wrap around if necessary based on the circular nature).
    5. Return the retrieved value.

C Program- Double ended queue using arrays
/***********************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define MAX 10
 
int deque_arr[MAX];
int front=-1;
int rear=-1;
 
void insertFront(int item);
void insertRear(int item);
int deleteFront();
int deleteRear();
void display();
int isEmpty();
int isFull();
 
int main()
{
        int choice,item;
        while(1)
        {
                printf("\n\n1.Insert at the front end\n");
                printf("2.Insert at the rear end\n");
                printf("3.Delete from front end\n");
                printf("4.Delete from rear end\n");
                printf("5.Display\n");
                printf("6.Quit\n");
                printf("\nEnter your choice : ");
                scanf("%d",&choice);
 
                switch(choice)
                {
                case 1:
                        printf("\nInput the element for adding in queue : ");
                        scanf("%d",&item);
                        insertFront(item);
                        break;
                case 2:
                        printf("\nInput the element for adding in queue : ");
                        scanf("%d",&item);
                        insertRear(item);
                        break;
                 case 3:item=deleteFront();
                        if(item!=-1)
                            printf("\nElement deleted from front end is : %d\n",item);
                        break;
                 case 4:
                        item=deleteRear();
                        if(item!=-1)
                            printf("\nElement deleted from rear end is : %d\n",item);
                        break;
                 case 5:
                        display();
                        break;
                 case 6:
                        exit(1);
                 default:
                        printf("\nWrong choice\n");
                }/*End of switch*/
                printf("\nfront = %d, rear =%d\n", front , rear);
                display();
        }/*End of while*/
}/*End of main()*/
 
void insertFront(int item)
{
        if( isFull() )
        {
                printf("\nQueue Overflow\n");
                return;
        }
        if( front==-1 )/*If queue is initially empty*/
        {
                front=0;
                rear=0;
        }
        else if(front==0)
                front=MAX-1;
        else
                front=front-1;
        deque_arr[front]=item ;
}/*End of insert_frontEnd()*/
 
void insertRear(int item)
{
        if( isFull() )
        {
                printf("\nQueue Overflow\n");
                return;
        }
        if(front==-1)  /*if queue is initially empty*/
        {
                front=0;
                rear=0;
        }
        else if(rear==MAX-1)  /*rear is at last position of queue */
                rear=0;
        else
                rear=rear+1;
        deque_arr[rear]=item ;
}/*End of insert_rearEnd()*/
 
int deleteFront()
{
        int item;
        if( isEmpty() )
        {
                printf("\nQueue Underflow\n");
                return -1;
        }
        item=deque_arr[front];
        if(front==rear) /*Queue has only one element */
        {
                front=-1;
                rear=-1;
        }
        else
                if(front==MAX-1)
                        front=0;
                else
                        front=front+1;
        return item;
}/*End of deleteFront()*/
 
int deleteRear()
{
        int item;
        if( isEmpty() )
        {
                printf("\nQueue Underflow\n");
                return -1;
        }
        item=deque_arr[rear];
 
        if(front==rear) /*queue has only one element*/
        {
                front=-1;
                rear=-1;
        }
        else if(rear==0)
                rear=MAX-1;
        else
                rear=rear-1;
        return item;
}/*End of delete_rearEnd() */
 
int isFull()
{
        if ( (front==0 && rear==MAX-1) || (front==rear+1) )
                return 1;
        else
                return 0;
}/*End of isFull()*/
 
int isEmpty()
{
        if( front == -1)
                return 1;
        else
                return 0;
}/*End of isEmpty()*/
 
void display()
{
        int i;
        if( isEmpty() )
        {
                printf("\nQueue is empty\n");
                return;
        }
        printf("\nQueue elements :\n");
        i=front;
        if( front<=rear )
        {
                while(i<=rear)
                        printf("%d ",deque_arr[i++]);
        }
        else
        {
                while(i<=MAX-1)
                        printf("%d ",deque_arr[i++]);
                i=0;
                while(i<=rear)
                        printf("%d ",deque_arr[i++]);
        }
        printf("\n");
}/*End of display() */


Here are step-by-step algorithms for the basic operations of a double-ended queue (deque) using linked list
1. Initialization:
Algorithm InitializeDeque():
    Create an empty data structure to represent the deque.
    Initialize front and rear pointers.
2. Enqueue at the Front:
Algorithm EnqueueFront(deque, element):
    1. Create a new node or allocate memory for the new element.
    2. Set the value of the new node to the given element.
    3. If the deque is empty, set both front and rear pointers to the new node.
    4. If the deque is not empty, set the "next" pointer of the new node to the current front.
    5. Update the front pointer to the new node.
3. Enqueue at the Rear:
Algorithm EnqueueRear(deque, element):
    1. Create a new node or allocate memory for the new element.
    2. Set the value of the new node to the given element.
    3. If the deque is empty, set both front and rear pointers to the new node.
    4. If the deque is not empty, set the "next" pointer of the current rear to the new node.
    5. Update the rear pointer to the new node.
4. Dequeue from the Front:
Algorithm DequeueFront(deque):
    1. If the deque is empty, return an error or a special value to indicate underflow.
    2. Retrieve the value of the front node.
    3. If the deque has only one element, set both front and rear pointers to null.
    4. If the deque has more than one element, update the front pointer to the next node.
    5. Return the retrieved value.
5. Dequeue from the Rear:
Algorithm DequeueRear(deque):
    1. If the deque is empty, return an error or a special value to indicate underflow.
    2. Retrieve the value of the rear node.
    3. If the deque has only one element, set both front and rear pointers to null.
    4. If the deque has more than one element, traverse the deque to find the second-to-last node.
    5. Set the "next" pointer of the second-to-last node to null, and update the rear pointer to the
       second-to-last node.
    6. Return the retrieved value.

C Program- double ended queue using linked list
/*********************************************************************/
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

struct Node* front = NULL;
struct Node* rear = NULL;

void insertFront(int x) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->next = front;
    front = newNode;
    if (rear == NULL) {
        rear = front;
    }
}

void insertRear(int x) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->next = NULL;
    if (rear == NULL) {
        front = rear = newNode;
            }
    else{
    rear->next = newNode;
    rear = newNode;
    }
}

int deleteFront() {
    if (front == NULL) {
        printf("Queue is Empty\n");
        return -1;
    }
    struct Node* temp = front;
    int x=front->data;
    front = front->next;
    if (front == NULL) {
        rear = NULL;
    }
    free(temp);
    return(x);
}

int deleteRear() {
    int x;
    if (rear == NULL) {
        printf("Queue is Empty\n");
        return -1;
    }
    if (front==rear)
        {
            struct Node* temp = rear;
            x=rear->data;
            front=rear=NULL;
            free(temp);
            return x;
        }
    struct Node* temp = front;
    while (temp->next != rear) {
        temp = temp->next;
    }
    x=rear->data;
    rear = temp;
    rear->next = NULL;
    temp=temp->next;
    free(temp);
    return x;
}

void display() {
    if (front == NULL) {
        printf("Queue is Empty\n");
        }
    else{
    struct Node* temp = front;
    while (temp != NULL) {
        printf("%d-->", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
    }
}

int main() 
{
     int choice,item;
        while(1)
        {
                printf("\n\n1.Insert at the front end\n");
                printf("2.Insert at the rear end\n");
                printf("3.Delete from front end\n");
                printf("4.Delete from rear end\n");
                printf("5.Display\n");
                printf("6.Quit\n");
                printf("\nEnter your choice : ");
                scanf("%d",&choice);
 
                switch(choice)
                {
                case 1:
                        printf("\nInput the element for adding in queue : ");
                        scanf("%d",&item);
                        insertFront(item);
                        break;
                case 2:
                        printf("\nInput the element for adding in queue : ");
                        scanf("%d",&item);
                        insertRear(item);
                        break;
                 case 3:
                        item=deleteFront();
                        if(item!=-1)
                        printf("\nElement deleted from front end is : %d\n",item);
                        break;
                 case 4:
                        item=deleteRear();
                        if(item!=-1)
                        printf("\nElement deleted from rear end is : %d\n",item);
                        break;
                 case 5:
                        display();
                        break;
                 case 6:
                        exit(1);
                 default:
                        printf("\nWrong choice\n");
                }/*End of switch*/
               
        }/*End of while*/
}/*End of main()*/


Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more