Review 7: Stacks & queues: Questions

7.1.1.

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());
        }
    }
}

7.1.2.

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());

7.1.3.

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 2 + f(3) 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.

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);

7.1.4.

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);
    }
}

7.1.5.

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;
    }
}

7.2.1.

Name and describe at least three of the four operations of the discussed Queue ADT.

7.2.2.

How are the concepts of stack and queue different?

7.2.3.

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.

7.2.4.

Complete the following method to echo back all strings typed by the user after the user finally types end. Example transcript (user input in boldface):

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();

7.2.5.

Explain why an ArrayList is a poor choice to use for implementing the Queue interface.

7.2.6.

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;
    }
}

7.2.7.

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?

7.2.8.

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) {

Review 7: Stacks & queues: Solutions

7.1.1.

professor
millionaire

7.1.2.

cook
alum
president

7.1.3.

        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();
}

7.1.4.

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();
        }
    }
}

7.1.5.

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();
        }
    }
}

7.2.1.

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.

7.2.2.

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.

7.2.3.

a.	stack
b.	queue
c.	queue

7.2.4.

            q.add(user);
            if(user.equals("end")) break;
        }

        while(!q.isEmpty()) {
            System.out.println(q.remove());
        }
    }
}

7.2.5.

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.

7.2.6.

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;
    }

7.2.7.

It would correspond to a preorder traversal.

7.2.8.

        data[rear] = value;
        rear++;
        if(rear == data.length) rear = 0;
    }
}