Question

In C++: Provide a linked implementation of a deque and name it LinkedDeque (use singly linked list). It can be a template/generic class or you can set it up with a certain data type. Use a test driver to try out your LinkedDeque by adding and removing values from both ends.

Answer 1

#######################################
           Deque.cpp
#######################################
#include "Deque.h"

using namespace std;

Deque::Deque() {
        head = NULL;
        tail = NULL;
}

void Deque::createNode(node* &x, int value) {
        x = new node;
        x->data = value;
        x->next = NULL;
}

void Deque::push(int value) {
        // create a new node
        node *x;
        createNode(x, value);
        x->next = head;
        
        // if list is originally empty
        if(head == NULL) {
                tail = x;
        }
        head = x;
}

void Deque::inject(int value) {
        // create a new node
        node *x;
        createNode(x, value);
        
        // if list is originally empty
        if(head == NULL) {
                head = x;
                tail = x;
        } else {
                tail->next = x;
                tail = x;
        }
}

int Deque::pop(){
        int data = -1;
        // check if list is not empty
        if(head != NULL) {
                node *x = head;

                // update head pointer
                head = head->next;
                if(head == NULL) {
                        tail = NULL;
                }
                data = x->data;
                delete x;
        }
        return data;
}

int Deque::eject() {
        int data = -1;
        // check if list is not empty
        if(head != NULL) {
                node *x = head;

                // check if list has only one node
                if(x == tail) {
                        data = x->data;
                        delete x;
                        head = tail = NULL;                     
                } else {
                        // move to second last node
                        while(x->next != tail) {
                                x = x->next;
                        }
                        data = tail->data;
                        delete tail;
                        tail = x;
                        tail->next = NULL;
                }
        }
        return data;
}

void Deque::printQueue() {
        node *x = head;

        // till all nodes are not traversed
        while(x != NULL) {
                cout << x->data << " ";
                x = x->next;
        }
        cout << endl;
}



#######################################
             Deque.h
#######################################
#pragma once
#include <iostream>

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

class Deque {
        private:
        node *head;
        node *tail;
        void createNode(node* &x, int value);

        public:
        Deque();
        void push(int value);
        void inject(int value);
        int pop();
        int eject();
        void printQueue();
};



#######################################
            main.cpp
#######################################
#include <iostream>
#include "Deque.h"

using namespace std;

int main() {
        Deque d;

        d.push(1);
        d.push(2);
        d.push(3);
        d.push(4);
        d.push(5);

        cout << "After pushing values from 1 to 5: ";
        d.printQueue();

        d.inject(1);
        d.inject(2);
        d.inject(3);
        d.inject(4);
        d.inject(5);

        cout << "After injecting values from 1 to 5: ";
        d.printQueue();

        cout << "The front element popped out: " << d.pop() << endl;
        cout << "The front element ejected out: " << d.eject() << endl;
        cout << "The front element popped out: " << d.pop() << endl;
        cout << "The front element ejected out: " << d.eject() << endl;
}

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.