DS Queue Simulation: Hot Potato

Section 3.13 Queue Simulation: Hot Potato

One of the typical applications for showing a queue in action is to simulate a real situation that requires data to be managed in a FIFO manner. To begin, let’s consider the children’s game hot potato. In this game (see Figure 3.13.1) children line up in a circle and pass an item from neighbor to neighbor as fast as they can. At a certain point in the game, the action is stopped and the child who has the item (the potato) is removed from the circle. Play continues until only one child is left.

Figure 3.13.1. A Six-Person Game of Hot Potato

This game is a modern-day equivalent of the famous Josephus problem. Based on a legend about the famous first-century historian Flavius Josephus, the story is told that in the Jewish revolt against Rome, Josephus and 39 of his comrades held out against the Romans in a cave. With defeat imminent, they decided that they would rather die than be slaves to the Romans. They arranged themselves in a circle. One man was designated as number one, and proceeding clockwise they killed every seventh man. Josephus, according to the legend, was among other things an accomplished mathematician. He instantly figured out where he ought to sit in order to be the last to go. When the time came, instead of killing himself, he joined the Roman side. You can find many different versions of this story. Some count every third man and some allow the last man to escape on a horse. In any case, the idea is the same.

We will implement a general simulation of Hot Potato. Our program will input a list of names and a value, call it num to be used for counting how many times the potato is passed before the action is stopped. The method will return the name of the last person remaining after repetitive counting by num. What happens at that point is up to you.

To simulate the circle, we will use a queue (see Figure 3.13.2). Assume that the child holding the potato will be at the head of the queue. Upon passing the potato, the simulation will dequeue and then immediately enqueue that child, putting them at the end of the line. They will then wait until all the others have been at the head before it will be their turn again. After num dequeue/enqueue operations, the child at the front will be removed permanently and another cycle will begin. This process will continue until only one name remains (the size of the queue is 1).

Figure 3.13.2. A Queue Implementation of Hot Potato

The program is shown in Listing 3.13.3. A call to the hotPotato method using 7 as the counting constant returns "Susan".

import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.ArrayList;
import java.util.NoSuchElementException;

class Queue<T> {

ArrayList<T> items;

public Queue() {
        this.items = new ArrayList<T>();
    }

public boolean isEmpty() {
        return (this.items.isEmpty());
    }

public void enqueue(T item) {
        this.items.add(0, item);
    }

public T dequeue() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        return this.items.remove(this.size() - 1);
    }

public T peek() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        return this.items.get(this.size() - 1);
    }

public int size() {
        return this.items.size();
    }

public String toString() {

if (!this.items.isEmpty()) {
            String arrString = this.items.toString();
            return "tail ->" + arrString + "-> head";
        } else {
            return "<<empty queue>>";
        }
    }
}

^^^^
public class HotPotatoSimulation {

public static String hotPotato(String[] nameList, int num) {
        Queue<String> simQueue = new Queue<>();

for (String name: nameList) {
            simQueue.enqueue(name);
        }

while (simQueue.size() > 1) {
            // pass the potato: move person at head to tail
            for (int pass = 0; pass < num; pass++) {
                simQueue.enqueue(simQueue.dequeue());
            }

String removed = simQueue.dequeue(); // remove person at head
            System.out.println(removed + " is out of the game.");
        }
        return simQueue.dequeue();
    }

public static void main(String[] args) {
        String[] people = {"Bill", "David", "Susan", "Jane",
            "Kent", "Brad"};
        String lastPerson = hotPotato(people, 7);
        System.out.println("Last person is " + lastPerson + ".");
    }
}

Listing 3.13.3. Hot Potato Simulation

Note that in this example the value of the counting constant is greater than the number of names in the list. This is not a problem since the queue acts like a circle and counting continues back at the beginning until the value is reached. Also, notice that the list is loaded into the queue such that the first name on the list will be at the front of the queue. "Bill" in this case is the first item in the list and therefore moves to the head of the queue. A variation of this implementation, described in the exercises, allows for a random counter.

You have attempted of activities on this page.

Prev Top Next