Assignment 4 Solutions

CSCI 132 Data Structures--Spring 2014

Assignment 4 Solutions
Solution queue.cc code:
/****************************************************
* Name: Brenda Student
* Date: 3/16/14
* Course: CSCI 132 Section 01
* Assignment: Assignment 4
* Instructor: Royden
* File name: Queue.cc
* Purpose: Implementation of Queue class
*****************************************************/

#include "queue.h"

Queue :: Queue(const Queue &original) // copy constructor
  /* Post: The Queue is initialized as a copy of Queue original. */
{
  Node *new_copy, *original_node = original.front; //pointers to first node
  if (original_node == NULL) front = rear = NULL;
  else { // Duplicate the linked nodes.
    front= rear = new_copy = new Node(original_node->entry);
    while (original_node->next != NULL) {
      original_node = original_node->next;
      new_copy->next = new Node(original_node->entry);
      new_copy = new_copy->next;
    } //end while
    rear = new_copy;
  } //end if--else
} //end Queue()

void Queue :: operator = (const Queue &original) 
  /* Post: The Queue is reset as a copy of Queue original. */
{
	//Declare pointers to traverse list and make a copy.
  Node *new_front, *new_rear,*new_copy, *original_node = original.front;
  if (original_node == NULL) new_front = new_rear = NULL;
  else { // Duplicate the linked nodes.
    new_front= new_rear = new_copy = new Node(original_node->entry);
    while (original_node->next != NULL) {
      original_node = original_node->next;
      new_copy->next = new Node(original_node->entry);
      new_copy = new_copy->next;
    } // end while
    new_rear = new_copy;
  } //end if--else
  while (!empty()) //Delete all nodes from pointer being assigned to
    serve();
  front = new_front;
  rear = new_rear;
}  //end operator=()

Queue :: ~Queue() {
  /* Post: The Queue is deleted */
  while(!empty()) {
    serve();
  } //end while
} //end ~Queue

Term :: Term(int exponent, double scalar)
  /* Post: The Term is initialized with the given coefficient 
     and exponent, or with default parameter values of 0. */
{
  degree = exponent;
  coefficient = scalar;
}

Node ::Node()
{
  next =NULL ;
}

Node ::Node(Node_entry item ,Node *add_on)
{
  entry =item ;
  next =add_on ;
}

int Extended_queue::size( ) const
  /* Post: Return the number of entries in the Extended_queue. */
{
  Node *window = front;
  int count = 0;
  while (window != NULL) {
    window = window->next;
    count++;
  }
  return count;
}

bool Extended_queue :: full() const
  /* post: return true if no room in queue */
{
  Node *new_node = new Node();
  return new_node == NULL;
}

void Extended_queue::clear() 
  /* Post: clear and delete queue entries */
{
  while (!empty()) {
    serve();
  }
}

Error_code Extended_queue :: serve_and_retrieve(Queue_entry &item)
  /* Post: return entry at front of queue in item, then delete front node*/
{
  if( retrieve(item) == underflow) {
    return underflow;
  }
  return serve();
}

Queue::Queue()
  /*
Post: The Queue is initialized to be empty.
  */
{
  front = rear = NULL;
}


bool Queue::empty() const
  /*
Post: Return true if the Queue is empty, otherwise return false.
  */
{
  return front == NULL;
}


Error_code Queue::append(const Queue_entry &item)
  /*
Post: item is added to the rear of the Queue. If the Queue is full
return an Error_code of overflow and leave the Queue unchanged.
  */

{
  Node *new_rear = new Node(item);
  if (new_rear == NULL) return overflow;
  if (rear == NULL) front = rear = new_rear;
  else {
    rear->next = new_rear;
    rear = new_rear;
  }
  return success;
}


Error_code Queue::serve()
  /*
Post: The front of the Queue is removed. If the Queue
is empty return an Error_code of underflow.
  */

{
  if (front == NULL) return underflow;
  Node *old_front = front;
  front = old_front->next;
  if (front == NULL) rear = NULL;
  delete old_front;
  return success;
}


Error_code Queue::retrieve(Queue_entry &item) const
  /*
Post: The front of the Queue retrieved to the output
      parameter item. If the Queue is empty return an Error_code of underflow.
  */

{
  if (front == NULL) return underflow;
  item = front->entry;
  return success;
}