deque

• STL - Container Classes:
  • Sequence Container
    • Vector
    • List
    • Double-ended Queue(Deque)
  • Container Adaptor
    • Stack
    • Queue
    • Priority Queue
  • Associative Container
    • Set
    • Map

Double-ended Queue(Deque)

• 추천 문제
  • [BOJ] 덱 (소스코드)
  • [BOJ] 카드 놓기 (소스코드)
  • [BOJ] 풍선 터뜨리기 (소스코드)
  • [BOJ] 회전하는 큐 (소스코드) - deque를 이용한 회전하는 큐 구현

---

덱(deque)

• deque (usually pronounced like "deck") is an irregular acronym of double-ended queue.
• Restricted Structure
• push의 시간 복잡도는 O(1)
• pop의 시간 복잡도는 O(1)
• front, back의 시간 복잡도는 O(1)

소스코드

#include <iostream>
#include <deque>

// deque
using std::deque;

int main() {
  std::deque<int> dq;
  dq.push_back(10);   // { 10 }
  dq.push_back(40);   // { 10 40 }
  dq.push_front(50);  // { 50 10 40 }
  std::cout << dq.size() << '\n';   // 3
  std::cout << dq.front() << '\n';  // 50
  std::cout << dq.back() << '\n';   // 40
  if (dq.empty())
    std::cout << "deque is empty!\n";
  else
    std::cout << "Deque is not empty!\n";  // print "Deque is not empty!"

  dq.pop_front();    // { 10 40 }
  dq.push_back(60);  // { 10 40 60 }
  dq.pop_back();     // { 10 40 }
  std::cout << dq.front() << '\n';  // 10
  std::cout << dq.back() << '\n';   // 40
  for (const int& i : dq)
    std::cout << i << ' ';  // 10 40
  std::cout << '\n';

  return 0;
}

---

이전 - Array	목록	다음 - BFS & DFS