Post-class 04/27

1 files changed, 263 insertions, 0 deletions

diff --git a/04-27.md b/04-27.md
new file mode 100644
index 0000000..82d4ec8
--- /dev/null
+++ b/04-27.md
@@ -0,0 +1,263 @@
+[\<- 04/24](04-24.md)
+
+---
+
+## Start
+
+- Today: Ch. 3+4
+- You are responsible for section 3.1
+- You are responsible for section 4.1
+- In other words, just the concepts of stacks and queues
+
+## List
+
+- A **list** is an ordered collection of items, which are not necessarily distinct. Ordered does not necessarily mean sorted, rather that there is a 1st, 2nd, ... ith, ... nth etc.
+- Two important types of lists are:
+	1. stacks
+	2. queues
+
+- We can look up items by position (indexing) on a list. Sometimes also by name/id/key, but position is usually more important
+
+## Stack - Concept
+
+- Concept:
+	- A **stack** is a **linear list** in which all additions and deletions are restricted to one end, called the top
+
+- Nomenclature
+	- insert = push
+	- remove/delete = pop
+
+- Feature:
+	- A stack obeys last-in/first-out order (LIFO). The last item inserted into the stack is always the first to be removed
+
+## Stack - Example
+
+- We can think of a stack where we need to remember a bunch of things and always go back to the **most recent** thing
+
+- Examples:
+	- stack of plates
+	- back button on browser
+	- undo button
+
+## Stack - Implementation through Array
+
+- Let's consider implementing a stack using an array
+- Assume that we **use the end of the array** for push and pop. If there are **n** things in an array, the next available slot is slot ...?
+- Push
+	- Big-O: O(1)
+
+```
+//array is 'a'
+//'n' is the length of the array that is filled
+//'m' is the max length of the array
+
+assert(n < m); //make sure there is room to "push" a new element in the list
+a[n] = x;
+n++;
+```
+
+- Pop
+	- Big-O: O(1)
+
+```
+//array is 'a'
+//'n' is the length of the array that is filled
+//'m' is the max length of the array
+
+assert(n > 0); //avoid going oob
+x = a[n-1];
+n--;
+return x; //"pop" returns the "popped" element
+```
+
+---
+
+## Queue - Concept
+
+- Concept:
+	- A **queue** is a **linear list** in which data can only be inserted at one end, called the rear, and deleted from the other end, called the front
+
+- Nomenclature:
+	- insertion = enqueue
+	- deletion = dequeue
+
+- Feature:
+	- A queue obeys **first-in/first-out order (FIFO)**. The first item inserted is always the first to be removed
+
+- In a queue we always remove **the oldest item** in the list
+	- they're often used to ensure fairness
+
+- We can think of a queue as a list in which insertions and deletions/removals **happen at opposite ends**
+
+## Queue - Examples
+
+- Standing in a line
+- A buffer
+- Netflix/Youtube Queue
+- Music Playlist
+
+## Queue - Implementation through Array (Method 1)
+
+- Let's consider implementing a queue through an array
+	- **Add at the end**, remove from the front (always keep the fron of the queue located at index 0)
+		- What's the big-O for insertion? Deletion?
+
+- Insertion
+	- Big-O: O(1)
+
+```
+//array is 'a'
+//'n' is the length of the array that is filled
+//'m' is the max length of the array
+
+assert(n < m);
+a[n] = x;
+n++;
+```
+
+- Deletion
+	- Big-O: O(n) (because of shifting)
+
+```
+//array is 'a'
+//'n' is the length of the array that is filled
+//'m' is the max length of the array
+
+assert(n > 0);
+x = a[0];
+n--;
+
+//need to shift everything down
+for(i = 0; i < n-1; i++){
+	a[i] = a[i+1];
+}
+
+return x;
+```
+
+- Note: Changing the add and remove side will not change the Big-O
+
+## Queue - Implementation through Array (Method 2)
+
+- Can we make both of them O(1)?
+	- There is no reason to force the front of the queue always to be in `items[0]`, we **can let it "move up" as items are dequeued**
+	- Use a variable "first"
+
+### Example
+
+- Example: we use **"first"** to indicate the **index of the oldest element**, **"count"** for the current number of elements
+
+|deq <-|0|1|2|3|<- enq|
+|------|-|-|-|-|------|
+|      |~|~|~|~|      |
+
+- enq 3 (queue if often abbreviated "q")
+	- count = 1
+	- first = 0
+
+|deq <-|0|1|2|3|<- enq|
+|------|-|-|-|-|------|
+|      |3|~|~|~|      |
+
+- enq 7 (queue if often abbreviated "q")
+	- count = 2
+	- first = 0
+
+|deq <-|0|1|2|3|<- enq|
+|------|-|-|-|-|------|
+|      |3|7|~|~|      |
+
+- enq 4 (queue if often abbreviated "q")
+	- count = 3
+	- first = 0
+
+|deq <-|0|1|2|3|<- enq|
+|------|-|-|-|-|------|
+|      |3|7|4|~|      |
+
+- deq (you have no choice of what gets pop'd or deq'd)
+	- 3 comes out
+	- count = 2
+	- first = 1
+
+|deq <-|0|1|2|3|<- enq|
+|------|-|-|-|-|------|
+|      |~|7|4|~|      |
+
+- enq 7 
+	- count = 3
+	- first = 1
+
+|deq <-|0|1|2|3|<- enq|
+|------|-|-|-|-|------|
+|      |~|7|4|7|      |
+
+- deq
+	- 7 comes out
+	- count = 2
+	- first = 2
+
+|deq <-|0|1|2|3|<- enq|
+|------|-|-|-|-|------|
+|      |~|~|4|7|      |
+
+- enq 1
+	- Where to insert the 1?
+		- We "bend the array" into a circle
+		- insert in index 0
+	- count = 3
+	- first = 2
+
+|deq <-|0|1|2|3|<- enq|
+|------|-|-|-|-|------|
+|      |1|~|4|7|      |
+
+---
+
+- How do you create a circle in your code?
+	- **mod (%)**
+	- so we just have to do all our arithmetic **modulo the size of the array**
+
+- Let's treat the indices as if the array was circular. This is known as a **circular** buffer
+- To accomplish this, we'll do all our arithmetic modulo the size of the array
+- Three variables:
+	- length = length of the buffer
+	- count = # of things in the buffer
+	- first = location of the first item
+
+- enq
+	- Big-O: O(1)
+
+```
+//array is 'a'
+//'x' is the new value
+
+assert(count < length);
+a[(count + first) % length] = x;
+count++;
+```
+
+- deq
+	- Big-O: O(1)
+
+```
+//array is 'a'
+//'x' is the new value
+
+assert(count > 0);
+x = a[first];
+first = (first+1) % length;
+count--;
+return x;
+```
+
+## Summary: Queue and Stack (ADT)
+
+- Queue:
+	- Operations - enqueue and dequeue
+	- data structure - we've introduces array (possible to use others)
+- Stack:
+	- operations - push, pop, and top
+	- Data structure - we've introduced array (possible to use others)
+
+- Please note that Queue only allows operations on its two ends. Stack only allow operations on its top end