Tutorial 6, CPSC 331, Fall 2008

Stacks and Queues

About This Exercise

This exercise is based on material presented during the lectures on Monday, September 29 4 and Wednesday, October 1. Information presented on Friday, September 26 will also be useful as well, if you complete the programming exercises that are included here.

The objectives of this exercise are

to ensure that you understand and can work with the specifications of abstract data types that are used in the textbook
to ensure that you understand and can work with the descriptions of the corresponding interfaces, abstract classes and classes included in the Java Collections Framework
to ensure that you understand properties of stacks and queues, and of their implementations
to give you practice in implementing both stacks and queues using a facilities that a variety of programming languages (including but not limited to Java) would provide for this, and
to use the implementations of these abstract data types that are available in Java to solve problems whose solutions make effective use of these abstract data types.

Please read through and try to solve the problems on this exercise before attending the tutorials on February 11-14.

Problems To Be Solved

Chapters 5 and 6 of the textbook include specifications of abstract data types corresponding to an “unbounded stack” and a “bounded queue.”

Use these examples, and the information from lectures, to write corresponding specifications of a “bounded stack” and an “unbounded queue” as well.
After consulting information about the current version of the Java Collections Framework and, more generally, the online documentation for Java 1.5, describe the support for stacks and queues that Java currently provides.
Consider the following stack.
1. Draw the array that would be used to represent this stack, using the array-based representation of a stack described in class, with an array of size eight.
2. Draw the linked list that would be used to represent this stack, using the list-based representation of a stack described in class.
3. Show the stacks (represented using pictures like the above, as well as arrays and lists) that would result from the following sequence of operations if you started with the above stack:
  1. push “epsilon”
  2. pop
  3. push ”zeta”
Write classes to implement stacks in Java as described below.
1. Implement a “Bounded Stack” using a simple array.
2. Implement a stack using ArrayList.
3. Implement a stack using LinkedList.
If you know Pascal or C, write array-based and linked list-based implementations of a Stack in either (or, better yet, both) of these programming languages.

If possible, your array-based implementations should be expandable, just like an implementation in Java that is based on ArrayList.
Use one (or more) of the implementations of Stack that you now know about to write a program that solves the “Parenthesis Matching” problem that was described in class. Your program should read a string on the command line and it should produce a short message as output to say whether parentheses in the input string are matched.
Consider the following queue.

This can be implemented as a “circular queue” (with an array of size 8) as follows.
1. Draw the queues (using both types of pictures that are shown, above) that would result if you performed the following sequence of operations on the above queue.
  1. enqueue “e”
  2. dequeue
  3. dequeue
  4. enqueue “f”
  5. enqueue “g”
  6. dequeue
  7. dequeue
  Make sure to include the values of “front” and “back” in each case.
2. Draw the linked-list implementation of each of the above queues as well.
Consider the problem of recognizing “palindromes” that was discussed during the lecture on queues.

Describe a way to decide whether a given string of text is palindrome. Your solution use both a stack and a queue and it should determine whether the input string is a palindrome using a number of steps that is linear in the length of the input.
Consider each of the following ways to implement a bounded queue (with capacity N) using an array of size N. Explain why each implementation is less useful than the array-based implementation described in lectures, even though it is simpler in one way or another.
1. Make sure that the elements of the queue are always stored at the beginning of the array: If the queue currently includes n elements then these should be stored in positions 0, 1, …, n−1 of the array.
2. Allow the queue to be used just like it is as described in lectures, except that we cannot wrap around: An attempt to enqueue an element should cause an exception to be thrown, and the queue to be unchanged, if “back” has value N−1.
Write classes to implement queues in Java as described below.
1. Implemented a Bounded Queue using a simple array — where a “Bounded Queue” is a queue with a maximal capacity (that can be declared by the user when the structure is initialized).
2. Implement a queue using an array. Use array expansion when the size of the queue exceeds the size of the array that is currently being used. Choose array sizes to keep the total number of operations reasonably small: If you begin with an empty queue and perform n operations then the total number of steps used by your implementation should be at most linear in n.
3. Implement a queue using LinkedList.
Modify your implementations to obtain implementations of deques.
If you know Pascal or C, write array-based and linked list-based implementations of queues and deques in either (or, better yet, both) of these programming languages.
Using one of the implementations of each of a stack and a queue that are now available to you, write a program that implements the solution for the “palindrome checking” problem that you produced to answer Question 8, above.

This page last modified:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/F08/tutorials/tutorial6.html