:+1: [2020 競技程設教材 HackMD Book](https://hackmd.io/@nckuacm/ryLIV6BYI) :+1:
2019 Week 3: Data Structures
=
資料結構 (data structure) 簡單說，是種對資料的有系統的整理，
通常一個資料結構的誕生是為了令在其之上運作的演算法，能更好的進行操作，或是為了提昇演算法的效率，甚至是為了方便解釋演算法的運作(抽象化)。
每種資料結構一般都是針對：**新增**，**刪除**，**修改**，**查詢**[^crud] 這些功能的效率及操作上的追求。
# Basic STL 介紹
STL 全名 Standard Template Library
由容器 (containers)、迭代器 (Iterators)、演算法 (Algorithms)、函式 (Functions) 4 種元件組成。
>可以將容器簡單視為一種資料結構
延續第二週，我們將再介紹幾個常用的 STL 裡的容器及函式，還有迭代器
絕大部分 STL 的東西只要涉及區間的操作，==區間表示一律為左閉右開==[^start_at_zero]
這週介紹的 `std::queue`, `std::stack`, `std::list` 將會先給出簡易實作，接著再介紹三者在 STL 裡的用法。
推薦的參考網站： [cplusplus.com](http://www.cplusplus.com/)、[C++ reference](https://en.cppreference.co)
## Iterator
假設容器 `C`，已經裝了一些元素，若想遍歷 `C` 中的所有元素，那要如何做到呢?
有些容器是沒有 index 可以隨機存取的 (例如： `std::list`)，
為處理此問題，STL 為每個容器提供一個成員型別：**迭代器 (Iterator)**
可用"指標"的概念理解迭代器
>實際上，指標算是一種迭代器
假設迭代器 `it`，存取 `it` 所指向的內容，就用 `*it`
迭代器有 3 類：
- 隨機存取迭代器：能夠和整數的加減法，後移 $n$ 項、前移 $n$ 項
- 雙向迭代器：只能做遞增 (`++`)、遞減 (`--`)
- 單向迭代器：只能做遞增 (`++`)
回憶第二週的介紹：
`v.begin()`: v 的起始地址
`v.end()`: v 的末端地址 + 1 (由於左閉右開)
與 `vector` 相似，大部分的容器都有 `.begin()` 與 `.end()` 成員函式
且它倆都會回傳一個迭代器。
## queue
要搭公車之前，都是先*排隊*進入公車站，等到公車到來時，再從公車站出去搭上公車；
由此，公車站可以作為一種資料結構，人可類比為欲儲存之資料
 [^4]
此種資料結構稱作*隊列* (Queue)；擁有**先進先出 (First In, First Out)** 的特性。
例如在郵局要辦事，會先從機器拿號碼紙等叫號，這時候就是用隊列去儲存編號。
下面給出隊列的簡易實作程式碼：
```cpp
int Q[maxn], front_idx = 0, back_idx = 0;
void enqueue(int data)
{ Q[back_idx++] = data; }
int front()
{ return Q[front_idx]; }
bool empty()
{ return front_idx == back_idx; }
void dequeue()
{ if(!empty()) front_idx++; }
```
當我們操作多次 `enqueue` 與 `dequeue`，會使得 `front_idx` 最終會碰到陣列邊界，這樣會導致能儲存的資料量變小。
觀察發現，當 `front_idx` 增加，相當於丟掉以前的資料，這時候就有舊的空間空出來了，該如何使用這塊舊空間呢？
直接的，讓 `back_idx` 碰到邊界後回去初始位置就可以了： 這種資料結構稱作*環狀隊列*
還有種變種隊列，叫做*雙端隊列*(**D**ouble **e**nded **que**ue)，他可以從前面或後面 `enqueue` 或 `dequeue`。
### `std::queue`
```cpp
#include <queue>
using std::queue;
```
#### 宣告：
`queue<T> q`: `q` 為空的隊列，且各元素型別為 `T`
#### 函式：
`q.front()`: 第一個進入 `q` 的元素
`q.back()`: 最後一個進入 `q` 的元素
`q.push(T a)`: 將 `a` 加入 `q` 中 (enqueue)
`q.pop()`: 將第一個進入 `q` 的元素移除 (dequeue)
`q.empty(), q.size()`: `q` 當然也有這兩個函式
```cpp
queue<int> q; // []
q.push(1); // [1]
q.push(2); // [1, 2]
cout << q.front() << ' '; // 1
q.push(3); // [1, 2, 3]
cout << q.front() << ' '; // 1
q.pop(); // [2, 3]
q.pop(); // [3]
cout << q.front(); // 3
q.pop(); // []
```
```
< 1 1 3
```
#### 練習：
[UVa OJ 10935 Throwing cards away I](https://uva.onlinejudge.org/external/109/10935.pdf)
[UVa OJ 12100 Printer Queue](https://uva.onlinejudge.org/external/121/12100.pdf)
[Zero Judge c700 壞掉的隊列(queue)](https://zerojudge.tw/ShowProblem?problemid=c700) (建議讀完 stack 再來練習本題)
## stack
考慮將鬆餅每次只放一片疊到盤子上，則最後放上去的鬆餅將會是最上層的鬆餅，如果要吃會依序從最上層開始拿；
由此，盤子可以作為一種資料結構，鬆餅可類比為欲儲存之資料
[^5]
此種鬆餅(資料)的放法，拿法，是種稱做*堆疊* (stack) 的資料結構；有**後進先出 (Last In, First Out)** 的特性，
下面給出堆疊的簡易實作程式碼：
```cpp
int S[maxn], top_idx = -1;
void push(int data)
{ S[++top_idx] = data; }
int top()
{ return S[top_idx]; }
bool empty()
{ return top_idx == -1; }
void pop()
{ if(!empty()) top_idx--; }
```
相較於隊列的簡易實作版，堆疊不用擔心**已用過的**空間會永遠用不到
### `std::stack`
```cpp
#include <stack>
using std::stack;
```
#### 宣告：
`stack<T> st`: `st` 為空的堆疊，且各元素型別為 `T`
#### 函式：
`st.top()`: 存取最後一個進入 `st` 的元素
`st.push(T a)`: 將 `a` 加入 `st` 中
`st.pop()`: 將最後一個進入 `st` 的元素移除
```cpp
stack<int> st; // []
st.push(1); // [1]
st.push(2); // [1, 2]
st.push(3); // [1, 2, 3]
cout << st.top() << ' '; // 3
st.pop(); // [1, 2]
cout << st.top() << ' '; // 2
st.pop(); // [1]
cout << st.top(); // 1
st.pop(); // []
```
```
< 3 2 1
```
#### 練習：
[UVa OJ 514 Rails](https://uva.onlinejudge.org/external/5/514.pdf)
[UVa OJ 673 Parentheses Balance](https://uva.onlinejudge.org/external/6/673.pdf)
[UVa OJ 271 Simply Syntax](https://uva.onlinejudge.org/external/2/271.pdf)
[UVa OJ 11234 Expressions](https://uva.onlinejudge.org/external/112/11234.pdf)
## list
玩撲克牌遊戲時，常會有將牌拿起與將牌插到某個位置的動作
支援這兩個行為的資料結構稱為"連結串列 (Linked list)"[^doubly_linked_list]
[^6]
連結串列比較複雜點，需要造出兩種結構：
1. 定義一個結構叫做"節點(node)"，它可儲存**資料**及下個節點的**位置**
```cpp
struct node {
int data;
node *prev, *next;
} *list[maxn];
```
2. 當資料都放進節點後，要將節點們串起來
其中 `list[0]` 不當一般資料 (`.data`) 使用，它用來**指向**連接串列的頭
```cpp
for (int i = 0; i < N; i++) {
node *p = new node;
if(i) { // 0 or others
list[i-1]->next = list[i] = p;
list[i]->prev = list[i-1];
} else list[0] = p;
}
list[0]->prev = list[N-1];
list[N-1]->next = list[0];
```
在最後將 `list[0]`(head pointer) 與串列尾部連接起來，是為了下面兩個函式寫法上的方便(?
當擁有這樣的結構，拔除節點和插入節點只需 $O(1)$：
```cpp
void remove(int idx) {
list[idx]->prev->next = list[idx]->next;
list[idx]->next->prev = list[idx]->prev;
list[idx]->next = list[idx]->prev = NULL;
}
void insert(int idx1, int idx2) {
list[idx2]->next = list[idx1]->next;
list[idx1]->next = list[idx2];
list[idx2]->next->prev = list[idx2];
list[idx2]->prev = list[idx1];
}
```
> 比起 queue 和 stack，從頭刻 linked list 真的挺累的
### `std::list`
```cpp
#include <list>
using std::list;
```
#### 宣告：
`list<T> ls`: `ls` 為空的連接串列，且各元素型別為 `T`
#### 函式：
`insert`, `erase` 將回傳操作過後的迭代器位置 (最好自行實驗)
`ls.insert(iterator it, T a)`: 在 `it` 位置**前**插入 `a`
`ls.insert(iterator it, size_type n, T a)`: 在 `it` 位置**前**插入 `n` 個 `a`
`ls.erase(iterator it)`: 把 `it` 位置上的元素移除
`ls.erase(iterator l, iterator r)`: 把 $[l, r)$ 位置上的元素移除
```cpp
list<int> ls;
ls.push_back(1); // 1
ls.push_back(2); // 1 <-> 2
ls.push_front(3); // 3 <-> 1 <-> 2
cout << ls.front() << ' '; // 3
cout << ls.back(); // 2
```
```
< 3 2
```
```cpp
for (list<int>::iterator i = ls.begin(); i != ls.end(); i++)
cout << *i << ' ';
```
```
< 3 1 2
```
```cpp
list<int>::iterator it = ls.begin();
++it; ++it; // it points now to position 2 (start from 0)
ls.insert(it, 3, 100); // 3 <-> 1 <-> 100 <-> 100 <-> 100 <-> 2
for (list<int>::iterator i = ls.begin(); i != ls.end(); i++)
cout << *i << ' ';
```
```
< 3 1 100 100 100 2
```
此時 `it` 將指向第 $5$ 個位置 ($2 + 3$)
其中：
$2$ 是還未 `ls.insert(it, 3, 100)` 前的位置
$+3$ 因為插入了 $3$ 個 `100`
```cpp
--it; --it;
ls.erase(it, ls.end());
for (list<int>::iterator i = ls.begin(); i != ls.end(); i++)
cout << *i << ' ';
```
```
< 3 1 100
```
#### 練習：
[UVa OJ 11988 Broken Keyboard (a.k.a. Beiju Text)](https://uva.onlinejudge.org/external/119/11988.pdf)
[UVa OJ 245 Uncompress](https://uva.onlinejudge.org/external/2/245.pdf)
[Sprout OJ 21 陸行鳥大賽車](https://neoj.sprout.tw/problem/21/)
[Sprout OJ 20 中國人排隊問題](https://neoj.sprout.tw/problem/20/)
[^start_at_zero]: [Why numbering should start at zero](https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html)
[^crud]: [wikipedia/ 建立、讀取、更新、刪除](https://zh.wikipedia.org/wiki/%E5%BB%BA%E7%AB%8B%E3%80%81%E8%AE%80%E5%8F%96%E3%80%81%E6%9B%B4%E6%96%B0%E3%80%81%E5%88%AA%E9%99%A4)
[^doubly_linked_list]: 這裡介紹的是更為泛用的 doubly linked list 而非單純的 singly linked list
[^4]: [wikipedia/ Representation of a FIFO (first in, first out) queue](https://en.wikipedia.org/wiki/Queue_(abstract_data_type)#/media/File:Data_Queue.svg)
[^5]: [wikipedia/ Simple representation of a stack runtime with push and pop operations](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)#/media/File:Lifo_stack.png)
[^6]: [wikimedia/ DoubleLinkedListHsrw](https://commons.wikimedia.org/wiki/File:DoubleLinkedListHsrw.png)
Sign in with Wallet
Connect another wallet