CSCI 132 Data Structures--Spring 2014

    Home | | Syllabus | | Assignments | | Lecture Notes

    Laboratory 4
    Due at the beginning of class, Wednesday, 2/19
    Note: Because there is an exam on Tuesday, 2/25, no late labs will be accepted after Friday, 2/21 in class so that the solutions can be posted on Friday.

    In today's lab you will practice using the Queue class that we implemented in class. You will also have a chance to implement some of the stack classes using the linked list representation.

    The code for this lab is available in the directory:

      ~csci132/labs/lab4

    Start the lab as follows:

    • Copy the code for lab4 into your labs folder by typing:
        cp -r ~csci132/labs/lab4 labs/.
    • Change directories into your new lab4 directory by typing:
        cd labs/lab4
    • Type ls to verify that the lab3 directory contains the following files:
      • stack.h
      • stack.cc
      • queue.h
      • queue.cc
      • testStack.cc
    • Start up an emacs window to create the file, compare.cc .

    1. Comparing strings

    Write a program, compare.cc, that reads in one line from the computer keyboard. The line should consist of two strings separated by a colon. The program should compare the two strings without using a counter and output the appropriate one of the following messages:
    • The input has no colon.
    • The lefthand string is longer than the righthand string.
    • The righthand string is longer than the lefthand string.
    • The two strings are the same length, but they are different.
    • The two strings are the same.
    Note that if you read in the line one character at a time, you can store each character of the first string in a queue. You don't need to store the characters of the second string in a queue--you can simply compare each character you read in to the characters retrieved from the queue for the first string. You do not need to save the strings for use after determining the relative lengths.

    Compile your program using the command:

      g++ -g -Wall compare.cc queue.cc -o compare

    Sample output
    The following are some sample runs of the program: 

      mathcs% ./compare
Please enter two strings separated by a colon:
The rain:in Spain
The two strings are the same length, but they are different.
mathcs% ./compare
Please enter two strings separated by a colon: 
I think:therefore I am
The righthand string is longer than the lefthand string.
mathcs% ./compare
Please enter two strings separated by a colon: 
Ice is nice
The input line has no colon. 
mathcs% ./compare
Please enter two strings separated by a colon: 
Four score and seven:Four score and seven
The two strings are the same. 
mathcs% ./compare
Please enter two strings separated by a colon:
:olympic gold
The righthand string is longer than the lefthand string.

    Hints:

    • Read the input one character at a time (use cin.get(c)).
    • Store each character in your queue until you reach a ':' or a '\n'.
    • Use the presence of the '\n' to indicate there was no colon.
    • As you read in the characters in the second string, compare them to the retrieved characters in the queue (and serve each character after retrieving it).
    • Use a boolean flag initialized to true to signal whether the two strings are the same. As you compare the characters in the second string with the queue entries, set the flag to false if they don't match.
    • If the queue is emptied before you finish reading the second string (i.e. before you reach a '\n'), then the second string has more characters.
    • If the queue has entries remaining after reading all the characters of the second string (i.e. after you reach the '\n'), then the first string has more characters.
    • If the queue is emptied as you reach the '\n', the strings have the same number of characters. If your flag is still true, the strings are the same.

    2. Implementing a stack with linked lists

    In class we learned how to implement the push() and pop() functions for a Stack class that represents the stack with a linked list instead of an array. In this problem you will implement the top( ) function and the size( ) function for this same class.

    Open the file, stack.cc. Notice that this file implements both the Node constructor functions and most of the stack functions. There are two stubs that you will need to implement: 

      int Stack::size( ) const {
  /*Post: Number of items in the stack is returned
  	***You must implement this function for Lab4 *****/
  return 0;
} //size

Error_code Stack:: top(Stack_entry &item) const {
  /*Post:Value of top of stack is placed in item;
    returns success or returns
    a code of underflow if the stack is empty
    ***You must implement this function for Lab4 *****/
  return underflow;
} //top

    Keep in mind the following:

    • To implement the size( ) function, create a new pointer that moves along the stack's linked list until it reaches the end of the list. Increment a counter with each move of this pointer.
    • Make sure that your top( ) function returns the appropriate error code.
    • Test your implementation by compiling and running the testStack.cc file. Compile your program with the following command:
        g++ -g -Wall testStack.cc stack.cc -o testStack
    • Run testStack.

    Sample Output
    Your output should look as follows: 

      Pushing 1
The stack size is 1
Pushing 2
The stack size is 2
Pushing 3
The stack size is 3
Pushing 4
The stack size is 4
Pushing 5
The stack size is 5
Pushing 6
The stack size is 6
Pushing 7
The stack size is 7
Pushing 8
The stack size is 8
Pushing 9
The stack size is 9
Pushing 10
The stack size is 10
Stack top is 10. Popping top. 
Stack top is 9. Popping top. 
Stack top is 8. Popping top. 
Stack top is 7. Popping top. 
Stack top is 6. Popping top. 
Stack top is 5. Popping top. 
Stack top is 4. Popping top. 
Stack top is 3. Popping top. 
Stack top is 2. Popping top. 
Stack top is 1. Popping top. 
All done!

    What To Turn In.

    • A printout of the compare.cc file
    • A printout of the stack.cc file
    • Submit an electronic version your lab with the submit command:
        ~csci132/bin/submit csci132 lab4

    Be sure that the file prologue for each file contains your name, course, lecture section, date and purpose of the program or a description of the contents of the file (e.g. specification of the stack class).

    Reminder.
    Be sure to save a copy of each file in your labs directory. It is your responsibility to keep the copies of all programs written for this course until your graded assignment is returned.

    Home | | Syllabus | | Assignments | | Lecture Notes