vector

$vector$，動態數組。
先來看一下它的一些基本操作及其拆后殘渣。
1.a.push_back(x)，將$x$加入動態數組$a$的末尾。
實現：a[++cnt]=x
2.a.size()，查詢動態數組$a$中元素的數量。
實現：cnt
3.a.pop_back()，將動態數組$a$末尾的元素刪除。
實現：cnt--
4.a.erase(a.begin()+x)，刪除動態數組$a$中第$x+1$個元素。
實現：for(int i=x+1;i<=--cnt;i++)a[i]=a[i+1];
5.a.clear()，清空動態數組$a$。
實現：cnt=0
總體實現：

int a[N];
int cnt;
void Push_back(int x){a[++cnt]=x;
}
int Size(){return cnt;
}
void Pop_back(){cnt--;
}
void Erase(int x){for(int i=x+1;i<=--cnt;i++)a[i]=a[i+1];
}
void Clear(){cnt=0;
}

queue

$queue$，隊列。
隊列常用的操作：
1.q.push(x)，向隊列$q$中加入一個元素$x$。
實現：q[++tail]=x
2.q.pop()，彈出隊列$q$的隊首。
實現： head++
3.q.front()，查詢隊列$q$的隊首。
實現：q[head+1]
4.q.back()，查詢隊列$q$的隊尾。
實現：q[tail]
5.q.empty()，判斷隊列$q$是否為空。
實現：(head==tail)
6.q.size()，查詢隊列$q$的元素個數
實現：tail-head
手寫的思想：兩個變量$head$和$tail$，$head$存隊頭前一個元素的下標，$tail$存隊尾的下標。
總體實現：

int q[N];
int head,tail;
void Push(int x){q[++tail]=x;
}
void Pop(){head++;
}
int Front(){return q[head+1];
}
int Back(){return q[tail];
}
bool Empty(){return head==tail;
}
int Size(){return tail-head;
}

deque

$deque$，雙端隊列。
一些基本操作：
1.q.push_back(x)，在雙端隊列$q$的隊尾加入一個元素$x$。
實現：q[++tail]=x
2.q.push_front(x)，在雙端隊列$q$的隊頭加入一個元素$x$。
實現：q[head--]=x
3.q.front()，查詢雙端隊列$q$的隊頭。
實現：q[head+1]
4.q.back()，查詢雙端隊列$q$的隊尾。
實現：q[tail]
5.q.pop_back()，彈出雙端隊列$q$的隊尾。
實現：tail--
6.q.pop_front()，彈出雙端隊列$q$的隊頭。
實現：head++
手寫的思想：兩個變量$head$和$tail$，開雙倍的數組空間$N$，將$head$和$tail$都初始化為$\frac{N}{2}$，$head$存隊頭前一個元素的下標，$tail$存隊尾的下標。
總體實現：

int q[N];
int head=N/2,tail=N/2;
void Push_back(int x){q[++tail]=x;
}
void Push_front(int x){q[head--]=x;
}
int Front(){return q[head+1];
}
int Back(){return q[tail];
}
void Pop_back(){tail--;
}
void Pop_front(){head++;
}

priority_queue

$priorit{y}_{q}ueue$，優先隊列。
要拆優先隊列，首先得明白優先隊列的運行規則。
優先隊列實際上是在維護一個二叉堆。
二叉堆就是一顆完全二叉樹，那么要維護這個二叉堆的什么狀態呢？
答案是維護二叉堆的每一個非葉子節點的值都大于等于（或者小于等于）它的兩個兒子的值。
那么……開拆。（大根堆）
優先隊列的常用操作：
1.q.push(x)，將元素$x$加入優先隊列$q$。
對于一個元素，從左至右依次加入二叉堆，如果父親節點有了這個兒子之后就違法了，那么它就當父親了，父親自然成了兒子。
例如向下面這個二叉堆加入一個元素$7$。

實現：

void Push(int x){q[++cnt]=x;int p=cnt;while(p>1&&q[p/2]<q[p])swap(q[p/2],q[p]),p/=2;//維護單調性
}

2.q.top()，返回優先隊列$q$中的最值
實現：由于時刻都在維護二叉堆的單調性，所以最值就是q[1]
3.q.pop()，彈出優先隊列$q$的隊頭（最值）。
實現：

void Pop(){q[1]=q[cnt--];q[cnt+1]=0;int p=1;while(p<=cnt&&q[p]<max(q[p*2],q[p*2+1])){//維護//判斷左兒子和右兒子哪一個更大if(q[p*2]>q[p*2+1])swap(q[p],q[p*2]),p*=2;else swap(q[p],q[p*2+1]),p=p*2+1;}
}

思想：維護一個二叉堆。
總體實現：

int q[N];
int cnt;
void Push(int x){q[++cnt]=x;int p=cnt;while(p>1&&q[p/2]<q[p])swap(q[p/2],q[p]),p/=2;
}
int Top(){return q[1];
}
void Pop(){q[1]=q[cnt--];q[cnt+1]=0;int p=1;while(p<=cnt&&q[p]<max(q[p*2],q[p*2+1])){if(q[p*2]>q[p*2+1])swap(q[p],q[p*2]),p*=2;else swap(q[p],q[p*2+1]),p=p*2+1;}
}

stack

$stack$，棧。
棧的基本操作：
1.t.push(x)，將元素$x$加入棧$t$中。
實現：t[++cnt]=x
2.t.pop()，彈出棧$t$的棧頂。
實現：cnt--
3.t.top()，查詢棧$t$的棧頂元素。
實現：t[cnt]
4.t.empty，判斷棧$t$是否為空。
實現：(!cnt)
5.t.size()，查詢棧$t$的元素個數。
實現：cnt
總體實現：

int t[N];
int cnt;
void Push(int x){t[++cnt]=x;
}
void Pop(){cnt--;
}
int Top(){return t[cnt];
}
bool Empty(){return !cnt;
}
int Size(){return cnt;
}