Lab 4. Queue
and Stack
CS203,
Spring 2006
1. (35pt) Create a CircularArrayQueue
class, which implements the Queue
interface, using the circular
array approach we discussed in class. You may assume that
there will be no more than 3 objects in the queue at any time. Note that
- enqueue()
and dequeue()
must take only O(1) time.
- The array you use for the queue must be of size 3.
- You must test the queue with at least 6 enqueue()
operations.
2. (15pt) Modify your CircularArrayQueue
class so it dynamically grows like the ArrayList
class, e.g. the size of the array doubles whenever a user
tries to enqueue an object to a queue that is already full.
3. (40pt) Write a program to check whether the symbols '(',
')', '[', ']', '{', and '}' in a given file are balanced. The algorithm
uses a Stack
and goes like this:
- Scan the file one character at a time.
- If the character is not one of the symbols to be checked,
ignore it, and continue with the next character in the file.
- If the character is an opening symbol ( '(', '[', or '{'
), push it onto the stack, and continue with the next character.
- If the character is a closing symbol ( ')', ']', or '}'
), pop a character from the stack, and check whether these two match.
If they do not match, or if there is no character on the
stack, output an error message and terminate the program; otherwise,
continue with the next character.
- After all characters in the file are processed, if the
stack is not empty, output an error message; otherwise output the
message "The symbols in the file are balanced.".
4. (10pt) Modify the program you developed in the previous
exercise so that not only it outputs an error message, it also outputs
the line number where the error occurs (or more precisely, where the
error is caught).
5. Turn in all the source code files through
CSNS. The total points of this lab is 50. Anything above 50 is considered extra credit.