CSCI 262 Data Structures--Spring 2004

    Assignment 3

    Due at the beginning of class, Friday, February 20, 2004

    Home | | Syllabus | | Assignments | | Lecture Notes

    Note: Because there is an exam on Tuesday, February 24, no late assignments will be accepted. That way solutions can be posted immediately so that you can use them to study for the exam.

    Deques

    As described in the textbook on page 92, a deque (pronounced either "deck" or "DQ") is a double-ended queue (This is not to be confused with the class Deck from the last assignment, which represented a deck of cards). A deque denotes a list in which entries can be added or removed from either end of the list (the first or the last position) but not from the middle. It is like a combination of a stack and a queue. The operations for a deque are: 

      	append_front      //append an item to the front of the deque
	append_rear       //append an item to the rear of the deque
	serve_front       //delete an item from the front of the deque
	serve_rear        //delete an item from the rear of the deque
	retrieve_front    //retrieve an item from the front of the deque
	retrieve_rear     //retrieve an item from the rear of the deque

    In this problem set you will create a Deque class and complete a program to test it.

    Starting the assignment.
    In the ~csci262/assignments/assign3 folder you will find the header file, queue.h and the implementation file, queue.cc. These contain all the class definitions that you will need for this assignment. In addition there is a file, testDeque.cc, that contains code from the textbook section 3.4, slightly altered to refer to a deque instead of a queue.

    Copy the files from the csci262 directory into your own by typing:

      cp -r ~csci262/assignments/assign3 assignments/.

    Creating the Deque class
    Create two new files: deque.h and deque.cc. In these files you should write the definition and implementation, respectively, of the Deque class. The Deque class should inherit from the Queue class. Write the definition so that the Queue functions are inaccessible to the client code when using a Deque object. The Deque class should contain all the member functions listed above. The functions should be modeled on the Queue class functions, returning appropriate error codes and using similar parameter lists. You can continue to use the type Queue_entry for your deque items (i.e. you do not have to declare a type, Deque_entry). The Deque should be implemented using the circular array model.

    Testing the Deque class
    Fill in the missing code in the get_command() and the do_command() functions in the testDeque.cc file. Make sure the commands perform the tasks described in the help() function included in the file:

      A - Append the next input character to the rear.
      P - Push the next input character to the front.
      S - Serve the front of the queue
      X - Extract the rear of the queue
      R - Retrieve and print the front entry.
      W - Retrieve and write the rear entry.
      H - Show the help screen
      Q - Quit

    You are not required to break the do_command() into smaller functions.

    Sample Output:
    Here is an example of what your output should look like: 

      radius% testDeque

This program allows the user to enter one command
(but only one)on each input line.
For example, if the command S is entered, then
the program will serve the front of the queue.

 The valid commands are:
A - Append the next input character to the rear.
P - Push the next input character to the front.
S - Serve the front of the queue
X - Extract the rear of the queue
R - Retrieve and print the front entry.
W - Retrieve and write the rear entry.
H - This help screen
Q - Quit
Press <Enter> to continue.
Select command and press <Enter>:s
Serve failed, the deque is empty.

Select command and press <Enter>:x
Serve failed, the Deque is empty.

Select command and press <Enter>:r
Deque is empty.

Select command and press <Enter>:w
Deque is empty.

Select command and press <Enter>:a
Enter new key to insert:1
1 appended to rear of deque. 

Select command and press <Enter>:a
Enter new key to insert:2
2 appended to rear of deque. 

Select command and press <Enter>:a
Enter new key to insert:3
3 appended to rear of deque. 

Select command and press <Enter>:r
The first entry is: 1

Select command and press <Enter>:w
The last entry is: 3

Select command and press <Enter>:p
Enter new key to insert:4
4 appended to front of deque.

Select command and press <Enter>:r
The first entry is: 4

Select command and press <Enter>:s
Successfully served the front of the deque. 

Select command and press <Enter>:r
The first entry is: 1

Select command and press <Enter>:w
The last entry is: 3

Select command and press <Enter>:x
Successfully served the rear of the deque.

Select command and press <Enter>:w
The last entry is: 2

Select command and press <Enter>:q
Deque demonstration finished.

    What to turn in:

    • Turn in a hard copy of the files, deque.h, deque.cc, testDeque.cc.
      Make sure you include a file prologue with your name, class, lecture section, the date, and the assignment number, along with a description of the file contents and their purpose. Also include appropriate comments for each of the functions you implement (with proper pre and post conditions).
    • Turn in a printout of a sample run of your program with the same inputs as shown above.
    • Submit the soft copy of your program using the command:
      ~csci262/bin/submit csci262 assign3

    Home | | Syllabus | | Assignments | | Lecture Notes

    Constance Royden--croyden@mathcs.holycross.edu
    Computer Science 262--Data Structures
    Date Created: February 7, 2002
    Last Modified: February 11, 2004
    Page Expires: January 14, 2005