Vector:(順序表【數組存儲】)

1.當申請的空間不足的時候，需要再次開辟一塊更大的空間，并把值拷過去。

2.對于尾刪和尾插是比較方便的，只需要改動最后一個元素即可。不會改動原有的空間。適用于多次重復的對尾部插刪。

3.順序存儲，地址是連續的。

4.頭插和頭刪都需要移動一定的大小。時間復雜度為o(N)。而鏈表只需o(1)。

List:(鏈表)

1.需要每次都創建節點。

2.適用于頭刪尾插，但是不適用于多次重復的插刪，因為每次都得創建節點，釋放節點，消耗是比較大的。

3.非順序存儲，地址不連續。

4.由于節點之間地址是不連續的，所以會產生內存碎片問題。

如圖：

List和Vector還有一個重要的點是：

Vector的CPU緩存利用率比鏈表高。

簡單闡述一下：

那么，Vector/List與Stack/Queue有什么聯系呢？

Stack:[棧]（后進先出）

對于棧來說，后進先出，所以是對尾部進行插刪操作，和Vector（尾插尾刪較方便）是類似的。

Queue:[隊列]（先進先出）

對于隊列來說，是先進先出的。所以，對頭部刪除，尾部插入是比較方便的，剛好和鏈表（List）是類似的。

一般情況下，我們會用Vector來模擬實現棧；用List來模擬實現隊列。