# stacks and queues

## stack

stack: examine the item most recently added (last in; first out)

queue: examine the item least recently added (first in; first out)

Linked-list:

- every operation takes constant time
- use extra time and space to deal with links

Resizing array:

- evray operation takes constant amortized time, total time is much less
- less wasted space

### linked-list representation

in section 1.3.

Every operation takes constant time in the worst case.

A stack with N items use \(\sim 40N\)

#### Node()

```
private Node first=null;
private class Node
{
String item;
Node next;
}
```

#### pop()

```
// save item to return
String item = first.item;
// delete first node
first = first.next;
// return saved item
return item;
```

#### push()

```
// save a link to the list
Node oldfirst = first;
// create a new node for the beginning
first = new Node();
// set the instance variables in the new node
firt.item = newitem;
first.next = oldfirst;
```

### array implementation

- use array s[ ] to store N items on stack
- push(): add new item as s[N]
- pop(): remove item from s[N-1]

Use between \(\sim 8N\) (when full) and \(\sim 32N\) (when one-quarter full) bytes to represent a stack with N items.

Defect: stack overflows when N exceeds capacity.

## resizing arrays

How to grow and shrink array?

First try:

- push(): increase size of array s[ ] by 1.
- pop(): decrease size of array s[ ] by 1.

Too expensive.

- need to copy all item to a new array.
- inserting first N items takes time proportional to \(1+2+…+N \sim N^2/2\)

To grow array, if array is full, create a new array of twice the size, and copy items. Time proportional to N.

```
public ResizingArrayStackOfString()
{ s = new String[1]; }
public void push(String item)
{
if (N == s.length) resize(2*s.length);
s[N++] = item;
}
private void resize(int capacity)
{
String[] copy = new String[capacity];
for (i=0; i<N; i++)
copy[i] = s[i];
s = copy;
}
```

To shrink the array: halve size of array s[ ] when array is one-quarter full.

```
public String pop()
{
String item = s[--N];
s[N] = null;
if (N>0 && N == s.length/4) resize(s.length/2);
return item
}
```

Every operation takes constant amortized time.

## queues

maintain pointer to first and last nodes in a linked list;

insert/remove from opposite ends.

- insert at end of linked list
- remove from front of linked list

### linked-list

#### dequeue

same code as linked-list stack pop()

```
String item = first.item;
first = first.next;
if (isEmpty()) last = null;
return item;
```

#### enqueue

```
// save a link to the last node
Node oldlast = last;
// create a new node for the end
Node last = new Node();
last.item = "not";
last.next = null;
// linke the new node to the end of the list
if (isEmpty()) first = last;
else oldlast.next = last;
```

#### full

```
public boolean isEmpty()
{ return first == null; }
```

### resizing array

- use array q[ ] to store items
- enqueue(): add new item at q[tail]
- dequeue(): remove item from q[head]
- update head and tail modulo the capacity
- add resizing array

## generics

Want to implement StackOfURLs, StackOfInts, …

Avoid casting in client.

```
public class Stack<Item>
{
private class Node
{
Item item;
Node next;
}
// ...
public void push(Item item)
// ...
public Item pop()
// ...
}
```

Generic array creation is not allowed in java. Use cast

```
public FixedCapacityStack(int capacity)
{ s = (Item[]) new Object[capacity]; }
```

declare and initialize a Stack of integers

```
Stack<Integer> stack = new Stack<Integer>();
// in java 7
Stack<Integer> stack = new Stack<>();
```

## iterators

Support iteration over stack items by client, without revealing the internal representation of the stack. Make stack implement the **Iterable** interface.

Iterable: has a method that returns an Iterator

Iterator: has methods `hasNext()`

and `next()`

```
public interface Iterable<Item>
{
Iterator<Item> iterator();
}
public interface Iterator<Item>
{
boolean hasNext();
Item next();
// void remove();
}
// foreach statement(shorthand)
for (String s : stack)
StdOut.println(s);
```

Iterator in linked-list

```
import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>
{
...
public Iterator<Item> iterator()
{ return new ListIterator(); }
private class ListIterator implements Iterator<Item>
{
private Node current = first;
public boolean hasNext()
{ return current != null; }
public void remove()
{ /* not supported */ }
public Item next()
{
Item item = current.item;
current = current.next;
return item;
}
}
}
```

Array iterator

```
import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>
{
...
public Iterator<Item> iterator()
{ return new ReverseArrayIterator(); }
private class ReverseArrayIterator implements Iterator<Item>
{
private int i = N;
public boolean hasNext()
{ return i > 0; }
public void remove()
{/* not supported */ }
public Item next()
{ return s[--i]; }
}
}
```

### bag API

Adding items to a collection and iterating (order doesn’t matter)

Implementation: Stack without pop or queue without dequeue.

`Bag()`

: create an empty bag`void add(Item x)`

: insert a new item onto bag`int size()`

: number of items in the bag`Iterable<Item> iterator()`

: iterator for all items in bag

## applications

dangerous to use unfamiliar library.

```
java.util.list
java.util.Stack
java.util.Queue
```

Dijkstra’s two stack algorithm

