diff options
| -rw-r--r-- | 04-24.md | 3 | ||||
| -rw-r--r-- | 04-27.md | 263 |
2 files changed, 266 insertions, 0 deletions
@@ -117,3 +117,6 @@ A bag is an **unordered** collection of elements, which are **not necessarily di |**Remove One**|O(n)|O(n)|O(n) (worst case); O(1) (ideal case)| |**Remove All**|O(n)|O(n)|O(n) (worst case); O(1) (ideal case)| +--- + +[04/27 ->](04-27.md) 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 |