summaryrefslogtreecommitdiff
path: root/04-27.md
diff options
context:
space:
mode:
Diffstat (limited to '04-27.md')
-rw-r--r--04-27.md263
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