# Stacks and Queues & Elementary Sorts

## 1. Stacks and Queues

### 1.1. Stacks

- Stack of strings data type.
- Two ways to implement:
**Linked List**: Maintain pointer to first node in a linked list; insert/remove from front.**Array**: Use array s[] to store N items on stack.- Defect: Stack overflows when N exceeds capacity.

- Overflow and underflow.
- Underflow: throw exception if pop from an empty stack.
- Overflow: use resizing array for array implementation.

**Null items**. We allow null items to be inserted.**Loitering**(Java). Holding a reference to an object when it is no longer needed.- Already pop up the N-th item, should set it null before return.

#### Resizing Array Stack

- push(): double size of array s[] when array is full.
- pop(): halve size of array s[] when array is one-quarter full.
- Array is between 25% and 100% full.

### 1.2. Queues

Two ways to implement:

**Linked List**: Maintain pointer to first and last nodes in a linked list;**Array**:- Use array q[] to store items in queue.
- enqueue(): add new item at q[tail].
- dequeue(): remove item from q[head].
- Update head and tail modulo the capacity.
- Add resizing array.
- Q. How to resize?
- create another array with double size of the original array and duplicate all of the nodes in the new array
- create another array as the second array, and create a linkedlist to link the first queue and the second queue.

### 1.3. Generics

// ignore

### 1.4. Iterators

- Has methods hasNext() and next().

### 1.5. Applications(Dijkstra's two-stack algorithm)

## 2. Elementary Sorts

### 2.1. Selection Sort

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

### 2.2. Insertion sort

- Assume left side is already sorted, then in iteration
**i**, swap a[i] to the left if a[i] < a[i-1]

### 2.3. Shellsort

- Move entries more than one position at a time by
**h-sorting**the array. - Shellsort: which increment sequence to use?
- 3x + 1. 1, 4, 13, 40, 121, 364, …
- OK. Easy to compute.

- Sedgewick. 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, …
- Good. Tough to beat in empirical studies.

- 3x + 1. 1, 4, 13, 40, 121, 364, …

### 2.4. Shuffle

- One way is: Generate a random real number for each array entry, then sort the array.
- Defect: sorting.

- Better way:
**Knuth shuffle**- In iteration
**i**, pick integer**r**between**0**and**i**uniformly at random. - Swap
**a[i]**and**a[r]**.

- In iteration

### 2.5. Convex hull

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

#### Convex hull application

**Robot motion planning**. Find shortest path in the plane from**s**to**t**that avoids a polygonal obstacle.**Farthest pair problem**. Given N points in the plane, find a pair of points with the largest Euclidean distance between them.**Geometric properties**- Fact. Can traverse the convex hull by making only counterclockwise turns.
- Fact. The vertices of convex hull appear in increasing order of polar angle with respect to point p with lowest y-coordinate.

#### Graham scan demo

- Choose point p with smallest y-coordinate.
- Sort points by polar angle with p.
- Consider points in order; discard unless it create a counterclockwise turn.

- Given three points a, b, and c, is a → b→ c a counterclockwise turn?