Exercises - Using Queues

  1. Which abstract data type, stack or queue, would you choose to implement an "Undo" feature in a word processor? Which would you choose to store mouse click events when implementing a user interface?

    An "undo" feature is best implemented with a stack, while storing mouse click events is best implemented with a queue.

  2. If a class implements Iterable interface, what can you do with the class objects?

    One can iterate through the items of an object of that class. More specifically, one can use a "for-each" loop (sometimes called an "enhanced for-loop") to do this -- or one can get an iterator using the iterator() method and then use it's next() and hasNext() methods to iterate through the items of the object in question.

  3. What does the following code fragment print when n is 10? In general, what does it do for other positive integers n?

    Queue q = new Queue();
    q.enqueue(0);
    q.enqueue(1);
    for (int i = 0; i < n; i++) {
       int a = q.dequeue();
       System.out.println(a);
       int b = q.peek();
       q.enqueue(a + b);
    }
    

    0
    1
    1
    2
    3
    5
    8
    13
    21
    34
    
    In general, this code prints the first n terms of the Fibonacci sequence.

  4. Write a class BinaryCounter that prompts the user for a value $n$, and then uses a queue to generate and print all binary numbers with decimal values from $1$ to $n$, in a manner similar to the sample run shown below. Use the QueueArray implementation of the Queue interface to accomplish this task.

    $ java BinaryCounter↵
    Count in binary to what decimal value?
    8↵
    1
    10
    11
    100
    101
    110
    111
    1000
    
  5. Write a class ZerosAndNines that prompts the user for a value $n$, and then (using a queue) calculates and prints the least positive integer $x$ that is a multiple of $n$ and whose digits are only zeros or nines. Use the QueueArray implementation of the Queue interface to accomplish this task. Hint: knowing how to use a queue to generate consecutive binary numbers might prove helpful

    $ java ZerosAndNines↵
    Find smallest multiple (with digits of only zeros and nines) of what value?
    7↵
    9009
    
  6. Flavius Josephus

    A Jewish historian living in the 1st centruy named Flavius Josephus gave an account of the siege of Yodfat, where he and his 40 soldiers were trapped in a cave by Roman soldiers. Choosing suicide over capture, they settled on a serial method of committing suicide where each person to die would be killed by the next person to die. Josephus states that by luck or possibly the hand of God, he and another man remained until the end and surrendered to the Romans rather than killing themselves.

    The precise mechanism for choosing the order of the executions was not completely described in Josephus' account, however in 1612 Claude Gaspar Bachet (the writer of books on mathematical puzzles and tricks that formed the basis for almost all later books on mathematical recreations) suggested that the men arranged themselves in a circle, and then started counting by threes from a randomly selected man.

    Write a class Josephus that prompts the user for a number of people in a circle, and a value $n$, where every $n^{th}$ person will be killed, and then finds (using a queue) and displays the positions of those people killed, in the order they died, in a manner similar to the one shown in the sample run below.

    Use the QueueArray implementation of the Queue interface to accomplish this task.

    Hints: Note how similar moving through a circle is to moving someone from the front of a line to its end. Of course, if a person in the circle is killed -- that's more like removing them without adding them back.

    $ java Josephus↵
    Enter the total number of people in a circle:
    13↵
    Every nth person will be killed. What do you wish n to be?
    2↵
    Here are the people killed, in the order they died:
    2 4 6 8 10 12 1 5 9 13 7 3 11 
    
  7. Complete the class QueueFromStacks that implements the Queue interface but internally uses two stack instance variables to accomplish its required methods. The two stack objects created should be of the type described by the StackArray class, which implements the Stack interface. Add code only to the QueueFromStacks class, and only to the areas indicated by the comments included therein. Other than the given stack instance variable, use no variables (even local ones) that can hold a collection of values. That is to say, avoid the use of arrays, linked lists, deques, etc.

    Recall that items added to a queue are retrieved in the order they were added, while items added to a stack are retrieved in the reverse of the order they were added.

    With two stack instance variables, one can simply reverse this reverse order to create the desired queue behavior.

  8. Complete the class QueueFromStack that implements the Queue interface but internally uses a single stack instance variable to accomplish its required methods. This class depends on the StackArray class, which implements the Stack interface. Add code only to the QueueFromStack class, and only to the areas indicated by the comments included therein. Other than the given stack instance variable, use no variables (even local ones) that can hold a collection of values. That is to say, avoid the use of arrays, linked lists, deques, etc. You may add exactly one additonal method, if needed.

    There is another (hidden) stack available to you -- the function call stack. Consequently, you can overcome the limitation of a single stack instance variable by using recursion.

  9. The Game of War

    In the card game War, a standard 52-card deck is dealt to two players so that each player ends up with a pile of 26 cards. Let us call these players 1 and 2. One wins the game by taking all of one's opponent's cards. Niether player looks at his or her cards. Instead, player 1 removes the top card of his or her pile and places it face-up in the center of the table. Player 2 does the same with the top card from his or her pile. Whoever flipped over the higher ranked card takes both cards in the center and adds them to the bottom of their packet in the same order they were revealed. For the purposes of deciding which card is the higher card, cards are ranked in the normal way (with the Ace being the card of highest rank) : 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K, A. Suits are ignored. Both players then flip over the next card in their respective piles, again moving them to the center of the table and the process is repeated. This continues until one player wins by taking all of the cards.

    When the face-up cards on any given turn are of the same rank, there is a war. When this happens, the initial cards played stay on the table to form a small pile to which the players alternatively add their next three cards face-down. Finally, they each add one more card, face-up. These last two cards added face-up are again compared, and the player with the higher card takes all of the cards on the table (10 cards in total now) and adds them to the bottom of their pile. Whenever cards are added to the bottom of a player's pile, they are always added in the exact same order as the cards were played -- specifically, player 1's first card, player 2's first card, player 1's second card, etc. Should this second pair compared result again in a tie, three more face-down cards are played, and then one more face-up, with the player whose last card played is higher taking the entire stack of now 18 cards. In the unlikely event that there should still be a tie, this process is repeated until there is no tie or until someone doesn't have enough cards to continue. Should a player not have enough cards to complete their turn, they lose.

    You wish to simulate this game to predict on what turn the game ends and who wins given the initial states of the two players' piles. To this end, complete the War.java class by using the classes and interfaces described by Card.java, Pile.java, Queue.java, and QueueArray.java.

    Note:

    • The Card class can be used to represent individual cards from a standard deck and implements the Comparable interface, which uses the compareTo() method to compare to cards by their aforementioned rank.

    • The Pile class is a subclass of QueueArray<Card> that adds a constructor for creating a pile of cards from a string of two-character abbreviations for the cards the pile is supposed to contain. It also overrides the toString() method so that the cards in the pile can be displayed efficiently.

    • The QueueArray class is an array-based, iterable version of a queue, supporting the methods guaranteed by the Queue interface.

    • Your program should show the state of each player's pile on each turn, as shown in the sample run below. (This will help immensely in debugging, by the way!).

    • Every time compared cards have the same rank, your program should print "*** WAR! ***", as shown in the sample run below. Note, this means that occassionally (when multiple ties occur in the same turn) that this message may be printed more than once on the same turn.

    • Some games might be infinite. As such, your program needs only to identify on which turn the game ends and who wins if the number of turns required to do so is less than 5000. Otherwise, declare the game a draw.

    Sample Run:

    $ java War↵
    Enter Player 1's cards (from top to bottom):
    6h 3h Jc Ts 3c 7h 2h 9c 3s 7s 8c 5d Js Jh 6d Ah Qh 9d Ks 6c Kc Td Jc Th 9s Kd↵
    Enter Player 2's cards (from top to bottom):
    3d Qs Jd 8d Ad Tc Qc 9h 2d 5h 5c 5s 6s 7c 4c 7d Kh 8s Ac 4h 2c Qd As 4d 4s 2s↵
    Turn: 1
    
    player1:
    6h  3h  Jc  Ts  3c  7h  2h  9c  3s  7s  
    8c  5d  Js  Jh  6d  Ah  Qh  9d  Ks  6c  
    Kc  Td  Jc  Th  9s  Kd  
    
    player2:
    3d  Qs  Jd  8d  Ad  Tc  Qc  9h  2d  5h  
    5c  5s  6s  7c  4c  7d  Kh  8s  Ac  4h  
    2c  Qd  As  4d  4s  2s  
    --------------------------------------
    Turn: 2
    
    player1:
    3h  Jc  Ts  3c  7h  2h  9c  3s  7s  8c  
    5d  Js  Jh  6d  Ah  Qh  9d  Ks  6c  Kc  
    Td  Jc  Th  9s  Kd  6h  3d  
    
    player2:
    Qs  Jd  8d  Ad  Tc  Qc  9h  2d  5h  5c  
    5s  6s  7c  4c  7d  Kh  8s  Ac  4h  2c  
    Qd  As  4d  4s  2s  
    --------------------------------------
    Turn: 3
    
    player1:
    Jc  Ts  3c  7h  2h  9c  3s  7s  8c  5d  
    Js  Jh  6d  Ah  Qh  9d  Ks  6c  Kc  Td  
    Jc  Th  9s  Kd  6h  3d  
    
    player2:
    Jd  8d  Ad  Tc  Qc  9h  2d  5h  5c  5s  
    6s  7c  4c  7d  Kh  8s  Ac  4h  2c  Qd  
    As  4d  4s  2s  3h  Qs  
    --------------------------------------
                                            *** WAR! ***
    
    Turn: 4
    
    player1:
    9c  3s  7s  8c  5d  Js  Jh  6d  Ah  Qh  
    9d  Ks  6c  Kc  Td  Jc  Th  9s  Kd  6h  
    3d  
    
    player2:
    9h  2d  5h  5c  5s  6s  7c  4c  7d  Kh  
    8s  Ac  4h  2c  Qd  As  4d  4s  2s  3h  
    Qs  Jc  Jd  Ts  8d  3c  Ad  7h  Tc  2h  
    Qc  
    --------------------------------------
                                            *** WAR! ***
    
                                            *** WAR! ***
    
    Turn: 5
    
    player1:
    Qh  9d  Ks  6c  Kc  Td  Jc  Th  9s  Kd  
    6h  3d  9c  9h  3s  2d  7s  5h  8c  5c  
    5d  5s  Js  6s  Jh  7c  6d  4c  Ah  7d  
    
    
    player2:
    Kh  8s  Ac  4h  2c  Qd  As  4d  4s  2s  
    3h  Qs  Jc  Jd  Ts  8d  3c  Ad  7h  Tc  
    2h  Qc  
    --------------------------------------
    Turn: 6
    
    player1:
    9d  Ks  6c  Kc  Td  Jc  Th  9s  Kd  6h  
    3d  9c  9h  3s  2d  7s  5h  8c  5c  5d  
    5s  Js  6s  Jh  7c  6d  4c  Ah  7d  
    
    player2:
    8s  Ac  4h  2c  Qd  As  4d  4s  2s  3h  
    Qs  Jc  Jd  Ts  8d  3c  Ad  7h  Tc  2h  
    Qc  Qh  Kh  
    --------------------------------------
    .
    .
    .
    --------------------------------------
    Turn: 194
    
    player1:
    9d  Qs  4s  Ah  8c  
    
    player2:
    9h  6c  Ts  Qc  Kd  4d  Kc  7c  8d  6s  
    Qd  3h  Ad  2c  7d  2s  Tc  4h  5d  3d  
    Jh  3s  Js  3c  Jc  2d  7h  6h  Th  5s  
    Qh  4c  Td  5h  Jc  9s  Jd  7s  Kh  6d  
    9c  2h  Ks  8s  Ac  5c  As  
    --------------------------------------
                                            *** WAR! ***
    
    Turn: 195
    
    player1:
    
    
    player2:
    4d  Kc  7c  8d  6s  Qd  3h  Ad  2c  7d  
    2s  Tc  4h  5d  3d  Jh  3s  Js  3c  Jc  
    2d  7h  6h  Th  5s  Qh  4c  Td  5h  Jc  
    9s  Jd  7s  Kh  6d  9c  2h  Ks  8s  Ac  
    5c  As  9d  9h  Qs  6c  4s  Ts  Ah  Qc  
    8c  Kd  
    --------------------------------------
    player 2 wins!