Question

In: Computer Science

26.5 Project 3: List & Queue ADT Overview For this project, you are to implement two...

26.5 Project 3: List & Queue ADT

Overview

For this project, you are to implement two abstract data types (ADTs). You will write a doubly linked list (Dll) and a queue class. The queue will use the dll internally. The class interfaces are downloadable below. You must follow the interface exactly. While you can define other public and private methods and fields, the class names and methods given must appear as provided, or you will not pass the unit tests. Include the implementation of the classes in their respective header (.h) files. Please note: Dll is not a node class, as in, a Dll does not point to another Dll; it contains nodes internally.

Dll Comments

When inserting into a dll, rank 0 inserts at the front of the list and rank size() inserts at the back of the list. If you have the list 0 -> 10 -> 30, then after insert(2, 20), the list should be 0 -> 10 -> 20 -> 30.

When removing from a dll, rank 0 removes from the front of the list and rank size() - 1 removes from the back of the list. If you have the list 0 -> 10 -> 20 -> 30, then after remove(2), the list should be 0 -> 10 -> 30.

When building a dll from an array, the array [ 0 1 2 ] should create the list 0 -> 1 -> 2.

Displaying

When displaying a Dll, it should appear with the head on the left and the tail on the right. For example, the list created after insert(0, 3), insert(0, 2), insert(0, 1) should represent the list 1 -> 2 -> 3 and should display as follows:

[ 1 2 3 ]

When displaying a queue, it should appear with the front on the left and the back on the right. For example, the queue created after enqueue(1), enqueue(2), enqueue(3) should display as follows:

[ 1 2 3 ]

When displaying an empty ADT, it should be a single space surrounded by brackets:

[ ]

Efficiency

All operations should have an efficient runtime. Besides display(), all queue operations should run in O(1). Because the queue uses a dll internally, this means insert(), remove(), and size() must be O(1) for the appropriate cases (insert back, remove front), which also means size should be stored and not calculated by looping through the list.

Exceptions

Two exception classes can be found in exceptions.h: InvalidOperationException and IndexOutOfRangeException. Your ADTs will throw exceptions according to the instructions below:

  • List: throw IndexOutOfRangeException for the following operations:
    • at(): when accessing an index outside the bounds (0 to size-1 inclusive) of the linked list with the message "at(): Index was outside the bounds of the linked list."
    • insert(): when index is not in the range from 0 to size (inclusive) with the message "insert(): Index was outside the bounds of the linked list."
    • remove(): when removing an index outside the bounds (0 to size-1 inclusive) of the linked list with the message "remove(): Index was outside the bounds of the linked list."
  • Queue: throw InvalidOperationException with the message "Queue empty." when dequeuing or peeking an empty queue.

p3.cpp

p3.cpp is a command-line interface that can be used to test your data structures. Review the code before running it and testing your data structures. p3.cpp assumes your dll.h and queue.h are completed. You must comment out the portions of the code that you have not implemented (includes and the loops in main pertaining to the data structure) or create "empty" method definitions to make it compilable.

You can compile your program with g++ p3.cpp.

Notes

  • Your data structures will be unit tested separately, meaning Dll can be tested accurately without a fully implemented Queue.
  • Be sure to print to the ostream os variable and not to cout or you will fail the test cases.
  • Throw the exceptions if the index is negative.
  • Be sure to initialize pointers to NULL or nullptr as *nix environments do not initialize variables to 0.

Solutions

Expert Solution

in queue class four function are mentioned

  1. insert ----> insert element at first of the queue.
  2. remove -----> remove element from last of the queue
  3. insertat------> insert element at the given position of the queue.
  4. removeat--------> remove element from the given position of the queue.
#include <iostream>
#define MAX 100
using namespace std;

class Queue
{
      int front,rear;
      int queue[MAX];
 
      public:
  
      Queue()
      {
              front=rear=-1;
      }
 
       void insert(int item)
       {
              if(rear==MAX-1)
             {
                      cout<<"\nqueue overflow occured";
             }
             else if(front==-1 && rear==-1)
             {
                      front=rear=0;
                      queue[rear]=item;
                      cout<<"\n elements inserted "<<item;
             }
             else
             {
                      rear++;
                      queue[rear]=item;
                      cout<<"\nelements inserted : "<<item;
             }
       }
       void insertat(int pos,int val)
       {
       rear++;
       for(int i=rear;i>pos;i--)
       queue[i]=queue[i-1];
       queue[pos]=val;
       }
       void removeat(int pos)
       {
       for(int i=pos;i<rear;i++)
       queue[i]=queue[i+1];
       rear--;
       }
       void remove()
       {
              int item;
  
              if(rear==-1)
             {
                       cout<<"\nQueue Uderflow ";
             }
             else if(front==0 && rear==0)
             {
                       item=queue[front];
                       front=rear=-1;
                       cout<<"\n\nItems deleted : "<<item;
             }
             else
             {
                      item=queue[front];
                      front++;
                      cout<<"\n\nITEM DELETED: "<<item;
             }
       }
 
