acwing

826. 單鏈表

#include <iostream>using namespace std;const int N = 100010;int idx, e[N], ne[N], head;void init()
{head = -1;idx = 0;
}void insert_head(int x)
{e[idx] = x;ne[idx] = head;head = idx ++ ;
}void delete_k_pos(int x, int k)
{e[idx] = x;ne[idx] = ne[k];ne[k] = idx ++ ;
}void delete_k(int k)
{ne[k] = ne[ne[k]];
}int main()
{int n;cin >> n;init();ios::sync_with_stdio(false);cin.tie(0);char op;int x, k;while (n -- ){cin >> op;if (op == 'H'){cin >> x;insert_head(x);}else if (op == 'D'){cin >> k;if (!k) head = ne[head];else{delete_k(k - 1);}}else{cin >> k >> x;delete_k_pos(x, k - 1);}}for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';cout << endl;return 0;
}

827. 雙鏈表

#include <iostream>
#include <string>using namespace std;const int N = 100010;int idx, e[N], l[N], r[N];void init()
{r[0] = 1;l[1] = 0;idx = 2;
}// 在節點a的右邊插入一個數x
void insert_a_right(int a, int x)
{e[idx] = x;r[idx] = r[a];l[idx] = a;l[r[a]] = idx;r[a] = idx ++ ;
}// 刪除節點a
void delet_k(int a)
{l[r[a]] = l[a];r[l[a]] = r[a];
}int main()
{int n;cin >> n;init();int x, k;string op;while (n -- ){cin >> op;if (op == "L"){cin >> x;insert_a_right(0, x);}else if (op == "R"){cin >> x;insert_a_right(l[1], x);}else if (op == "D"){cin >> k;delet_k(k + 1);}else if (op == "IL"){cin >> k >> x;insert_a_right(l[k + 1], x);}else{cin >> k >> x;insert_a_right(k + 1, x);}}for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';cout << endl;return 0;
}

1. 之所以在 “D”, “IL”, “IR” 要用 k+1 的原因是 雙鏈表的起始點是2. 所以，每個插入位置k的真實位置應該為 k-1+2 = k+1 (在單鏈表中為 k-1)。
2. 0, 1 節點的作用是邊界。0為左邊界，1為右邊界。他倆在這里有點類似保留字的作用。正因如此，我們的idx也是從2開始
3. 最后遍歷輸出結果的 for (int i = rn[0]; i != 1; i = rn[i])。從 rn[0] 開始是因為 0 為左邊界，而終止條件 i==1是因為1為右邊界（如果碰到，說明已經遍歷完畢）

828. 模擬棧

#include <iostream>using namespace std;const int N = 100010;int top = -1;int stk[N];int main()
{int n;cin >> n;string op;while (n -- ){int x;cin >> op;if (op == "push"){cin >> x;stk[++ top] = x;}else if (op == "query"){cout << stk[top] << endl;}else if (op == "pop"){top -- ;}else if (op == "empty"){if (top == -1){cout << "YES"<< endl;}else {cout << "NO" << endl;}}}
}