# elementary sorts

## sorting introduction

Goal: sort any type of data (Double, String or java.io.File), without any information about the type of an item’s key.

Use callback = reference to executable code.

- client passes array of objects to sort() function
- the sort function calls back object’s
`compareTo()`

method as needed.

Call back implementation

- Java: interfaces
- C: function pointers
- C++: class-typle functions
- python, Javascript: first-class functions

```
// client
...
Insertion.sort(files);
...
// object implementation
public class File implements Comparable<File>
{
public int compareTo(File b) {...}
}
// sort implementation
public static void sort(Comparable[] a)
{
...
if (a[i].compareTo(a[j-1]) < 0 )
...
}
```

### comparable API

Implement `compareTo()`

so that `v.compareTo(w)`

:

- is a total order
- returns a negative integer, zero or positive integer
- throw an exception if incompatible types(or either is null)

### example

```
public class Date implements Comparable<Date>
{
private final int month, day, year;
public Date(int m, int d, int y)
{
month = m;
day = d;
year = y;
}
public int compareTo(Date that)
{
if (this.year < that.year ) return -1;
if (this.year > that.year ) return +1;
if (this.month < that.month) return -1;
if (this.month > that.month) return +1;
if (this.day < that.day ) return -1;
if (this.day > that.day ) return +1;
return 0;
}
}
```

### two useful functions

```
// less
private static boolean less(Comparable v, Comparable w)
{ return v.compareTo(w) < 0; }
// exchange
private static void exch(Comparable[] a, int i, int j)
{
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
```

## selection sort

- In iteration i, find index min of smallest remaining entry.
- Swap
`a[i]`

and`a[min]`

Quadratic time \(\sim N^2/2\)

```
int N = a.length;
for (i = 0; i<N; i++)
{
int min = i;
for (j = i+1；j<N; j++)
{
if (less(a[j],a[i])
min = j;
}
exchange(a, min, i);
}
```

## insertion sort

- In iteration i, swap a[i] with each larger entry to its left.

Best case: linear， linear for partially-sorted arrays;

Worst case: \(\sim N^2/2\) but slower than selection sort

```
int N = a.length;
for (int i = 0; i < N; i++)
for (int j = i; j > 0; j--)
if (less(a[j], a[j-1]))
exch(a, j, j-1);
else break;
```

## shellsort

Move entries more than one position (h positions) at a time by h-sorting the array.

### h-sorting

Insertion sort, with stride length h

h is an increment number like 7, 4, 1

A hm-sorted array remains hm-sorted after hn-sorted it.

### increment sequence

\(3x+1\)

Sedgewick: 1,5,19,41,109,209…

### code

worse case: \(O(N^{3/2})\)

```
int h = 1;
while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, ...
while (h >= 1)
{ // h-sort the array.
for (int i = h; i < N; i++)
{
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
exch(a, j, j-h);
}
h = h/3;
}
```

## shuffling

- generate a random real number for each array entry
- sort the array

Goal: rearrange array so that results is a uniformly random permutation in linear time.

### Knuth shuffle

- in iteration i, pick integer r between 0 and i uniformly at random
- swap
`a[i]`

and`a[r]`

```
int N = a.length;
for (i = 0; i < N; i++)
{
int r = StdRandom.uniform(i+1); // [0,i)
exch(a,i,r);
}
```

## convex hull

The convex hull of a set of N points it the smallest perimeter fence enclosing the points.

Output: sequence of vertices in counterclockwise order.

### Graham scan

- choose point p with smallest y-coordinate
- sort points by polar angle with p
- consider points in order; discard unless it create ccw turn

challenges:

- Find point p with smallest y-coordinate:

Define a total order, comparing by y-coordinate - Sort points by polar angle with respect to p

Define a total order for each point p - Determine whether \(p_1 \rightarrow p_2 \rightarrow p_3\) is a counterclockwise turn

Computational geometry - sort efficiently

Mergesort in \(N\log N\) time - handle degeneracies(three or more points on a line)

Require care, but not hard

### ccw

for 3 points a, b, c, signed area \(Area(a,b,c)\):

\[2\times Area(a,b,c) = \left\vert \begin{array}{ccc} a_{x} & a_{y} & 1 \\ b_{x} & b_{y} & 1\\ c_{x} & c_{y} & 1 \end{array} \right\vert = (b_x -a_x)(c_y-a_y)-(b_y-a_y)(c_x-a_x)\]

- Area > 0: \(a \rightarrow b \rightarrow c\) is counterclockwise
- Area < 0: \(a \rightarrow b \rightarrow c\) is clockwise
- Area = 0: \(a \rightarrow b \rightarrow c\) is collinear

### code

```
Arrays.sort(p, Point2D.Y_ORDER);
Arrays.sort(p, p[0].BY_POLAR_ORDER);
hull.push(p[0]);
hull.push(p[1]);
for (i = 2; i<N; i++)
{
Point2D top = hull.pop;
while (Point2D.ccw(hull.peek(), top, p[i]) <= 0 )
top = hull.pop;
hull.push(top);
hull.push(p[i]);
}
```