2020 競技程設教材 HackMD Book

2019 Week 3: Data Structures

資料結構 (data structure) 簡單說，是種對資料的有系統的整理，
通常一個資料結構的誕生是為了令在其之上運作的演算法，能更好的進行操作，或是為了提昇演算法的效率，甚至是為了方便解釋演算法的運作(抽象化)。
每種資料結構一般都是針對：新增，刪除，修改，查詢^[1] 這些功能的效率及操作上的追求。

Basic STL 介紹

STL 全名 Standard Template Library
由容器 (containers)、迭代器 (Iterators)、演算法 (Algorithms)、函式 (Functions) 4 種元件組成。

可以將容器簡單視為一種資料結構

延續第二週，我們將再介紹幾個常用的 STL 裡的容器及函式，還有迭代器
絕大部分 STL 的東西只要涉及區間的操作，區間表示一律為左閉右開^[2]

這週介紹的 std::queue, std::stack, std::list 將會先給出簡易實作，接著再介紹三者在 STL 裡的用法。

推薦的參考網站： cplusplus.com、C++ reference

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

要搭公車之前，都是先排隊進入公車站，等到公車到來時，再從公車站出去搭上公車；
由此，公車站可以作為一種資料結構，人可類比為欲儲存之資料

^[3]
此種資料結構稱作隊列 (Queue)；擁有先進先出 (First In, First Out) 的特性。
例如在郵局要辦事，會先從機器拿號碼紙等叫號，這時候就是用隊列去儲存編號。

下面給出隊列的簡易實作程式碼：

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 碰到邊界後回去初始位置就可以了： 這種資料結構稱作環狀隊列

還有種變種隊列，叫做雙端隊列(Double ended queue)，他可以從前面或後面 enqueue 或 dequeue。

std::queue

#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 當然也有這兩個函式

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
UVa OJ 12100 Printer Queue
Zero Judge c700 壞掉的隊列(queue) (建議讀完 stack 再來練習本題)

stack

考慮將鬆餅每次只放一片疊到盤子上，則最後放上去的鬆餅將會是最上層的鬆餅，如果要吃會依序從最上層開始拿；
由此，盤子可以作為一種資料結構，鬆餅可類比為欲儲存之資料

^[4]

此種鬆餅(資料)的放法，拿法，是種稱做堆疊 (stack) 的資料結構；有後進先出 (Last In, First Out) 的特性，

下面給出堆疊的簡易實作程式碼：

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

#include <stack>
using std::stack;

宣告：

stack<T> st: st 為空的堆疊，且各元素型別為 T

函式：

st.top(): 存取最後一個進入 st 的元素
st.push(T a): 將 a 加入 st 中
st.pop(): 將最後一個進入 st 的元素移除

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
UVa OJ 673 Parentheses Balance
UVa OJ 271 Simply Syntax
UVa OJ 11234 Expressions

list

玩撲克牌遊戲時，常會有將牌拿起與將牌插到某個位置的動作
支援這兩個行為的資料結構稱為"連結串列 (Linked list)"^[5]

^[6]

連結串列比較複雜點，需要造出兩種結構：

1. 定義一個結構叫做"節點(node)"，它可儲存資料及下個節點的位置

struct node {
  int data;
  node *prev, *next;
} *list[maxn];

2. 當資料都放進節點後，要將節點們串起來
   其中 list[0] 不當一般資料 (.data) 使用，它用來指向連接串列的頭

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)$：

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

#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)$ 位置上的元素移除

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

for (list<int>::iterator i = ls.begin(); i != ls.end(); i++)
  cout << *i << ' ';

< 3 1 2

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

--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)
UVa OJ 245 Uncompress
Sprout OJ 21 陸行鳥大賽車
Sprout OJ 20 中國人排隊問題

---

1. wikipedia/ 建立、讀取、更新、刪除 ↩︎

2. Why numbering should start at zero ↩︎

3. wikipedia/ Representation of a FIFO (first in, first out) queue ↩︎

4. wikipedia/ Simple representation of a stack runtime with push and pop operations ↩︎

5. 這裡介紹的是更為泛用的 doubly linked list 而非單純的 singly linked list ↩︎

6. wikimedia/ DoubleLinkedListHsrw ↩︎