       void display()
       {
              if(front==-1)
              {
                      cout<<"\n\nQueue is Empty\n";
              }
              else
              {
                      cout<<"\n\nqueue contains element is : \n";
                      for(int i=front;i<=rear;i++)
                      {
                               cout<<queue[i]<<" ";
                      }
                      cout<<endl;
              }
        }
};

int main()
{
      Queue q;
 
      q.display();
      q.insert(10);
      q.insert(20);
       q.insert(30);
      q.insert(40);
       q.insert(50);
      q.insert(60);
       q.insert(70);
      q.insert(80);
      q.insertat(2,100);
      q.display();
      q.removeat(5);
      q.display();
      q.remove();
      q.insert(30);
 
      q.display();
      return 0;
}

output screen accrording to operation performed


Related Solutions

Overview: implement the ADT List in Java. This program is meant to the ADT List from...
Overview: implement the ADT List in Java. This program is meant to the ADT List from the ground up In the lecture, we learned how to implement an ADT like the ArrayList you have used in Project 1. With this project, you have the chance to implement an ADT called MyList, which is a simplified replacement for the full-blown ArrayList. Requirements You will implement the MyList ADT according to the following: 1. MyList must implement the List interface. It will...
In C++, Implement the queue ADT with a singly linked list
In C++, Implement the queue ADT with a singly linked list
You will implement the MyList ADT according to the following: 1. MyList must implement the List...
You will implement the MyList ADT according to the following: 1. MyList must implement the List interface. It will look something like below: public class MyList<E> implements List<E> { ... } Note: As said in the class, when implementing an interface, you have to implement each method in it. There are a lot of methods in the List interface. We are going to address this issue below. 2. The initial capacity of MyList must be 2. This is not an...
1. Implement the graph ADT using the adjacency list structure. 2. Implement the graph ADT using...
1. Implement the graph ADT using the adjacency list structure. 2. Implement the graph ADT using the adjacency matrix structure. LANGUAGE IS IN JAVA Comment for any questions Data structures and algorithms
Using a single queue (linkedQueue), re-implement the concept of Stack ADT, what is the complexity of...
Using a single queue (linkedQueue), re-implement the concept of Stack ADT, what is the complexity of the method push, pop, top, isEmpty, and size. You should not use any extra data structure. Related codes: public interface Stack<E> { int size( ); boolean isEmpty( ); void push(E e); E top( ); E pop( ); } public class LinkedStack<E> implements Stack<E> { private SinglyLinkedList<E> list = new SinglyLinkedList<>( );    public LinkedStack( ) { }    public int size( ) { return...
implement the Queue ADT using the linked list approach #include "QueueLinked.h" template QueueLinked::QueueNode::QueueNode(const DataType& nodeData, QueueNode*...
implement the Queue ADT using the linked list approach #include "QueueLinked.h" template QueueLinked::QueueNode::QueueNode(const DataType& nodeData, QueueNode* nextPtr) { } template QueueLinked::QueueLinked(int maxNumber = Queue::MAX_QUEUE_SIZE) { } template QueueLinked::QueueLinked(const QueueLinked& other) { } template QueueLinked& QueueLinked::operator=(const QueueLinked& other) { } template QueueLinked::~QueueLinked() { } template void QueueLinked::enqueue(const DataType& newDataItem) throw (logic_error) { } template DataType QueueLinked::dequeue() throw (logic_error) {    DataType temp;    return temp; } template void QueueLinked::clear() { } template bool QueueLinked::isEmpty() const {    return false; } template...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you...
C++ Data Structures: Implement a Stack and a Queue using Linked list In this lab you will implement the functionality of a stack and a queue using a linked list. Your program must use of the declaration of the Stack and Queue class in Stack.h and Queue.h You have to implement the functionalities of queue (enq, deq, displayQueue) in a file called Queue.cpp. All the functions in Queue.cpp should follow the prototypes declared in Queue.h. Your code should make use...
Implement the ADT character string as the class LinkedString by using a linked list of characters....
Implement the ADT character string as the class LinkedString by using a linked list of characters. Include the following LinkedString constructors and methods: LinkedString(char[] value) Allocates a new character linked list so that it represents the sequence of characters currently contained in the character array argument. LinkedString(String original) Initializes a new character linked list so that it represents the same sequence of characters as the argument. char charAt(int index) Returns the char value at the specified index. The first character...
Using the linked list abstract data type “Queue ADT”, write a menu dirven user interfece to...
Using the linked list abstract data type “Queue ADT”, write a menu dirven user interfece to teach each of the operations in the ADT. Any errors discovered during the processing should be printed as a part of the test result. Please Use C++ language.
One way to implement a queue is to use a circular linked list. In a circular...
One way to implement a queue is to use a circular linked list. In a circular linked list, the last node’s next pointer points at the first node. Assume the list does not contain a header and that we can maintain, at most, one iterator corresponding to a node in the list. For which of the following representations can all basic queue operations be performed in constant worst time? Justify your answers. Maintain an iterator that corresponds to the first...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT