You will use the definition of the linked-queue from lab6, and re-write it as a

Question

You will use the definition of the linked-queue from lab6, and re-write it as a template for a linked-queue (I hope you finished the function definitions)

In the driver file, create and use queues of different types to show it works.

In the documentation, indicate if there are any types it won’t work for, and why not.

driver.cpp

#include <iostream>
using namespace std;

#include "LQueue.h"
void print(Queue q)
{
q.display(cout);
}
int main()
{
Queue q1;
cout << "Queue created. Empty? " << boolalpha << q1.empty() << endl;
cout << "How many elements to add to the queue? ";
int numItems;
cin >> numItems;
for (int i = 1; i <= numItems; i++)
  q1.enqueue(100 * i);
cout << "Contents of queue q1 (via print): ";
print(q1); cout << endl;
Queue q2;
q2 = q1;
cout << "Contents of queue q2 after q2 = q1 (via print): ";
print(q2); cout << endl;
cout << "Queue q2 empty? " << q2.empty() << endl;
cout << "Front value in q2: " << q2.front() << endl;
while (!q2.empty())
{
  cout << "Remove front -- Queue contents: ";
  q2.dequeue();
  q2.display(cout);
}
cout << "Queue q2 empty? " << q2.empty() << endl;
cout << "Front value in q2?" << endl << q2.front() << endl;
cout << "Trying to remove front of q2: " << endl;
q2.dequeue();
return 0;
}

LQueue.h

#include <iostream>
#ifndef LQUEUE
#define LQUEUE
typedef int QueueElement;
class Queue
{
public:
/***** Function Members *****/
/***** Constructors *****/
Queue();
/*-----------------------------------------------------------------------
     Construct a Queue object.
      Precondition: None.
       Postcondition: An empty Queue object has been constructed.
            (myFront and myBack are initialized to null pointers).
      -----------------------------------------------------------------------*/
Queue(const Queue & original);
/*-----------------------------------------------------------------------
     Copy Constructor
      Precondition: original is the queue to be copied and is received
           as a const reference parameter.
         Postcondition: A copy of original has been constructed.
      -----------------------------------------------------------------------*/
      /***** Destructor *****/
~Queue();
/*-----------------------------------------------------------------------
     Class destructor
      Precondition: None.
       Postcondition: The linked list in the queue has been deallocated.
    -----------------------------------------------------------------------*/
    /***** Assignment *****/
const Queue & operator= (const Queue & rightHandSide);
/*-----------------------------------------------------------------------
     Assignment Operator
      Precondition: rightHandSide is the queue to be assigned and is
           received as a const reference parameter.
         Postcondition: The current queue becomes a copy of rightHandSide
              and a reference to it is returned.
        -----------------------------------------------------------------------*/
bool empty() const;
/*-----------------------------------------------------------------------
    Check if queue is empty.

       Precondition: None.
       Postcondition: Returns true if queue is empty and false otherwise.
       -----------------------------------------------------------------------*/
void enqueue(const QueueElement & value);
/*-----------------------------------------------------------------------
    Add a value to a queue.

       Precondition: value is to be added to this queue.
       Postcondition: value is added at back of queue.             
       -----------------------------------------------------------------------*/
void display(ostream & out) const;
/*-----------------------------------------------------------------------
    Display values stored in the queue.
       Precondition: ostream out is open.
       Postcondition: Queue's contents, from front to back, have been
       output to out.
       -----------------------------------------------------------------------*/
QueueElement front() const;
/*-----------------------------------------------------------------------
    Retrieve/Peep value at front of queue (if any).

       Precondition: Queue is nonempty.
       Postcondition: Value at front of queue is returned, unless the queue
       is empty; in that case, an error message is displayed and a
       "garbage value" is returned.
       -----------------------------------------------------------------------*/
void dequeue();
/*-----------------------------------------------------------------------
    Remove value at front of queue (if any).
       Precondition: Queue is nonempty.
       Postcondition: Value at front of queue has been removed, unless
       queue is empty; in that case, an error message is displayed
       and execution allowed to proceed.
       -----------------------------------------------------------------------*/
private:
void delete_q(); // utility/helper function to delete queues for
      // destructor and assignment operator
         /*** Node class for the queue***/
class Node
{
public:
  QueueElement data;
  Node * next;
  //--- Node constructor
  Node(QueueElement value, Node * link = 0)
        /*-------------------------------------------------------------------
            Precondition: value and link are received
             Postcondition: A Node has been constructed with value in its
                 data part and its next part set to link (default 0).
                  ------------------------------------------------------------------*/
  {
   data = value; next = link;
  }

}; //for Node class
typedef Node * NodePointer;

/***** Data Members *****/
NodePointer myFront,      // pointer to front of queue
  myBack;                 // pointer to back of queue

}; // end of class declaration
#endif

