## Lecture 04. Data Structures - Part 1
- Arrays & Dynamic Arrays
- Stacks
- Queues
- Deques
Note:
Speaker notes here
---
### Data Structures Overview
<img src="https://cdn.ucode.vn/uploads/1/upload/zmrUxFYB.png" class="element-left content-img" />
Note:
- Java
- Each has pros and cons and specific use-cases
---
### Data Structures Overview
<img src="https://cdn.ucode.vn/uploads/1/upload/ojdBGGdO.png" height="600px"/>
---
### Arrays
- An array is a **contiguous block of memory** that store multiple items of the **same type** together.
- An array has a **fixed length** after initialization.
<img src="https://cdn.ucode.vn/uploads/1/upload/wMEmFvJu.png"/>
---
### Arrays
- 1D array: Memory Address (A[i])= Base Address (A) + Word Length * ( i - First Index)
- 2D array: Memory Address (A[i, j])= Base Address(A)+ Word Length * (n * (i-1) + (j-1))
<img src="https://cdn.ucode.vn/uploads/1/upload/wMEmFvJu.png"/>
---
### Arrays
- 3D array: 1) Depth index 2) Row index 3) Column index
<img src="https://cdn.ucode.vn/uploads/1/upload/hHDgjlQx.png"/>
---
### Array operations
- **Access:** Access an element in the array by its index one.
- **Search:** Searches an element in the array using the given the value.
---
### Array operations
- **Access:** $O(1)$
- **Search:** $O(n)$
- **Insertion:** Not supported
- **Deletion:** Not supported
---
### Array in Python
- `array.array`: space-efficient storage of basic **C-style** data types
```python=
import array
arr = array.array('f', (1.0, 1.5, 2.0, 2.5))
print(arr[1]) # 1.5
print(arr) # array('f', [1.0, 1.5, 2.0, 2.5])
arr[1] = 3.0 # Arrays are mutable
del arr[1] # fixed size?
arr.append(4.0)
print(arr) # array('f', [1.0, 2.0, 2.5, 4.0])
arr[1] = 'hello' # TypeError
```
---
### Array in Python
- `array.array`: Basic Typed Arrays
- `bytes`: Immutable Arrays of Single Bytes
- `bytearray`: Mutable Arrays of Single Bytes
- `numpy`: **fast** array implementations for scientific computing
---
### Dynamic Arrays
- **Dynamic array** (*growable array*, *resizable array*, *array list*) is a **random access**, **variable-size** list data structure.
<img src="https://cdn.ucode.vn/uploads/1/upload/gWBNmfkv.png"/>
Note:
that allows elements to be added or removed.
---
### Dynamic Arrays
- C++'s `vector` and Java's `ArrayList` are dynamic arrays
<img src="https://cdn.ucode.vn/uploads/1/upload/gWBNmfkv.png"/>
---
### Dynamic Array operations
- **Access:** $O(1)$
- **Search:** $O(n)$
- **Insertion:** $O(n)$
- **Deletion:** $O(n)$
- **Append:** $O(1)$
- **Pop:** $O(1)$
---
### Python List
A Python `list` is an `array`, a `dynamic array` or a `linked list`?
- Its size can be changed?
- Contains data of same types?
- Supports random access?
Note:
Everything in Python is an object, and that includes the numbers. There are no "primitive" types, only built-in types.
---
### Python List
- `a.insert(i, x)`: $O(n)$
- `a.pop(i)`: $O(n)$
- `del a[i]`: $O(n)$
- `del a[i:j]`: $O(n)$
- `a.remove(x)`: $O(n)$
- `a.index(x)`: $O(n)$
- `a.pop()`: $O(1)$
---
### Linked List
- Elements are **NOT** stored at **contiguous memory** locations
- The elements in a linked list are linked using **pointers**
<img src="https://cdn.ucode.vn/uploads/1/upload/lHcsemFg.png"/>
---
### Linked List - Advantages
- Dynamic allocation of memory
- Simple implementation
- **Insertion** and **deletion** are fast
---
### Linked List - Disadvantages
- Sequential access (no random access)
- Extra storage space for address fields
---
### Linked List
- **Access:** $O(n)$
- **Search:** $O(n)$
- **Insertion:** $O(1)$
- **Deletion:** $O(1)$
- **Sorting:** $O(n^2)$?
---
### Singly Linked List
<img src="https://cdn.ucode.vn/uploads/1/upload/icItCnhQ.png"/>
---
### Doubly Linked List
<img src="https://cdn.ucode.vn/uploads/1/upload/GvikVyeE.png"/>
---
### Circular Linked List
<img src="https://cdn.ucode.vn/uploads/1/upload/ghhiOWiK.png"/>
Circular doubly linked list?
---
### Linked list in Python
- Built-in: `collections.deque` (doubly linked list)
- 3rd-party: `llist`, `structlinks`
---
### Time complexity comparison
<img src="https://cdn.ucode.vn/uploads/1/upload/CefosZCB.png"/>
Note:
https://www.bigocheatsheet.com/
---
### Stacks
- A **linear** data structure that follows the principle of Last In First Out (**LIFO**)
- Two main operators:
- `push`: putting an item on top of the stack
- `pop`: removing an item on the top of the stack
---
### Stacks
<img src="https://cdn.ucode.vn/uploads/1/upload/TvDbNTsu.png"/>
---
### Stack operations
- `push`: Add an element to the top of a stack
- `pop`: Remove an element from the top of a stack
- `is_empty`: Check if the stack is empty
- `is_full`: Check if the stack is full
- `size`: The size of the stack
- `peek`: Get the value of the top element without removing it
---
### Stack Time Complexity
- For array-based implementation: both `push` and `pop` have **$O(1)$** time complexity.
- Other operators?
- For linked list based implementation?
---
### Stack in Python
- Using normal `list`
- Using `collections.deque`
- Using `queue.LifoQueue` $\rightarrow$ synchronized
Note:
The queue module implements multi-producer, multi-consumer queues. It is especially useful in threaded programming when information must be exchanged safely between multiple threads.
Both `LifoQueue` and `deque` claim to be thread-safe in the documentation.
`collections.deque` is an alternative implementation of unbounded queues with fast atomic `append()` and `popleft()` operations that do not require locking and also support indexing.
---
### Stack in Python
Normal `list` as a stack
- `push(x)`: `list.append(x)`
- `pop`: `list.pop()`
- `is_empty`: `len(list) == 0`
- `size`: `len(list)`
- `peek`: `list[-1]`
---
### Queues
- A **linear** data structure that follows the principle of First In First Out (**FIFO**)
- Two main operators:
- `enqueue`: adding an item on the end of the queue
- `dequeue`: removing an item from the front of the queue
---
### Queues
- `enqueue`: adding on the end
- `dequeue`: removing from the front
<img src="https://cdn.ucode.vn/uploads/1/upload/OqCLIDYs.png"/>
---
### Queue operations
- `enqueue`: Add an element to the end of a queue
- `dequeue`: Remove an element from the front of a queue
- `is_empty`: Check if the queue is empty
- `is_full`: Check if the queue is full
- `size`: The size of the queue
- `peek`: Get the value of the front element without removing it
---
### Queue Time Complexity
- For linked list based implementation: all operatoins are $O(1)$.
- For array-based implementation: not efficient
<img src="https://cdn.ucode.vn/uploads/1/upload/OaTVWEtD.png"/>
---
### Queue in Python
- Using normal `list` $\rightarrow$ **not efficient**
- Using `collections.deque`
- Using `queue.Queue` $\rightarrow$ synchronized (thread-safe)
---
### Queue in Python
Using `collections.deque`
- `enqueue(x)`: `deque.append(x)`
- `dequeue`: `deque.popleft()`
- `is_empty`: `len(deque) == 0`
- `is_full`: `len(deque) == deque.maxlen()`
- `size`: `deque.maxlen()`
- `peek`: `deque[0]` $\rightarrow$ complexity?
Note:
access item by index in `deque` generally is $O(n)$, but with some optimization, and both first and last item access are $O(1)$
---
### Queue types
- Simple Queue
- Circular Queue
- Double Ended Queue (deque)
- Priority Queue
---
### Simple Queue
<img src="https://cdn.ucode.vn/uploads/1/upload/vjGQTWaH.png"/>
- Not efficient to implement using arrays.
---
### Circular Queue
<img src="https://cdn.ucode.vn/uploads/1/upload/vNsXwsJU.png"/>
- Can be implemented efficiently using arrays.
---
### Double Ended Queue
<img src="https://cdn.ucode.vn/uploads/1/upload/BQSSYcwl.png"/>
- Generic: can also be used as `stack` and normal `queue`
---
### Priority Queue
<img src="https://cdn.ucode.vn/uploads/1/upload/JbbfGdIB.png"/>
$\rightarrow$ Next lecture!
---
### Problem: Sliding windows minimum
Given an array $A[N]$ and an integer $K$, find the minimum for each and every contiguous subarray of size $K$.
<img src="https://cdn.ucode.vn/uploads/1/upload/uMSVuUrU.png"/>
Note:
- https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/
- https://vnoi.info/wiki/algo/data-structures/deque-min-max
---
### Sliding windows minimum
<img src="https://cdn.ucode.vn/uploads/1/upload/HVNGSZap.png"/>
<!-- <img src="https://cdn.ucode.vn/uploads/1/upload/aPndSsSq.png"/> -->
- Naive Approach: nested loops, traverse through all $k$-length subarray.
---
### Sliding windows minimum
```python=
for i in range(K, N + 1):
windowMin = float("inf")
for j in range(i, i - K, -1):
windowMin = min(windowMin, A[j])
print(windowMin)
}
```
- Complexity: $O(K \times (N - K))$ time
---
### Sliding windows minimum: deque
- Create a deque `dq` of capacity $K$, that stores only **useful** elements of current window of $K$ elements.
- **Useful** element: greater than all other elements on right side of it in current window.
- These useful elements are maintained in **sorted (decending) order**.
- The element **at front** of the `dq` is the **largest** and element at rear/back of `dq` is the smallest of current window.
---
### Sliding windows minimum: deque
<img src="https://cdn.ucode.vn/uploads/1/upload/sAPaTDUc.png"/>
---
### Sliding windows minimum: deque
<img src="https://cdn.ucode.vn/uploads/1/upload/CFtJFazi.png"/>
---
### Sliding windows minimum: deque
<img src="https://cdn.ucode.vn/uploads/1/upload/QMRsDgwx.png"/>
---
### Sliding windows minimum: deque
<img src="https://cdn.ucode.vn/uploads/1/upload/ISiKIXxu.png" class="element-left content-img" />
---
### Sliding windows minimum: deque
```python=
```python=
dq = deque()
for i in range(N):
# Remove the elements which are out of this window
while dq and dq[0] <= i - K: dq.popleft()
# Remove all elements smaller than the current one
while dq and A[i] >= A[dq[-1]]: dq.pop()
# Add current element at the rear of dq
dq.append(i)
if i >= K-1:
print(A[dq[0]], end=" ")
```
Note:
```python=
from collections import deque
A = [1, 2, 3, 1, 4, 5, 2, 3, 6]
N = len(A)
K = 3
dq = deque()
for i in range(N):
# Remove the elements which are out of this window
while dq and dq[0] <= i - K:
dq.popleft()
# Remove all elements smaller than the currently being added element
while dq and A[i] >= A[dq[-1]]:
dq.pop()
# Add current element at the rear of dq
dq.append(i)
if i >= K-1: # print result since 1st window
print(A[dq[0]], end=" ")
```
---
### Sliding windows minimum: deque
```python=
dq = deque()
for i in range(N):
while dq and dq[0] <= i - K: dq.popleft()
while dq and A[i] >= A[dq[-1]]: dq.pop()
dq.append(i)
if i >= K-1: print(A[dq[0]], end=" ")
```
- Complexity?
---
### Sliding windows minimum: deque
```python=
dq = deque()
for i in range(N):
while dq and dq[0] <= i - K: dq.popleft()
while dq and A[i] >= A[dq[-1]]: dq.pop()
dq.append(i)
if i >= K-1: print(A[dq[0]], end=" ")
```
- `dq.append(i)`: $N$ times
- `dq.popleft()` + `dq.pop()` cannot exceed $N$ times
- Total: maximum $2N$ times $\rightarrow$ $O(n)$
---
## The End
---
{"metaMigratedAt":"2023-06-17T19:46:10.666Z","metaMigratedFrom":"YAML","title":"Thuc Nguyen's ADSA Course - Lecture 04. Data Structures - P1","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":13281,\"del\":1603}]"}