path: root/04-27.md

[\<- 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

---

[05/01 ->](05-01.md)