COMP125 Stacks and Queues

Learning outcomes

This week we look at stacks and queues. By the end of this session, you should

• have a better understanding of how stacks and queues operate;
• be able to use stacks and queues to solve simple problems.

The le stacksQueues_tutorial_start.zip contains a few java programs to make the implementation easier.

Questions

1. a. Using pen and paper, add strings "unit", "this", "love", "I" to a stack. What message would be displayed when removing elements from the stack?

b. Implementa)inJava. Namely, createastackof String, additems"unit", "this","love", "I"tothestackand use a loop to display all the elements in the stack separated by a space.

2. a. Howwouldyoudisplaytheelementsofastackintheordertheyareenteredinthestack,i.e. frombottomto top?

b. The class Card deals with playing cards. It has methods to set and display the value of a card. In the class Hand, write a method makeHand that takes an integer n and returns a stack of n random cards. The method should also display the values of the card as they are generated and added to the stack.

c. Write a method reverseDisplay that displays the cards in the order they are entered in the stack.

3. In class SQDemo, complete the method countEven that when passed a stack of integers, returns the number of even numbers. Return null if the stack is empty.

4. a. Given a queue of Integer, devise an approach that displays the elements of the queue from head to tail as well as returning the number of elements in the queue that are strictly larger than the head element.

b. Implement your solution as a method countAndShow in the class SQDemo.

c. Create a queue called pipe to store 10 random integral values between -20 and 20 and test countAndShow on it.

5. a. Given a queue q, explain how to create another queue that contains the same elements as q but in reverse order.

b. Implement your approach as a method reverseQueue in the class SQDemo.

6. In class SQDemo, complete the method alternateItems that when passed a stack of integers, returns a stack containingeveryalternateitem,startingfromthetopitem,fromthepassedstack. Forexample,ifthestackpassed is [8, 1, 3, 6], returns the stack [8, 3], and when the stack passed is [8, 1, 3, 6, 2], returns the stack [8, 3, 2]

Hints: You will need to ensure that the stack is not empty when you want to remove the item that should NOT be added to the result. Also, you will need to populate a temporary stack and then reverse it before returning it.