COSC 2436 - Programming Fundamentals III Data Structures
Bob Comer, Professor of Computer Studies

Be sure to read through Chapter 8 of the textbook before starting this assignment.

Section 8.3 in the Nyhoff textbook discusses a linked-list implementation of a queue. Figure 8.3 has code for an implementation using a standard singly-linked list with two pointers - a pointer to the front element (myFront) and a pointer to the back element (myBack). Review this code to be sure that you understand how this implementation works.

Page 423 of your textbook discusses a modification to the linked-list implementation that uses a circular linked-list. In particular, the last paragraoh on page 423 suggests that this implementation only requires a single pointer to the back element (myBack).

Your assignment is to start with the code in Figure 8.3 of the textbook and modify it to use a circular linked-list with a single myBack pointer as described in the last paragraph on page 423 of the textbook.

I am not requiring you to write a copy constructor or overloaded assignment operator for your updated class. If you remove the prototypes for these functions from the class header file and the function definitions from the class implementation file, C++ will create a default copy constructor and assignment operator that will work incorrectly. To prevent a programmer from using these operations, I want you to do the following.

In the class header file, include prototypes for the copy constructor and asignment operator. Instead of preconditions and postconditions, tell the client programmer that the class has no copy constructor or assignment operator. Queue(const Queue & original); // the Queue class has no copy constructor // Operations that require a copy constructor are not allowed const Queue & operator= (const Queue & rightHandSide); // the Queue class has no assignment operator // Assigning a Queue object to another Queue object is not allowed In the class implementation file, do not include definitions for these functions. Include brief documentation that the class does not have these functions. //--- Queue class has no copy constructor // Queue::Queue(const Queue & original){} //--- Queue class has no assignment operator // const Queue & Queue::operator=(const Queue & rightHandSide){}

Discussion/Questions

The following questions are designed to help you think about situations that you will need to identify in your circular linked-list. It would be a good idea to draw pictures of what the linked-list might look like to help you visualize what you are doing. These questions are NOT to be turned in. If you cannot answer any of these questions, it would be a good idea to discuss them with yoiur instructor or a tutor.

1. Write an expression which is true when the queue is empty, and false otherwise.
2. The data member myBack holds the address of the last (back) element in the queue (assuming that the queue is not empty). Write an expression that gives the address of the front element in the queue.
3. Is there a special case where your expression from the previous question will not work?
4. Write an expression that is true when there is exactly one element in the queue, and false otherwise.
5. Is there a special case where your expression from the previous question will not work?

Hints

1. -
2. Since the linked-list is circular, the node containing the front element comes after the node containing the back element.
3. What happens when the queue is empty?
4. In this situation, the front element and back element are the same. More precisely, the node containing the front element and the node containing the back element have the same memory location.
5. -

Return to Data Structures homepage 

Return to ACC Homepage

URL: http://www.austincc.edu/comer/cosc2436/
Copyright: 2015 by the Austin Community College
Department of Computer Studies. All rights reserved.
Comments to: Bob Comer
Last updated: October 25, 2015

Austin Community College is an equal opportunity educator and employer.