LQueue-Incomplete.cpp

#include <new>
using namespace std;
#include "LQueue.h"
//--- Definition of Queue constructor
Queue::Queue()
: myFront(0), myBack(0)
{}
//--- Definition of Queue copy constructor
Queue::Queue(const Queue & original)
{
myFront = myBack = 0;
if (!original.empty())
{
  // Copy first node
  myFront = myBack = new Node(original.front());
  // Set pointer to run through original's linked list
  NodePointer origPtr = original.myFront->next;
  while (origPtr != 0)
  {
   myBack->next = new Node(origPtr->data);
   myBack = myBack->next;
   origPtr = origPtr->next;
  } //while
} //if
}
void Queue::delete_q(void) {
// Set pointer to run through the queue
NodePointer prev = myFront, // node to be released/deleted
  ptr; // points to the front node

while (prev != 0)
{
  ptr = prev->next;
  delete prev;
  prev = ptr;
}
}
//--- Definition of Queue destructor
// delete queue from the front
Queue::~Queue()
{
delete_q();
}
//--- Definition of assignment operator
const Queue & Queue::operator=(const Queue & rightHandSide)
{
if (this != &rightHandSide)         // check that not q = q
{
  this->delete_q();               // destroy current linked list

  if (rightHandSide.empty())       // empty queue
   myFront = myBack = 0;
  else
  {                                // copy rightHandSide's list
           // Copy first node
   myFront = myBack = new Node(rightHandSide.front());
   // Set pointer to run through rightHandSide's linked list
   NodePointer rhsPtr = rightHandSide.myFront->next;
   while (rhsPtr != 0)
   {
    myBack->next = new Node(rhsPtr->data);
    myBack = myBack->next;
    rhsPtr = rhsPtr->next;
   }
  }
}
return *this;
}
//--- Definition of empty()
bool Queue::empty() const
{
return (myFront == 0);
}
//--- Definition of enqueue()
void Queue::enqueue(const QueueElement & value)
{
NodePointer newptr = new Node(value);
if (empty())
  myFront = myBack = newptr;
else
{
  myBack->next = newptr;
  myBack = newptr;
}
}
//--- Definition of display()
void Queue::display(ostream & out) const
{
NodePointer ptr;

for (ptr = myFront; ptr != 0; ptr = ptr->next)
  out << ptr->data << " ";
out << endl;
}
//--- Definition of front()
// Peep the first element of the queue
QueueElement Queue::front() const
{
if (!empty())
  return (myFront->data);
else
{
  cerr << "*** Queue is empty "
   " -- returning garbage *** ";
  QueueElement * temp = new(QueueElement);
  QueueElement garbage = *temp;     // "Garbage" value
  delete temp;
  return garbage;
}
}
//--- Definition of dequeue()
// simply decrement the queue
void Queue::dequeue()
{
if (!empty())
{
  NodePointer ptr = myFront;
  myFront = myFront->next;
  delete ptr;
  if (myFront == 0)     // queue is now empty
   myBack = 0;
}
else
  cerr << "*** Queue is empty -- can't remove a value *** ";
}

Explanation / Answer

Answer:

#include<iostream>
#include<stdio.h>
#include<conio.h>
using namespace std;
struct node
{
    int data;
    node *next;
}*front = NULL,*rear = NULL,*p = NULL,*np = NULL;
void push(int x)
{
    np = new node;
    np->data = x;
    np->next = NULL;
    if(front == NULL)
    {
        front = rear = np;
        rear->next = NULL;
    }
    else
    {
        rear->next = np;
        rear = np;
        rear->next = NULL;
    }
}
int remove()
{
    int x;
    if(front == NULL)
    {
        cout<<"empty queue ";
    }
    else
    {
        p = front;
        x = p->data;
        front = front->next;
        delete(p);
        return(x);
    }
}
int main()
{
    int n,c = 0,x;
    cout<<"Enter the number of values to be pushed into queue ";
    cin>>n;
    while (c < n)
    {
   cout<<"Enter the value to be entered into queue ";
   cin>>x;
        push(x);
        c++;
     }
     cout<<" Removed Values ";
     while(true)
     {
        if (front != NULL)
            cout<<remove()<<endl;
        else
            break;
     }
     getch();
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.