---
title: 基礎資結 # 簡報的名稱
tags: 7th 教學 # 簡報的標籤
---

# 基礎資料結構
#### Author: PixelCat

## 概要

各種基礎資料結構的介紹，包括：

1. 隊列 queue
2. 堆疊 stack
3. 雙端隊列 deque
4. 鏈結串列 linked list

他們都已經內建成[STL](https://hackmd.io/@PixelCat/rJB-6hVau#/)了，所以這裡不會講實作方式。

## 資料結構？

在真的進入資結前，所以什麼是資料結構？

資料結構，就是用精妙、~~邪門、毒瘤~~的方式儲存資料，讓我們可以：

- 更快的插入資料
- 更快的刪除資料
- 更快的修改資料
- 更快的查詢資料、計算答案

很多演算法(圖論、動態規劃...etc.)都需要對應的資料結構才能迅速完成，假如你沒有這些工具，看到題目就算有正確的做法也實做不出來，強大的資料結構可以做為好用的工具幫你對付題目。

這篇講到的資料結構都是最簡單直覺的資結，因為STL都內建好了，熟悉這些資結有效的幫助你實做你的演算法。

就醬，我把這段寫得好無聊。

## 隊列 queue

身為台灣人怎麼能沒排過隊？一個人加入隊伍，從後面進去，從前面出來。
隊列也一樣，元素從後面進去，從前面出來，先進先出（First In First Out, FIFO）。
可以從中間插入元素嗎？當然不行，怎麼可以插隊。
可以從中間刪除元素嗎？也不行，第一個人排這麼久，看後面的人先排到隊，情何以堪。
你說兩個ue連在一起不會唸？~~有邊讀邊沒邊念中間~~，Q的音唸長一點就行了，/kjuː/。


[STL](https://hackmd.io/@PixelCat/rJB-6hVau#/7)幫你內建好了。

## 堆疊 stack

想像學期結束了，你從學校帶回將近一百本教科書，全部疊在地上高到可以當椅子坐。又有新的書了你把它疊在上面，要拿書的時候從最上面開始拿下來。

<image src="https://i.imgur.com/E6SiHdI.jpg" height=300px></image>

堆疊也是一樣，元素從上（後）面進去，從上（後）面出來，先進後出（First In Last Out, FILO）。
可以從中間插入刪除元素嗎？不行，要先把疊在上面重死人的書移開。


[STL](https://hackmd.io/@PixelCat/rJB-6hVau#/8)幫你內建好了。

## 雙端隊列 deque

我想不到比喻了。
既然叫雙端隊列，表示隊列可以做的事情，雙端隊列在兩端都可以做，所以可以從最前面插入刪除，也可以從最後面插入刪除。
從中間插入刪除呢？殘念，還是不行。
另外，_deque_ 念法跟deck相同，也就是應該要念 /dek/ ，全名是 _double-ended queue_，不要學一堆人念底Q /ˌdiːˈkjuː/。


[STL](https://hackmd.io/@PixelCat/rJB-6hVau#/5)幫你內建好了。
為什麼不叫雙端堆疊？我怎麼知道，可能是因為不知道要怎麼念desta吧。

## 鏈結串列

因為超級少用，所以抱著欣賞科普知識的吃瓜心態看過去就行了。

鏈結串列顧名思義，每份資料串在一起，形成一條鏈，每個人指向他的下一個人，這樣叫做**單向鏈結串列**。


或者是指前指後，變成**雙向鏈結串列**


鏈結串列最強大之處在於可以隨便插入刪除，要在哪就在哪。具體來說，你只需要知道要在哪裡做事，把前後的箭頭重新連一連就結束了，常數時間可以完成。

單向鏈結串列插入例：
單向鏈結串列刪除例：

雙向鏈結串列的插入刪除也是類似的做法，只是兩邊的箭頭都要做一樣的事情，~~因為太麻煩所以~~我就不畫了。假如你想自己實做的話，除了容易少連到什麼之外，還要特別注意首尾的箭頭可能會指向虛無，不小心就會戳到空指標噴<font color="#FC6">RE</font>。一個解決的方法是製造兩個額外的節點當頭尾，這樣所有資料在操作的時候，所有指針都會是有意義的，不需要特別判斷是不是頭尾。

然而，鏈結串列鮮少實際被使用，因為他最大的缺點是不能隨機存取內部元素。也就是說，你可以迅速地在串列上往前往後移動，但是一次就只能移動一格，要往裡面偷看的時候只能一步一步往裡面走，太慢。

鏈結串列雖然算在基礎資結，也有內建在[STL](https://hackmd.io/@PixelCat/rJB-6hVau#/6)裡面，實際上我完全沒有用過。

## 以上

上面這些基礎資料結構都是最基本的工具，這些工具STL裡都已經準備好了，只要多用幾次自然就會記住。不過反過來說，假如都不去用他是很難學起來的，所以大家還是有空多多拿著你的新工具去到處扁題目吧。