C - Doubly Linked List

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/3/ALDS1_3_C

問題文

以下のクエリを処理する双方向連結リストを実装してね。

• insert x : 連結リストの先頭に $x$ を挿入する
• delete x : 連結リストから $x$ を削除する
• deleteFirst : 連結リストの先頭を削除する
• deleteLast : 連結リストの末尾を削除する

制約

• 命令数は 2,000,000 以下
• delete x は 20 回以下
• $0 \le x \le 10^9$
• リストの要素数は $10^6$ 以下
• delete, deleteFirst, deleteLast のとき、要素は存在する

サンプル

I/O 1

7
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5

6 1 2

考察

双方向連結リスト...は作らず deque で代用。。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_3_C/judge/6746044/C++17

int main() {
  deque<int> dq;
  int n;
  cin >> n;
  while (n--) {
    string s;
    cin >> s;
    if (s == "insert") {
      int x;
      cin >> x;
      dq.push_front(x);
    }
    else if (s == "delete") {
      int x;
      cin >> x;
      rep(i, dq.size()) {
        if (dq[i] == x) {
          dq.erase(dq.begin() + i);
          break;
        }
      }
    }
    else if (s == "deleteFirst") {
      dq.pop_front();
    }
    else {
      dq.pop_back();
    }
    Debug(dq);
  }
  rep(i, dq.size()) {
    cout << dq[i] << (i == dq.size() - 1 ? "\n" : " ");
  }
  return 0;
}