###### tags: `MDCPP講義` # 基礎資料結構 **Author : 謝侑哲** --- ## 甚麼是資料結構(Data structure)? ---- 簡單來說 資料結構，就是一種儲存資料的方法 像是我們最常用的的陣列就算一種 除此之外還有很多種類，各有不同的特性 ---- 今天要講幾個最基本的: - 堆疊(stack) - 動態陣列(vector) - 隊列(deque) - 佇列(queue) --- ## 在開始之前 ---- 我們要先來介紹STL ---- STL $\rightarrow$ Standard Template Library Standard = 標準 , Template = 模板 , Library = 庫 就是C++內建的模板庫，可以讓你直接呼叫(競賽中也行) ---- STL 主要分成 **<span style="color: red">容器</span>**、演算法、迭代器、函式 而今天所教的資料結構都包含在STL容器中 這意味著你們不用手刻出整個資料結構了 ---- 不過不是所有資料結構都可以直接抓STL容器的 所以你們以後還是會碰到自己手刻的部分 --- ## 堆疊(stack) ---- 推疊就像你們帶了一堆書回家，卻一本都沒有讀 等打電動打到半夜，突然想到明天的考試 拿書時，一定得先從最上面的開始拿  ---- 所以它會是一個先進後出的結構 FILO, first in last out 這樣講很難懂吧，讓我們直接上圖 ----  ---- 一般常見的用法有: push( DT value ) 把東西從最上面塞進去 pop(DT value) 把東西從最上面拿出來 ---- empty() 判斷stack是否為空 空則 return true 有東西則 return false ---- size() 判斷stack的大小 以這張圖來說，pop完的size就會是6  ---- top() 得到stack疊頂端的值 以這張圖來說，return的值就會是4  ---- 看起來是個酷東西，那原理呢? 我有一個同學常跟我說，要學東西就從最底層學 可以學到最多 然後他現在一直想拖我去建一個CNN神經網路 看著現成的東西卻不能用，我感到非常難過 反正重點是再來教原理 ---- 想像有一個指針，它叫做top(這裡暫時用int存它) 而他一直指著stack的頂端 像這樣  ---- 現在進行push的動作 - 首先將top+1(往上移)  ---- - 接者讓top指到的位置變成要插入的值 - 也就是 stack[top] = value  這樣就完成push操作了 ---- 接下來是pop的動作 - 只要簡單的把top -1(下移) 就行了  ---- 你們可能會疑惑，不用把原本的位置清掉之類的嗎 事實上，我們只會對0~top之間的數做操作 因此刪不刪不會有影響 push時，也會直接把舊數字覆蓋掉 ---- 那size()就很簡單了 只要看你的top在哪裡就可以了 這張圖的top在 2的位置，所以回傳值會是3  ---- empty()也是一樣的概念 只要top<0，就是空stack return Ture ---- 以上的原理，以陣列實作如下: ```cpp= int top = 0; int st[1000]; top++; st[top] = a; // push(a)操作 top --;// pop()操作 cout << st[top] << "\n"; // top()操作 if(top < 0); // empty() int size = top; // size() ``` ---- 我們在更之前有提到STL容器 那要怎麼使用他呢? ---- 這樣就行了 ```cpp= #include <stack> signed main() { stack<int> st; st.push(123); //加入 st.pop(); //丟出 if(st.empty()); //判斷是否為空 st.top(); //獲得最上面的值 } ``` ---- 練習題: [Parentheses Balance](http://mdcpp.mingdao.edu.tw/problem/B005) --- ## 動態陣列(vector) ---- 還記得前面教的stack嗎，現在把她忘掉吧 因為這東西比他好用啊 ---- 他之所以叫做動態陣列 就是因為它是可以自動隨長度擴展的陣列 ---- 講白了，他就是個高階版本的陣列 跟stack不一樣的是它可以用vec[i]的方式來存取 而且時間複雜度幾乎是O(1) 也可以開多維來使用 ---- 除此之外，因為他是動態的關係，stack做得到的，他也都做得到 速度甚至比它還快 所我也不是很確定stack的存在意義 ---- 在vector中，主要有兩個重要的特性 size : 元素長度 capacity : 容器大小 ---- 用圖來講就是這樣  ---- 在一開始vector會開一個預設的capacity 當size超過capacity時，它就會開更長的記憶體 然後整個轉移它 ---- 這個做法感覺是個O(n)的作法 而且可能會有多次進行，導致常數很大 但如果只是打打題目，不看效率的話可以忽略它沒差 ---- 不過也有方法處理這個問題 ---- ### 方法一 在已知會用到的空間下，可以先把它的容量開大一點 ```cpp= vector<int> vec(1000000); ``` ---- ### 方法二 在不確定空間下 可以使用reserve(預留)函式來一次擴很大 ```cpp= vector<int> vec; vec.reserve(100); ``` ---- 因為它的原理滿複雜的 大概長這樣  我就不說了 現在就會用就好 ---- 再來講講它的常用功能 ---- 宣告 ```cpp= #include<vector> vector<int> vc; //宣告一個vector vc vector<int> vc(100); //宣告一個大小為100的vector vector<int> vc(100, 9); //宣告一個大小為100，每個值都是9的vector vector<int> vc = {4, 8, 7, 6, 3}; //跟陣列一樣用法 vector< vector<int> > vec; //vector二維陣列 vector<int> vc[1000] ; // 第二維大小100的二維陣列 ``` ---- - empty() - 判斷是否為空 - size() - 取得vector大小 - front() - 取得第一個元素(=vc[0]) - back() - 取得最後面的元素(=vc[vc.size()-1]) - reserve( value ) - 重新弄vector的空間 ```cpp= vector<int> vec; vec.empty(); vec.size(); vec.front(); vec.back(); vec.reserve(10000) ``` ---- - push_back - 在最上面插入值 - pop_back - 把最上面的值丟掉 - clear() - 淨空整個vector ```cpp= vec.push_back(); vec.pop_back(); vec.claer(); ``` ---- 這些功能就可以取代stack了呢 還比它更好用 ---- vector的功用除了代替stack還可以幹嘛呢? ---- - 代替stack - 代替陣列 - 存圖 - 離線查詢 - 模擬 ...... 總之很多，看不懂也沒關係 會慢慢學到的 --- ## 雙向隊列(deque) ---- deque是個跟stack很像的東西 不過它除了可以從上面放上面拿之外 他也可以從下面放下面拿 ---- 就像這樣，不破壞隊伍的情況，可以從隊伍的尾端或是隊伍的前端進出  ---- 也就是說它會是一個兩邊都可以進出的結構 事實上，它也是一種動態陣列 所以我們可以把它當成是雙向的vector ---- 那他有甚麼用法呢? ---- 宣告基本上跟vector一樣 不過它有自己的標頭 ```cpp= #include<deque> ``` ---- 最基本的函式: empty() - 判斷是否為空。 size() - 取得deque大小。 front() - 取得最前面的元素。 back() - 取得最後面的元素。 deque[value] - 取那個位置的值 ( 不建議使用 ```cpp= deque<int> deq; deq.empty(); deq.size(); deq.front(); deq.back(); cout<<deq[13]; //( 不建議使用 ``` ---- 再來是雙向進出的部分 push_back(DT value) - 放入一個元素至最後面(數字大)。 push_front(DT value) - 放入一個元素至最前面(0的位置)。 pop_back() - 把最後面的元素移除(數字大)。 pop_front() - 把最前面的元素移除(0的位置)。 ```cpp= deq.push_back(123); deq.pop_back(); deq.push_front(123); deq.pop_front(); deq.clear(); ``` ---- 那它的原理呢? ---- 有請在vector出現過的圖  ---- 會發現它就是比stack多了在底部的指針 指針的運作原理都一樣，就可以知道它怎麼操作了 ---- 寫成陣列的實作長這樣: ```cpp= int head = 100, tail = 100; int deq[1000]; tail++; deq[tail] = a; // push_back(a) tail --; // pop_back()操作 head--; st[head] = a; // push_front(a)操作 head ++;// pop_front()操作 cout << q[head] << "\n"; // front()操作 cout << q[tail] << "\n"; // back()操作 if(tail <= head); // empty() int size = tail - head; // size() ``` ---- 練習題: <!--http://mdcpp.mingdao.edu.tw/problem/T063--> --- ## 佇列(queue) ---- 基本上queue就是殘廢版的deque 像是滴定管一樣 從哪裡進去就從另一邊出來  ---- 是不是聽不懂這個比喻 我很抱歉，聯想力不足 ---- 所以給你們看這張圖  ---- 也就是說，它是個先進後出的結構 (FIFO, first in first out) ---- 再來講一下用法 ---- 宣告: ```cpp= #include<queue> queue<int> que; ``` 基本上跟前面一樣 ---- 基本函式: empty() - 判斷是否為空。 size() - 取得queue大小。 front() - 取得最前面的元素。 back() - 取得最後面的元素。 還是熟悉的樣子 ```cpp= queue<int> que; que.empty(); que.size(); que.front(); que.back(); ``` ---- 進出的函式: - push(DT value) - 放入一個元素至最後面。 - pop() - 把最前面的元素移除。 - clear() - 清掉它 ```cpp= queue<int> que; que.push(123); que.pop(); que.clear(); ``` ---- 至於它的原理 還記得我說它是殘廢的deque嗎? ---- 基本上他就是deque把某些功能封掉 原理基本上是一樣的 ---- 唯一的差別大概是因為它跟deque一樣的原理 所以這個queue在push,pop時 指針都是往同一個方向的 所以看起來會造成空間的浪費 ---- 因此C++的STL容器用了環狀queue的概念 也就是當指針指到某數字，就把它丟回初始位置 變成環形的，減少浪費 ---- 練習題: [智乃還債計畫](http://mdcpp.mingdao.edu.tw/problem/T006) (sliding window) [小組隊列](http://mdcpp.mingdao.edu.tw/problem/B002)