Question

Using C++, create a doubly linked list data structure that stores strings. At a minimum, you must have a List class that contains the list functionality (including an insert function) and a linkable object ("link node") class. For convenience, you may include the data directly or the data may be external to the link node, connected with a reference. You may use an inner class for the LinkNode and/or include the LinkNode class with the List class file if you wish. Your list must have functions to both insert and remove (and return) values from both the front and end of the list. Use of a "standard container" (such as an STL class, Vector, or ArrayList) is not permitted.

Using composition (with the List class,) define a Queue class that has enque and deque functions, as well as an isEmpty function.

(Each of your classes may have any additional functionality that you deem necessary)

Write a main function that will read an unspecified number (until EOF) of input strings (each string may include whitespace and is terminated with a newline) from STDIN. Enque each string into your Queue. After you have read all of the input, deque each string from your Queue, printing it to STDOUT (one per line) until the Queue us empty. Your program should have no other output.

Answer 1

Hi, here is the code. Try it and let me know if you need any changes.

Source & Screens: List.h & List.cpp

#ifndef LIST_H_ #define LIST_H_ #include <string> using namespace std; class List { private:    class LinkNode    {    public:        string data;        LinkNode * prev;        LinkNode * next;    }; public:    LinkNode * head;    LinkNode * tail;    List();    void insertFirst(string);    void insertLast(string);    string removeFirst();    string removeLast(); }; #endif /* LIST_H_ */

/* * List.cpp * * Created on: Feb 5, 2020 * Author: Casper */ #include "List.h" List::List() {    this->head = nullptr;    this->tail = nullptr; } void List::insertFirst(string data) {    // create a new LinkNode    LinkNode * newNode = new LinkNode();    // set data member    newNode->data = data;    // set head node as right    newNode->next = head;    // if head is not null    if(head != nullptr){        // set previous of head as newNode        head->prev = newNode;    }    if(tail == nullptr)    {        tail = newNode;    }    // set newNode as head    head = newNode; } void List::insertLast(string data) {    // create a new LinkNode    LinkNode * newNode = new LinkNode();    // set data member    newNode->data = data;    // set head node as right    newNode->prev = tail;    // if tail is not null    if(tail != nullptr){        // set next of tail as newNode        tail->next = newNode;    }    if(head == nullptr)    {        head = newNode;    }    // set newNode as head    tail = newNode; } string List::removeFirst() {    // assign head node to tempNode    LinkNode * tempNode = head;    head = head->next;    if(head != nullptr)    {        // set previous of head to null        head->prev = nullptr;    }    else    {        tail = nullptr;    }    // retrun data    return tempNode->data; } string List::removeLast() {    // assign head node to tempNode    LinkNode * tempNode = tail;    tail = tail->prev;    if(tail!=nullptr)    {        // set previous of head to null        tail->next = nullptr;    }    else    {        head = nullptr;    }    // retrun data    return tempNode->data; }

Source & Screens: Queue.H & Queue.cpp

#ifndef QUEUE_H_ #define QUEUE_H_ #include "List.h" class Queue {    List list; public:    Queue();    void enque(string);    string deque();    bool isEmpty(); }; #endif /* QUEUE_H_ */

#include "Queue.h" Queue::Queue() { } void Queue::enque(string data) {    list.insertLast(data); } string Queue::deque() {    return list.removeFirst(); } bool Queue::isEmpty() {    return list.head == nullptr; }

Source & Screens: TestQueue.cpp

#include "Queue.h" Queue::Queue() { } void Queue::enque(string data) {    list.insertLast(data); } string Queue::deque() {    return list.removeFirst(); } bool Queue::isEmpty() {    return list.head == nullptr; }