3. Bags, Queues, and Stacks Flashcards
Generics
An essential characteristic of collection ADTs is that we should be able to use them for any type of data. A specific Java mechanism known as generics enables this capability. The notation <Item> after the class name in each of our APIs defines the name Item as a type parameter, a symbolic placeholder for some concrete type to be used by the client. You can read Stack<Item> as "stack of items." For example, you can write code such as</Item></Item>
Stack<String> stack = new Stack<String>();
stack.push("Test");
...
String next = stack.pop();</String></String>
to use a stack for String objects.
Autoboxing
Type parameters have to be instantiated as reference types, so Java automatically converts between a primitive type and its corresponding wrapper type in assignments, method arguments, and arithmetic/logic expressions. This conversion enables us to use generics with primitive types, as in the following code:
Stack<Integer> stack = new Stack<Integer>();
stack.push(17); // autoboxing (int -> Integer)
int i = stack.pop(); // unboxing (Integer -> int)</Integer></Integer>
Automatically casting a primitive type to a wrapper type is known as autoboxing, and automatically casting a wrapper type to a primitive type is known as unboxing.
Iterable collections:
For many applications, the client’s requirement is just to process each of the items in some way, or to iterate through the items in the collection. Java’s foreach statement supports this paradigm. For example, suppose that collection is a Queue<Transaction>. Then, if the collection is iterable, the client can print a transaction list with a single statement:</Transaction>
for (Transaction t : collection)
StdOut.println(t);
Bags
A bag is a collection where removing items is not supported—its purpose is to provide clients with the ability to collect items and then to iterate through the collected items.
//Stats.java is a bag client that reads a sequence of real numbers from standard input and prints out their mean and standard deviation.
public class Stats {
public class Stats {
public static void main(String[] args) {
// read in numbers
Bag<Double> numbers = new Bag<Double>();
while (!StdIn.isEmpty()) {
numbers.add(StdIn.readDouble());
}
int n = numbers.size();
// compute sample mean
double sum = 0.0;
for (double x : numbers)
sum += x;
double mean = sum/n;
// compute sample standard deviation
sum = 0.0;
for (double x : numbers) {
sum += (x - mean) * (x - mean);
}
double stddev = Math.sqrt(sum/(n-1));
StdOut.printf("Mean: %.2f\n", mean);
StdOut.printf("Std dev: %.2f\n", stddev);
} }
FIFO queues.
A FIFO queue is a collection that is based on the first-in-first-out (FIFO) policy. The policy of doing tasks in the same order that they arrive is one that we encounter frequently in everyday life: from people waiting in line at a theater, to cars waiting in line at a toll booth, to tasks waiting to be serviced by an application on your computer.
Pushdown stack
A pushdown stack is a collection that is based on the last-in-first-out (LIFO) policy. When you click a hyperlink, your browser displays the new page (and pushes onto a stack). You can keep clicking on hyperlinks to visit new pages, but you can always revisit the previous page by clicking the back button (popping it from the stack).
//Reverse.java is a stack client that reads a sequence of integers from standard input and prints them in reverse order.
public class Reverse {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<Integer>();
while (!StdIn.isEmpty()) {
stack.push(StdIn.readInt());
}
for (int i : stack) {
StdOut.println(i);
}
}
}</Integer></Integer>
Arithmetic expression evaluation
Evaluate.java is a stack client that evaluates fully parenthesized arithmetic expressions. It uses Dijkstra’s 2-stack algorithm:
Push operands onto the operand stack.
Push operators onto the operator stack.
Ignore left parentheses.
On encountering a right parenthesis, pop an operator, pop the requisite number of operands, and push onto the operand stack the result of applying that operator to those operands.
This code is a simple example of an interpreter.
Evaluate.java
public class Evaluate {
public static void main(String[] args) {
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();</Double></Double></String></String>
while (!StdIn.isEmpty()) {
String s = StdIn.readString();
if (s.equals("(")) ;
else if (s.equals("+")) ops.push(s);
else if (s.equals("-")) ops.push(s);
else if (s.equals("*")) ops.push(s);
else if (s.equals("/")) ops.push(s);
else if (s.equals("sqrt")) ops.push(s);
else if (s.equals(")")) {
String op = ops.pop();
double v = vals.pop();
if (op.equals("+")) v = vals.pop() + v;
else if (op.equals("-")) v = vals.pop() - v;
else if (op.equals("*")) v = vals.pop() * v;
else if (op.equals("/")) v = vals.pop() / v;
else if (op.equals("sqrt")) v = Math.sqrt(v);
vals.push(v);
}
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
} }
Fixed-capacity stack of strings
FixedCapacityStackOfString.java implements a fixed-capacity stack of strings using an array.
//FixedCapacityStackOfStrings.java
import java.util.Iterator;
import java.util.NoSuchElementException;
public class FixedCapacityStackOfStrings implements Iterable<String> {</String>
private String[] a; // holds the items
private int n; // number of items in stack
// create an empty stack with given capacity
public FixedCapacityStackOfStrings(int capacity) {
a = new String[capacity];
n = 0;
}
//FixedCapacityStackOfStrings.java
public boolean isEmpty() {
return n == 0;
}
//FixedCapacityStackOfStrings.java
public boolean isFull() {
return n == a.length;
}
//FixedCapacityStackOfStrings.java
public void push(String item) {
a[n++] = item;
}
//FixedCapacityStackOfStrings.java
public String pop() {
return a[–n];
}
//FixedCapacityStackOfStrings.java
public String peek() {
return a[n-1];
}
//FixedCapacityStackOfStrings.java
public Iterator<String> iterator() {</String>
return new ReverseArrayIterator();
}
//FixedCapacityStackOfStrings.java
// an array iterator, in reverse order
public class ReverseArrayIterator implements Iterator<String> {</String>
private int i = n-1;
public boolean hasNext() {
return i >= 0;
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
return a[i--];
}
}
//FixedCapacityStackOfStrings.java
public static void main(String[] args) {
int max = Integer.parseInt(args[0]);
FixedCapacityStackOfStrings stack = new FixedCapacityStackOfStrings(max);
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals(“-“)) stack.push(item);
else if (stack.isEmpty()) StdOut.println(“BAD INPUT”);
else StdOut.print(stack.pop() + “ “);
}
StdOut.println();
// print what's left on the stack
StdOut.print("Left on stack: ");
for (String s : stack) {
StdOut.print(s + " ");
}
StdOut.println();
} }
Fixed-capacity generic stack.
FixedCapacityStack.java implements a generic fixed-capacity stack.
//FixedCapacityStack.java
import java.util.Iterator;
import java.util.NoSuchElementException;
public class FixedCapacityStack<Item> implements Iterable<Item> {</Item></Item>
private Item[] a; // holds the items
private int n; // number of items in stack
// create an empty stack with given capacity
public FixedCapacityStack(int capacity) {
a = (Item[]) new Object[capacity]; // no generic array creation
n = 0;
}
//FixedCapacityStack.java
public boolean isEmpty() {
return n == 0;
}
//FixedCapacityStack.java
public void push(Item item) {
a[n++] = item;
}
//FixedCapacityStack.java
public Item pop() {
return a[–n];
}
//FixedCapacityStack.java
public Iterator<Item> iterator() {</Item>
return new ReverseArrayIterator();
}
///FixedCapacityStack.java
/ an array iterator, in reverse order
public class ReverseArrayIterator implements Iterator<Item> {</Item>
private int i = n-1;
public boolean hasNext() {
return i >= 0;
}
//FixedCapacityStack.java
public boolean hasNext() {
return i >= 0;
}
//FixedCapacityStack.java
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
return a[i–];
}
//FixedCapacityStack.java
public static void main(String[] args) {
int max = Integer.parseInt(args[0]);
FixedCapacityStack<String> stack = new FixedCapacityStack<String>(max);
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) stack.push(item);
else if (stack.isEmpty()) StdOut.println("BAD INPUT");
else StdOut.print(stack.pop() + " ");
}
StdOut.println();</String></String>
// print what's left on the stack
StdOut.print("Left on stack: ");
for (String s : stack) {
StdOut.print(s + " ");
}
StdOut.println();
} }
Array resizing stack
ResizingArrayStack.java implements a generic stack using a resizing array. With a resizing array, we dynamically adjust the size of the array so that it is both sufficiently large to hold all of the items and not so large as to waste an excessive amount of space. We double the size of the array in push() if it is full; we halve the size of the array in pop() if it is less than one-quarter full.
//ResizingArrayStack.java
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* The {@code ResizingArrayStack} class represents a last-in-first-out (LIFO) stack
* of generic items.
* It supports the usual <em>push</em> and <em>pop</em> operations, along with methods
* for peeking at the top item, testing if the stack is empty, and iterating through
* the items in LIFO order.
* <p>
* This implementation uses a resizing array, which double the underlying array
* when it is full and halves the underlying array when it is one-quarter full.
* The <em>push</em> and <em>pop</em> operations take constant amortized time.
* The <em>size</em>, <em>peek</em>, and <em>is-empty</em> operations takes
* constant time in the worst case.
*/
public class ResizingArrayStack<Item> implements Iterable<Item> {</Item></Item>
//ResizingArrayStack.java
// initial capacity of underlying resizing array
private static final int INIT_CAPACITY = 8;
private Item[] a; // array of items
private int n; // number of elements on stack
/**
* Initializes an empty stack.
*/
public ResizingArrayStack() {
a = (Item[]) new Object[INIT_CAPACITY];
n = 0;
}
//ResizingArrayStack.java
/**
* Is this stack empty?
*/
public boolean isEmpty() {
return n == 0;
}
//ResizingArrayStack.java
/**
* Returns the number of items in the stack.
*/
public int size() {
return n;
}
//ResizingArrayStack.java
// resize the underlying array holding the elements
private void resize(int capacity) {
assert capacity >= n;
// textbook implementation
Item[] copy = (Item[]) new Object[capacity];
for (int i = 0; i < n; i++) {
copy[i] = a[i];
}
a = copy;
// alternative implementation
// a = java.util.Arrays.copyOf(a, capacity);
}
//ResizingArrayStack.java
/**
* Adds the item to this stack.
*/
public void push(Item item) {
if (n == a.length) resize(2*a.length); // double size of array if necessary
a[n++] = item; // add item
}
