CS 2401 Assignment #7

Due Date: Monday, Nov 1, 2010, or Tuesday, Nov 2, 2010, depending on the day of your lab.

Objective: The goal of this assignment is to practice stacks and queues.

Assignment: The first part of your assignment is to implement both a stack and a queue data structure. You may use either an array-based implementation or a reference-based list implementation. Your Stack class should implement the standard push(), pop(), and peek() methods, in addition to a constructor. Your Queue class should implement the standard enqueue(), dequeue(), and peek() methods, in addition to a constructor.

Next, you will write two programs to test your Stack and Queue classes.

  1. Write a program to compute the value of an expression given in postfix notation, using a Stack as shown in class. Your program should prompt the user for an expression and read the expression in on the command line. Then, either print the result or an error message if the expression is invalid. You should be able to handle any integer input, and the four basic operations "*", "/", "+" and "-". All operands and operators must be separated by a single space (hint: an easy way to break this string into individual operators/operands is to use the "split" method for strings). If the input string contains any invalid characters or is incorrect for any other reason, print an error message. Otherwise, print the result of the expression.

  2. Write a program that uses a queue to implement a simple "todo" list. Each item in the list will have a name and an estimated time to complete. Your program will prompt the user for input. The user can either choose to complete the top task in the list, add a new task (with additional prompts for the name and estimated time to complete), or print the current list of tasks in an easy-to-read format. You may want to add a print method to your queue implementation to support this final task. Make sure to print an error message if the user tries to complete a non-existant task.