Double Ended Queue (Deque) using C Programming

Another type variant of a queue is Dequeue. In a dequeue, both insertion and deletion operations are performed at either end of the queue which is shown in the following Fig 1. In this topic, we will give the algorithms both for insertion as well as deletion. Later the c-code and output are given for clear understanding.

Deque implementation using Linked List

#include<stdio.h> #include<stdlib.h> typedef struct Node { int data; struct Node *next; } node; typedef struct { node *front; node *rear; } queue; void createQueue(queue *q); int isEmpty(queue *q); void enqueue_at_rear(queue *q, int data); int dequeue_from_front(queue *q ); int main() { queue q; int choice, data; createQueue(&q); while (1) { printf("Main Menu\n 1. Enter data in queue\n 2. Delete from queue\n 0. Exit\n"); scanf("%d", &choice); switch (choice) { case 1: printf("Enter the data: "); scanf("%d", &data); enqueue_at_rear(&q, data); break; case 2: if(isEmpty(&q)) printf("The queue is empty!\n"); else{ data = dequeue_from_front(&q); printf("The dequeued element is %d\n", data); } break; case 0: exit(0); default: printf("Invalid choice\n"); } } return 0; } void createQueue(queue *q) { q->front = q->rear = NULL; } int isEmpty(queue *q) { if(q->front == NULL) return 1; else return 0; } void enqueue_at_rear(queue *q, int data) { node *ptr; ptr = malloc(sizeof(struct Node)); ptr->data = data; ptr->next = NULL; if (q->rear == NULL) { q->front = q->rear = ptr; } else { (q->rear)->next = ptr; q->rear = ptr; } } int dequeue_from_front(queue *q ) { int data; node *ptr; data = (q->front)->data; ptr = q->front; if (q->front == q->rear) q->front = q->rear = NULL; else q->front = (q->front)->next; free(ptr); return data; }

Deque implementation using Array

#include <stdio.h> #define SIZE 5 typedef struct Queue { int front, rear; int data[SIZE]; } queue; void createQueue(queue *q); int isFull(queue *q); int isEmpty(queue *q); void enqueue_at_rear(queue *q, int data); int dequeue_from_front(queue *q); int main(void) { int choice, data; queue q; createQueue(&q); while(1) { printf("\nChoices:"); printf("\n 1: enqueue at rear"); printf("\n 2: dequeue from front"); printf("\n 3: enqueue at front"); printf("\n 4: dequeue from rear"); printf("\n 0: exit"); printf("\nEnter your choice:"); scanf("%d", &choice); switch(choice) { case 1: printf("\nEnter an element:"); scanf("%d", &data); enqueue_at_rear(&q, data); break; case 2: data = dequeue_from_front(&q); if(data != -1) printf("\nThe dequeued element is :%d", data); break; case 0: exit(0); default: printf("\nInvalid choice"); } } } void createQueue(queue *q) { q->front = -1; q->rear = -1; } int isEmpty(queue *q) { if(q->front == -1) return 1; else return 0; } int isFull(queue *q) { if((q->front == 0) && (q->rear == SIZE - 1)) return 1; else return 0; } void enqueue_at_rear(queue *q, int data) { int i; if(isFull(q)) { printf("\nQueue is full"); return; } if(q->front == -1) { q->front = q->rear = 0; } else if((q->rear == SIZE - 1) && (q->front != 0)) { for(i = q->front; i <= q->rear; i++) q->data[i - q->front] = q->data[i]; q->rear = q->rear - q->front + 1; q->front = 0; } else q->rear++; q->data[q->rear] = data; } int dequeue_from_front(queue *q) { int data; if(isEmpty(q)) { printf("\nQueue is empty"); return -1; } data = q->data[q->front]; if(q->front == q->rear) { q->front = q->rear = -1; } else q->front++; return data; }

---

Input-Output Restricted Queue

---

It is a variant of dequeue. In case of input-restricted we can insert the element in queue in normal fashion means as we insert the elements in normal queue from the rear end. So only one type of insertion is possible in this case i.e. insert from rear end but we can delete from the both end of the queue. Now in case of insertion(insertion from rear end) insert the element and place it at proper position. Initially when queue is empty(front=-1 and rear=-1)we first increment the rear position by one and place the element at the first position. Set front=0 for the rest of the insertion from rear end.This is shown in following figure.Initially the queue is empty with front=-1 and rear=-1.

Source code of the above procedure is given below.

Input-Output Restricted queue Using C

#include <stdio.h> #define MAX 5 int delStart(); int delEnd(); int queue[MAX]; int rear =-1, front =-1; void display(); void insertEnd(); void insertStart(); void insertEnd() { int token; if(rear==MAX-1) { printf("\nQueue full"); return; } else if(rear==-1) { front=0; printf("\nEnter the number to be inserted:"); scanf("%d",&token); rear=rear+1; queue[rear]=token; } else { printf("\nEnter the number to be inserted:"); scanf("%d",&token); rear=rear+1; queue[rear]=token; } } void insertStart() { int token,i; if(rear==MAX-1) { printf("\nQueue full"); return; } else if(rear==-1) { front=front+1; printf("\nEnter the number to be inserted:"); scanf("%d",&token); queue[front]=token; rear=rear+1; } else if(rear!=-1 && rear < MAX-1) { for(i=rear;i>=0;i--) { queue[i+1]=queue[i]; } printf("\nEnter the number to be inserted:"); scanf("%d",&token); queue[0]=token; front=0; rear=rear+1; } } int delEnd() { int t; if((front==-1 && rear==-1) ||(front==rear+1)) { printf("\nQueue empty"); return 0; } t=queue[rear]; printf("%d is deleted",t); rear=rear-1; return t; } int delStart() { int t,i; if((front==-1 && rear==-1) || (front==rear+1)) { printf("\nQueue empty"); return 0; } else { t=queue[front]; printf("%d is deleted",t); front=front+1; for(i=front;i<=rear;i++) { queue[i-1]=queue[i]; } front=0; rear=rear-1; //printf("\nfront=%d rear=%d",front,rear); } return t; } void display() { int i; printf("\nThe queue elements are:"); for(i=front;i<=rear;i++) { printf("%d ",queue[i]); } } int input_restricted_que() { int choice; while(1) { printf("\n1.insert from rear"); printf("\n2.delete from front"); printf("\n3.delete from rear"); printf("\n4.display"); printf("\n5.exit"); printf("\nenter the choice:"); scanf("%d",&choice); switch(choice) { case 1:insertEnd(); break; case 2:delStart(); break; case 3:delEnd(); break; case 4:display(); break; case 5:return 0; } } } int output_restricted_que() { int choice; while(1) { printf("\n1.insert from rear"); printf("\n2.insert from front"); printf("\n3.delete from front"); printf("\n4.display"); printf("\n5.exit"); printf("\nenter the choice:"); scanf("%d",&choice); switch(choice) { case 1:insertEnd(); break; case 2:insertStart(); break; case 3:delStart(); break; case 4:display(); break; case 5:return 0; } } } int main() { int ch; while(1) { printf("\n1.Input-restricted queue"); printf("\n2.Output-restricted queue"); printf("\n3.Exit"); printf("\n enter your choice:"); scanf("%d",&ch); switch(ch) { case 1:input_restricted_que(); break; case 2:output_restricted_que(); break; case 3:return 0; } } return 0; }

Hope, readers will understand this method and it will be helpful for them.

Happy Exploring!