Double Ended Queue (Deque) using C Programming - BunksAllowed

BunksAllowed

BunksAllowed is an effort to facilitate Self Learning process through the provision of quality tutorials.

Community

Join WhatsApp Grpup using https://chat.whatsapp.com/EAcqRurEOXb52Ax7Tlmj9I

  • Home
    • demo-image
    Home Data Structures Technology Double Ended Queue (Deque) using C Programming

    Double Ended Queue (Deque) using C Programming

    Share This

    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.

    dequeue
    Deque implementation using Linked List
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    #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;
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
    Deque implementation using Array
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    #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:");
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

    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
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    #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;
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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


    Happy Exploring!

    Tags
    Share This
    bunksAllowed

    About BunksAllowed

    Newer Article Heap Data Structure using C Programming Older Article Circular Queue using Array in C Programming
    By on
    Labels: ,
    Subscribe to: Post Comments (Atom)
    Comment Using!!

    No comments:

    Post a Comment

    Note: Only a member of this blog may post a comment.

    About BunksAllowed