| | |
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.
Which abstract data type, stack or queue, should one choose to use as a keyboard buffer? (When occasionally one types faster than the computer can keep up, a keyboard buffer stores the keys one has typed until the computer is ready for them.)
To ensure the letters are processed in the same order they are typed, use a queue.
Suppose an intermixed sequence of queue enqueue and dequeue operations are performed. The enqueues enqueue the integers 0 through 9 in order; the dequeues print out the returned value. Can the sequence 4 3 2 1 0 5 6 7 8 9 be printed as a result? If the answer is yes, indicate the sequence of enqueues and dequeues needed. If the answer is no, explain why.
No. Given that queues are first-in-first-out (FIFO) structures, the order of the returned values will always be identical to the order values were enqueued. In other words, since the enqueues enqueued the integers 0 through 9 in order, the printing will always result in 1 2 3 4 5 6 7 8 9 (assuming everything is eventually dequeued).
Suppose the variable stack references a stack of Integers objects, and the variable queue similarly references a queue of Integer objects. What is printed as a result of the following code snippet?
for (int i = 0; i < 6; i++)
stack.push(i);
for (int i = 0; i < 6; i++)
queue.enqueue(stack.pop());
while (queue.size() > 2) {
System.out.println(queue.dequeue());
queue.enqueue(queue.dequeue());
queue.enqueue(queue.dequeue());
}
5 2 4 0
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.
What does the following code fragment print when n is 10? In general, what does it do for other positive integers n?
Queueq = 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 34In general, this code prints the first n terms of the Fibonacci sequence.
The letters below are enqueued into a queue in the order they are given, while the dashes indicate a dequeue happens immediately after the letter preceding it has been enqueued. The queue is implemented using an array that doubles in size when the enqueued character would fill the array and halve its size when a dequeue would leave it one quarter full. Show the state of the internal array after each enqueue or dequeue, indicating the positions of both the "head" (the position of the next element to dequeue) and the "tail" (the position where the next element to be enqueued will go) for this queue.
A B C D - - E - -
enqueued A
index : 0 1
content: A .
H T
enqueued B
index : 0 1 2 3
content: A B . .
H T
enqueued C
index : 0 1 2 3
content: A B C .
H T
enqueued D
index : 0 1 2 3 4 5 6 7
content: A B C D . . . .
H T
dequeued A
index : 0 1 2 3 4 5 6 7
content: . B C D . . . .
H T
dequeued B
index : 0 1 2 3
content: C D . .
H T
enqueued E
index : 0 1 2 3
content: C D E .
H T
dequeued C
index : 0 1 2 3
content: . D E .
H T
dequeued D
index : 0 1
content: E .
H T
Note: For more practice with problems like this one, see the Trace QueueArray Operations Tool.
Consider the following code:
public class QueueRecurser {
static QueueArray queue = new QueueArray();
public int mystery(int n) {
if (n == 0)
return 1;
queue.enqueue(n);
return mystery(n-1) * queue.dequeue();
}
public static void main(String[] args) {
QueueRecurser qr = new QueueRecurser();
System.out.println(qr.mystery(4));
}
}
Starting with the invocation of qr.mystery(4), draw a snapshot of the queue after every enqueue and dequeue statement in the order they happen (in accordance with the recursive calls made).
In doing so, label each queue snapshot with the recursive call initiating the enqueue or dequeue, and indicate which of these two actions just happened (i.e., an enqueue or dequeue).
For example, the following shows snapshots of the queue after the first two such actions:
mystery(4), enqueue : H -> 4 <- T mystery(3), enqueue : H -> 4 3 <- T
What does mystery(4) return as a value?
More generally, for a given integer $n \ge 0$, what does mystery(n) calculate?
mystery(4), enqueue : H -> 4 <- T mystery(3), enqueue : H -> 4 3 <- T mystery(2), enqueue : H -> 4 3 2 <- T mystery(1), enqueue : H -> 4 3 2 1 <- T mystery(1), dequeue : H -> 3 2 1 <- T mystery(2), dequeue : H -> 2 1 <- T mystery(3), dequeue : H -> 1 <- T mystery(4), dequeue : H -> <-T (empty queue)
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
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
A Jewish historian living in the 1st century 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 classJosephus 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
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.
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 additional 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.
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 occasionally (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!