Question

Programming Project – Deques, Stacks & Queues

General Description:

Design and develop array based and linked list-based implementations for the Dequeue ADT. Your implementation must support generic data types using C++ templates. Develop Adapter Files to provide Stack and Queue functionality for the Deques.

Definitions:

You should implement the ADTs precisely as described in the following partial header files.

Deque.h

template

class Deque {

public:

        Deque();                    //constructor

        ~Deque();                 //destructor

        void insertFront(const E& e);

        void insertBack(const E& e);

        const E& eraseFront(); // throw(DequeEmpty);        //note that the use of exceptions is optional

        const E& eraseBack(); // throw(DequeEmpty);        //note that the use of exceptions is optional

        const E& front() const; // throw(DequeEmpty);        //note that the use of exceptions is optional

        const E& back() const; // throw(DequeEmpty);        //note that the use of exceptions is optional

        int size () const;

        bool empty() const;

}

You will also need header files for the Stack and Queue ADT’s for each implementation:

Stack.h

template

class Stack {

public:

        Stack();                      //constructor

                                     ~Stack();                                         //destructor

        void push(const E& e);

        const E& pop(); // throw(StackEmpty);        //note that the use of exceptions is optional

        const E& top() const; // throw(StackEmpty);        //note that the use of exceptions is optional

        int size () const;

        bool empty() const;

}

Queue.h

template

class Queue {

public:

        Queue();                    //constructor

                                     ~Queue();                                      //destructor

        void enqueue(const E& e);

        const E& dequeue(); //throw(QueueEmpty); //note that the use of exceptions is optional

        const E& front() const; //throw(QueueEmpty); //note that the use of exceptions is optional

        int size () const;

        bool empty() const;

}

You will need to write two versions of the Deque.cpp file (one for the array-based implementation, one for the linked list based implementation). Both Stack and Queue must be implemented by use of an Adapter applied to the Deque ADT. As a result, you will need 2 additional C++ files, Stack and Queue. Your Stack and Queue cpp files will be much much smaller though. See pages 220 – 222 of your text for a discussion of this topic along with partially provided code.

Requirements:

Develop a C++ software solution that includes an array based and linked-list based implementation for the Deque ADT. Develop C++ Adapter Classes for both the Stack and Queue ADT’s.

You should also provide formal algorithms for each of the methods of your Deque data structures (2 versions, one each for your array and linked list implementations), an efficiency analysis for each of your algorithms, and all of the necessary .cpp and .h files. Be sure to include expand files so that a new data type for the template can easily be added.

Deliverable:

You should provide two separate zip files, one for the array-based implementation and one for the linked-list based implementation. Each zip file should contain 3 header files (Deque.h, Stack.h, Queue.h), 6 cpp files (Deque.cpp, Stack.cpp, Queue.cpp, DequeExpand.cpp, StackExpand.cpp, and QueueExpand.cpp). In addition, you should include a document that contains formal algorithms for each function you have implemented along with a Big O efficiency analysis of the algorithms. Finally, you should include in your document an overall statement regarding the efficiency of each type of implementation (StackArray, StackList, QueueArray and QueueList).

It is always a good idea to include a readme file as well that includes any instructions for compiling and using your software. Although it is not strictly required, It is also advisable to develop a test file that instantiates and tests your stack and queue implementations.

Note on Exceptions:

Implementing your Deque, Stack and Queue to use Exceptions for indicated operations is optional. If you do it, you will receive extra credit (potentially 10 points).

Grading Criteria:

• Your code must conform to the standardized header files presented in this document.
• Your code must work! Obviously it has to compile, but it must also work with test code that will create both versions of the stack and queue and test the public functions.
• Your code will be evaluated for STYLE (as in whitespace, alignment of code blocks, comments that match the code, and appropriate names of variables.)
• Your efficiency analysis must be performed for every function for each implementation.
• Your efficiency analysis must include a summary of the overall efficiency of all implementations.

You can add to the header files, but you can change any function.

Answer 1

#include <bits/stdc++.h>
using namespace std;
  
// structure for a node of deque
struct DQueNode {
int value;
DQueNode* next;
DQueNode* prev;
};
  
// Implementation of deque class
class deque {
private:
  
// pointers to head and tail of deque
DQueNode* head;
DQueNode* tail;
  
public:
// constructor
deque()
{
head = tail = NULL;
}
  
// if list is empty
bool isEmpty()
{
if (head == NULL)
return true;
return false;
}
  
// count the number of nodes in list
int size()
{
// if list is not empty
if (!isEmpty()) {
DQueNode* temp = head;
int len = 0;
while (temp != NULL) {
len++;
temp = temp->next;
}
return len;
}
return 0;
}
  
// insert at the first position
void insert_first(int element)
{
// allocating node of DQueNode type
DQueNode* temp = new DQueNode[sizeof(DQueNode)];
temp->value = element;
  
// if the element is first element
if (head == NULL) {
head = tail = temp;
temp->next = temp->prev = NULL;
}
else {
head->prev = temp;
temp->next = head;
temp->prev = NULL;
head = temp;
}
}
  
// insert at last position of deque
void insert_last(int element)
{
// allocating node of DQueNode type
DQueNode* temp = new DQueNode[sizeof(DQueNode)];
temp->value = element;
  
// if element is the first element
if (head == NULL) {
head = tail = temp;
temp->next = temp->prev = NULL;
}
else {
tail->next = temp;
temp->next = NULL;
temp->prev = tail;
tail = temp;
}
}
  
// remove element at the first position
void remove_first()
{
// if list is not empty
if (!isEmpty()) {
DQueNode* temp = head;
head = head->next;
head->prev = NULL;
free(temp);
return;
}
cout << "List is Empty" << endl;
}
  
// remove element at the last position
void remove_last()
{
// if list is not empty
if (!isEmpty()) {
DQueNode* temp = tail;
tail = tail->prev;
tail->next = NULL;
free(temp);
return;
}
cout << "List is Empty" << endl;
}
  
// displays the elements in deque
void display()
{
// if list is not empty
if (!isEmpty()) {
DQueNode* temp = head;
while (temp != NULL) {
cout << temp->value << " ";
temp = temp->next;
}
cout << endl;
return;
}
cout << "List is Empty" << endl;
}
};
  
// Class to implement stack using Deque
class Stack : public deque {
public:
// push to push element at top of stack
// using insert at last function of deque
void push(int element)
{
insert_last(element);
}
  
// pop to remove element at top of stack
// using remove at last function of deque
void pop()
{
remove_last();
}
};
  
// class to implement queue using deque
class Queue : public deque {
public:
// enqueue to insert element at last
// using insert at last function of deque
void enqueue(int element)
{
insert_last(element);
}
  
// dequeue to remove element from first
// using remove at first function of deque
void dequeue()
{
remove_first();
}
};
  
// Driver Code
int main()
{
// object of Stack
Stack stk;
  
// push 7 and 8 at top of stack
stk.push(7);
stk.push(8);
cout << "Stack: ";
stk.display();
  
// pop an element
stk.pop();
cout << "Stack: ";
stk.display();
  
// object of Queue
Queue que;
  
// insert 12 and 13 in queue
que.enqueue(12);
que.enqueue(13);
cout << "Queue: ";
que.display();
  
// delete an element from queue
que.dequeue();
cout << "Queue: ";
que.display();
  
cout << "Size of Stack is " << stk.size() << endl;
cout << "Size of Queue is " << que.size() << endl;
return 0;
}