Home
Syllabus
Assignments
Tests
printable version
Section 7.1:
[1]
[2]
[3]
[4]
[5]
Section 7.2:
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
Given the two classes below, what will main
print?
public class Worker { private String job; public Worker(String val) { job = val; } public void setJob(String val) { job = val; } public String getJob() { return job; } }public class Main { public static void main(String[] args) { Stack<Worker> s = new Stack<Worker>(); Worker you = new Worker("student"); Worker me = new Worker("professor"); s.push(you); s.push(me); you.setJob("millionaire"); me = you; while(!s.isEmpty()) { Worker w = s.pop(); System.out.println(w.getJob()); } } }
professor millionaire
Using the same Worker class of the previous problem, what will the following print?
Stack<Worker> s = new Stack<Worker>();
Worker you = new Worker("student");
Worker me = new Worker("professor");
Worker he = new Worker("cook");
s.push(me);
s.push(you);
s.push(he);
you.setJob("alum");
he = me;
he.setJob("president");
me = you;
System.out.println(s.pop().getJob());
System.out.println(s.pop().getJob());
System.out.println(s.pop().getJob());
cook alum president
Using the discussed Stack class,
complete the following method so that it checks whether the
parentheses and braces in a string match properly.
For example, they match in
but not in 2 + f(3)
or
2 + f(3}
It can accomplish this by stepping through the string and using
a stack to track the unmatched parentheses and braces found.{2+f)3(}.
public static boolean parenthesesMatch(String s) {
Stack<String> found = new Stack<String>();
for(int i = 0; i < s.length(); i++) {
String cur = s.substring(i, i + 1);
if(cur.equals("(") || cur.equals("{")) {
found.push(cur);
} else if(cur.equals(")")) {
if(found.isEmpty() || !found.pop().equals("(")) {
return false;
}
} else if(cur.equals("}")) {
if(found.isEmpty() || !found.pop().equals("{")) {
return false;
}
}
}
return found.isEmpty();
}
Convert the following recursive method to a non-recursive equivalent that closely resembles the original in terms of how it executes.
public int combinations(int n, int r) {
if(r == 0 || n == r) {
return 1;
} else {
return combinations(n - 1, r) + combinations(n - 1, r - 1);
}
}
class CombFrame {
int n;
int r;
int state;
int save;
CombFrame(int n, int r) {
this.n = n;
this.r = r;
this.state = 0;
}
}
public int combinations(int n, int r) {
Stack<CombFrame> stack = new Stack<CombFrame>();
stack.push(new CombFrame(n, r));
int ret = 0;
while(!stack.isEmpty()) {
CombFrame frame = stack.peek();
if(frame.state == 0) {
if(frame.r == 0 || frame.n == frame.r) {
ret = 1;
stack.pop();
} else {
stack.push(new CombFrame(frame.n - 1, frame.r));
frame.state = 1;
}
} else if(frame.state == 1) {
frame.save = ret;
stack.push(new CombFrame(frame.n - 1, frame.r - 1));
frame.state = 2;
} else {
ret += frame.save;
stack.pop();
}
}
}
Convert the below recursive method into a non-recursive equivalent that mimics the same program stack behavior using its own stack.
public int compute(int n) {
if(n <= 2) {
return n;
} else {
int a = compute(n - 1);
int b = compute(n - 2);
int c = compute(n - 3);
return 2 * c + b - 2 * a;
}
}
class Frame {
int n;
int a;
int b;
int state;
Frame(int n) { this.n = n; this.state = 0; }
}
public int compute(int n) {
Stack<Frame> stack = new Stack<Frame>();
stack.push(new Frame(n));
int ret = 0;
while(!stack.isEmpty()) {
Frame frame = stack.peek();
if(frame.state == 0) {
if(frame.n <= 2) {
ret = frame.n;
stack.pop();
} else {
stack.push(new Frame(frame.n - 1));
frame.state = 1;
}
} else if(frame.state == 1) {
frame.a = ret;
stack.push(new Frame(frame.n - 2));
frame.state = 2;
} else if(frame.state == 2) {
frame.b = ret;
stack.push(new Frame(frame.n - 3));
frame.state = 3;
} else if(frame.state == 3) {
int c = ret;
ret = 2 * c + frame.b - 2 * frame.a;
stack.pop();
}
}
}
Name and describe at least three of the four operations of the discussed Queue ADT.
add adds an element to the back of the
queue.
remove removes and returns the element at the
front of the queue.
peek returns the element currently at the
front of the queue (without removing it).
isEmpty returns true when the queue
contains no elements.
How are the concepts of stack and queue different?
With a stack, additions and removals are made on the same end, whereas with a queue, removals come from the opposite end that additions occur.
Which ADT does each of the following situations from real-life grocery shopping most closely resemble?
a. Customers purchasing canned goods pull cans from the front of the shelf. Employees restocking the shelves place cans at the front of the shelf.
b. Customers purchasing milk cartons pull cartons from the front of the refrigerator. Employees have a walk-in area behind the shelves from which they restock.
c. Customers purchasing bulk cereal pull a lever that allows cereal to fall out of the bottom of the bin. Employees restock the bin by dumping cereal into its top.
| a. | stack |
| b. | queue |
| c. | queue |
Complete the following method to echo back all strings
typed by the user after the user finally types
Example transcript (user input in boldface):end.
this illustrates a queue end this illustrates a queue end
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Queue q = new LinkedList<String>();
while(true) {
String user = in.nextLine();
q.add(user);
if(user.equals("end")) break;
}
while(!q.isEmpty()) {
System.out.println(q.remove());
}
}
}
Explain why an ArrayList is a poor choice to use for implementing the Queue interface.
For an ArrayList holding n elements,
adding or removing from its beginning takes
O(n) time.
If we use an ArrayList, either the queue's beginning or the
queue's end will map to the first index of the ArrayList;
whichever end we map of the ArrayList's beginning, the
respective operation will take O(n) time.
This is much worse than the hoped-for O(1) performance for
both add and remove, which is supported by a
LinkedList, for example.
Using the ListNode class below,
write an implementation of Queue called LinkedQueue.
Neither add nor
remove should require stepping through the
entire queue. You need not worry about throwing
exceptions when appropriate.
(Your definition should not make use of an array or any of
the built-in List classes.)
public class ListNode<E> {
private E val;
private ListNode next;
public ListNode(E v, ListNode n) {
val = v; next = n;
}
public E getValue() { return val; }
public ListNode getNext() { return next; }
public void setValue(E v) { value = v; }
public void setNext(ListNode<E> n) {
next = n;
}
}
public class LinkedQueue<E>
implements Queue<E> {
private ListNode<E> head;
private ListNode<E> tail;
public LinkedQueue() {
head = null;
tail = null;
}
public boolean isEmpty() {
return head == null;
}
public E peek() {
return head.getValue();
}
|
public void add(E value) {
ListNode<E> n = new ListNode<E>(value, null);
tail.setNext(n);
tail = n;
if(head == null) head = tail;
}
public E remove() {
E ret = head.getValue();
head = head.getNext();
if(head == null) tail = null;
return ret;
}
|
We saw the following method to display the values in a tree
in level order. (I've swapped the if lines.)
public static void printLevelOrder(TreeNode root) {
Queue<TreeNode> unexplored = new LinkedList<TreeNode>();
unexplored.add(root);
while(!unexplored.isEmpty()) {
TreeNode n = unexplored.remove();
System.out.println(n.getValue());
if(n.getRight() != null) unexplored.add(n.getRight());
if(n.getLeft() != null) unexplored.add(n.getLeft());
}
}
Suppose unexplored were a Stack instead of a Queue
(and we used push rather than add and
pop rather than remove). What is the name
of the order in which the program would now display the
nodes?
It would correspond to a preorder traversal.
We saw that an array could be used to implement a queue
efficiently using the concept of a circular buffer.
Complete the constructor method and the add method in the
below class using
this concept; you can assume that remove,
peek,
and isEmpty would follow.
public class ArrayQueue<E> implements Queue<E> {
private E[] data;
private int front;
private int rear;
public ArrayQueue(int capacity) {
data = (E[]) new Object[capacity + 1];
front = 0;
rear = 0;
}
public void add(E value) {
data[rear] = value;
rear++;
if(rear == data.length) rear = 0;
}
}