Given the following stack, depicted here from top to bottom:
+ +
| 6 |
| 8 |
| 1 |
| 3 |
| 7 |
+---+
What would the stack look like after the following sequence of pushes and pops?
pop();
push(2);
push(9);
push(0);
pop();
push(7);
Solution: From left to right:
| 7 3 1 8 2 9 7
Given the following queue, depicted here from the back of the queue (left) to the front (right):
+-------------------+
| 3 | 8 | 1 | 5 | 2 |
+-------------------+
What would the queue look like after the following sequence of enqueues and dequeues?
dequeue(); // assume you simply throw away the value after dequeueing it
dequeue();
enqueue(9);
enqueue(3);
dequeue();
Solution:
3 9 3 8
Given the following MaxQueue, depicted here from the back of the queue (left) to the front (right):
+-------------------+
| 1 | 4 | 6 | 7 | 9 |
+-------------------+
Assuming that items in this priority queue are kept in max order, such that larger items leave the queue before smaller items, what would the queue look like after the following sequence of enqueues and dequeues?
getMax(); // assume you simply throw away the value after dequeueing it
insert(5);
getMax();
insert(12);
insert(2);
getMax();
Solution:
1 2 4 5 6
pop()
and push()
operations are
performed on a stack S. The push()
operations put the integers
0 through 9 onto S in order, and the pop()
operations print the
return value. That is, the sequence looks like this:
push(0); Pop and print 0 or more times; push(1); Pop and print 0 or more times; push(2); Pop and print 0 or more times;; .... push(9); Pop and print 0 or more times;Which of the following sequences could not occur as a result of such a sequence of stack operations (there may be more than one)?
9 8 7 6 5 4 3 2 1 0
8 7 6 5 4 3 2 1 0 9
4 3 2 1 0 5 6 7 8 9
4 6 8 7 5 3 2 9 0 1
Solution: Only number 4 could not occur.
insert()
and getMax()
operations are
performed on a MaxQueue M. The put()
operations put the integers
0 through 9 onto M in order, and the getMax()
operations print the
return value. That is, the sequence looks like this:
insert(0); getMax and print 0 or more times; insert(1); getMax and print 0 or more times; insert(2); getMax and print 0 or more times;; .... insert(9); getMax and print 0 or more times;
For each of the following sequences, state whether or not they could occur as a result of such a sequence of MaxQueue operations.
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 9 8 7
5 4 3 7 6 9 8 2 1 0
1 2 3 4 5 0 9 7 8 6
Solution: Only the last one could not occur!
0 1 2 3 4 5 6 7 8 9Is this the only sequence that you can produce, or is there is another sequence that is possible? Explain your answer by giving another sequence or explaining why the one given is the only possible sequence.
Solution: Yes, this is the only possible sequence, because we have defined the input sequence as ordered from 0 to 9, and a FIFO queue ALWAYS outputs in the same order as the input.
while(! Q.isEmpty() ) // push every element of Q onto the stack S.push( Q.dequeue() ); while(! S.isEmpty() ) // Enqueue every element popped off the stack Q.enqueue( S.pop() );How would you describe what you have done to the queue?
Solution: You have reversed the queue.
while(! M.isEmpty() ) // push every element of M onto the stack S.push( M.getMax() ); while(! S.isEmpty() ) // Insert every element popped off the stack M.insert( S.pop() );How would you describe what you have done to the priority queue? You may assume there are no duplicate numbers involved.
Solution: The MaxQueue is unchanged -- it is still in order!
while( !Q.isEmpty() ) M.insert( Q.dequeue() ); while( !M.isEmpty ) S.push( M.getMax() ); while( !S.isEmpty() ) Q.enqueue( S.pop() );How would you describe what you have done to the queue Q? You may assume there are no duplicate numbers involved.
Solution: Assuming M is a Max Queue, you have ordered the elements in the queue into reverse order (largest at rear, smallest at front); if M were a Min Queue, then you have ordered it into ascending order. The point is that M orders the elements, and S reverses them.
String s = "Hithere"; String t = "Folks"; String u = "CS112"; String v = s; s = t; t = v; u = s; System.out.println(s.charAt(0)); System.out.println(t.charAt(1)); System.out.println(u); System.out.println(v);
Solution:
F i Folks Hithere Explanation, line by line: String s = "Hithere"; // s points to "Hithere" String t = "Folks"; // t points to "Folks" String u = "CS112"; // u points to "CS112" String v = s; // both v and s point to "Hithere" s = t; // both s and t point to "Folks" t = v; // t, v, and s point to "Hithere" and only s points to "Folks" u = s; // s and u point to "Folks"; t, v, and s point to "Hithere" and none point to "CS112"