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.

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].

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?

results matching ""

    No results matching ""