CSE 214 – Fall 2013

Recitation 4: Queue

(TA Version)

1. [5 minutes] Propose an idea to do the following in java: [Hint: Use Math.random()]

1. Generate random multiples of 5 from the range [0, 100]
2. Generate random numbers uniformly distributed in the range (-10, 30)

(a)       public int randomNum1(){

return  (int) (Math.random() * 21) * 5;

}

(b)       public double randomNum2(){

int sign = 1; //sign determines if number is positive or negative

if(Math.random() < 0.25){  //0.25 is the portion of the range that is negative

sign = -1;

}

if(sign == -1){

return sign * (Math.random() * 10);

else

return Math.random() * 30;

2. [15 minutes] Write a MyQueue class, which implements a queue using two stacks called inputStack and outputStack. We assume that MyQueue is used to store element of type <Object>.

NOTE: inputStack is used to store pushed Objects and outputStack will provide the Object that is to be popped.

Reminder: Stack – First In Last Out                     Queue – First In First Out

(a)  public MyQueue() //basic Constructor

(b)  private void shiftStacks() //a helper method that shifts all the elements in inputStack to outputStack

(c)   public int size() //returns the number of Objects in MyQueue

(d)  public boolean isEmpty() //determines whether MyQueue is empty or not

(e)   public void enqueue(Object obj) //adds an Object to MyQueue

(f)   public Object dequeue() //removes an Object from MyQueue

(g)  public Object peek() //returns the next Object that can be popped

public class MyQueue<Object> {

Stack<Object> inputStack, outputStack;

public MyQueue(){

inputStack = new Stack<Object>();

outputStack = new Stack<Object>();

}

private void shiftStacks(){

while(!inputStack.isEmpty())

outputStack.push(inputStack.pop());

}

public int size(){

return inputStack.size() + outputStack.size();

}

public boolean isEmpty(){

if(size() == 0)

return true;

else

return false;

}

public void enqueue(Object obj){

inputStack.push(obj);

}

public Object dequeue(){

if(isEmpty())

return null;

else{

if(outputStack.size() == 0)

shiftStacks();

return outputStack.pop();

}

}

public Object peek(){

if(isEmpty())

return null;

else{

if(outputStack.size() == 0)

shiftStacks();

return outputStack.peek();

}

}

}

3. [15 minutes] Implement a GameQueue using a array with dynamic front and rear references. The size of the array should be stored in a final variable with a value of 8. Provide basic queue methods to use for the next question: (NOTE: Team is a class used in the next question. Disregard for now.)

(a)  public GameQueue() //basic Constructor

(b)  public void enqueue(Team t) //adds a Team into the Queue

(c)   public Team dequeue() // removes a Team from the Queue

public class GameQueue {

private final int MAX_SIZE = 8;

private Team[] line;

private int front, rear;

public GameQueue(){

line = new Team[MAX_SIZE];

frint = rear = -1; // no elements in the list

}

public void enqueue(Team t){

if(rear == -1)

front = rear = 0;

else

rear = (rear + 1) % MAX_SIZE; //wrap-around effect

line[rear] = t;

}

public Team dequeue(){

Team t = line[front];

if(front == rear)

front = rear = -1;

else

front = (front + 1) % MAX_SIZE; //wrap-around effect

return t;

}

}

4. [15 minutes] Taken from the lecture notes: Jai Alai

In a game of Jai Alai, there are 8 teams in total. At any given time, two teams compete while the rest are placed in a waiting queue. After a single round is completed, the loser should be placed at the end of the queue, while the winner is challenged by the next team waiting in queue. During the first 7 matches, the winning team earns 1 point. After 7 matches, the winning team earns 2 points. The game ends when a particular team has accumulated 7 points. Assuming each team has a win rate of 50% (same chances of winning for each team), write a program (with main method) that stimulates a game of Jai Alai. The Team class will be provided as follows:

public class Team{

String teamName;

int points;

public Team(String name){

teamName = name;

points = 0;

}

public String getTeamName(){

return teamName;

}

public int getPoints(){

return points;

}

points = points + earn;

}

}

** Using the GameQueue class from number 3, Team class from number 4, and your own driver class you just implemented, you can run the stimulation on a Java compiler. **

/**

*@author Sun

*/

public class JaiAlai{

public static void main(String[] args){

GameQueue line = new GameQueue();

for(int i = 1; i <= 8; i++)

line.enqueue(new Team(“Team ” + i));

int numRounds = 1;

Team winner = line.dequeue();

Team challenger = line.dequeue();

Team tempVar = null;

while(winner.getPoints < 7){

tempVar = compete(winner, challenger);

if(!winner.equals(tempVar)){          //if winner doesn’t win this round

challenge = winner;

winner = tempVar;

}

if(numRounds <= 7)

else

System.out.print(winner.getName() + “ has won round ” + numRounds +

“. \n” + winner.getName() + “ currently has ” + winner.getPoints() + “ point(s).”);

numRounds++;

line.enqueue(challenger);

challenger = line.dequeue();

}

System.out.println(“The winner is ” + winner.getName() + “!!!”);

}

private static Team compete(Team t1, Team t2){

double whoWins = Math.random();

if(whoWins < 0.5) //50% either team will win

return t1;

else

return t2;

}

}

[OPTIONAL] 5. [15 minutes] An animal shelter holds only dogs and cats, and operates on a strictly “first in, first out” basis. People must adopt either the “oldest” (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog and dequeueCat. You may use the built-in LinkedList data structure (has “addLast” method to insert an element at the end of the list, “poll” method to pop the first element of the list and “peek” method to get the first element).

Hint: Implement based on the abstract class Animal, you can define extend class Cat and Dog based on this Animal class. The definition of Animal is like:

public abstract class Animal {

private int order;

private String name;

public Animal (String n) {

name = n;

}

public void setOrder (int ord) {

order = ord;

}

public int getOrder () {

Return order;

}

}

public class Dog extend Animal {

public Dog (String n) {

super(n);

}

}

public class Cat extend Animal {

public Cat (String n) {

super(n);

}

}

public abstract class Animal {

private int order;

private String name;

public Animal (String n) {

name = n;

}

public void setOrder (int ord) {

order = ord;

}

public int getOrder () {

Return order;

}

}

public class Dog extend Animal {

public Dog (String n) {

super(n);

}

}

public class Cat extend Animal {

public Cat (String n) {

super(n);

}

}

Public class Animal Queue {

private int order = 0; //global time, acts as timestamp

public void enqueue (Animal a) {

a.setOrder (order);

order++;

if (a instanceof Dog)

else if (a instanceof Cat)

}

public Animal dequeueAny() {

if (doglist.size()==0)

return dequeueCats();

else if (catlist.size()==0)

return dequeueDogs();

Dog dog = doglist.peek();

Cat cat = catlist.peek();

if (dog.getOrder() < cat.getOrder)

return dequeueDogs();

else

return dequeueCats();

}

public Dog dequeueDogs() {

return doglist.poll();

}

public Cat dequeueCats() {

return catlist.poll();

}

}