stack, queue, priority_queue

Oak_Cassia·2022년 3월 20일
0

stack

  • deque로 만들어진다.
    (덱은 저장 공간을 재할당할 때 벡터처럼 전체원소를 이동하지 않아도 된다.)
std::stack<int, std::vector<int>> stk1;
std::stack<int, std::list<int>> stk2;
  • empty()
  • size()
  • top() : back()으로 구현
  • push() : 기본 컨테이너의 push_back()으로 구현
  • pop() : pop_back()으로 구현
  • emplace()
  • 한쪽 끝에서만 원소의 추가 및 삭제(LIFO)
  • 모든 연산의 시간 복잡도 : O(1)
  • 스택에서 기본 컨테이너로 함수 호출을 전달하는 과정은 컴파일러에 의해 inline 형식으로 호출돼서 오버헤드가 없다.

queue

  • deque를 기본 컨테이너로 사용한다.
  • push() : push_back()으로 구현
  • pop() : pop_front()으로 구현
  • front()
  • back()
  • stack과 비슷한 함수들 제공
  • 모든 함수의 시간복잡도 : O(1)

priority_queue

  • vector를 기본 컨테이너로 사용
  • heap을 제공
  • 최대/최소 원소에 접근하는 함수 O(1)
  • 원소 삽입 O(log n)
  • 우선순위 큐를 초기화 할 때는 O(n)
  • 비교자는 기본적으로 std::less를 사용하고 최대 원속 맨 위에 나타난다.
  • 원소를 삽입하거나 삭제할 때 다시 힢으로 만드는 알고리즘을 구현해야 한다.
 priority_queue<int,less<int>> pq1;
 priority_queue<int> pq1;
 priority_queue<int,deque<int>,less<int>> pq1;

위의 컨테이너 어댑터들은 반복자가 없다.(필요가 없기 때문에)

profile
rust로 뭐할까

0개의 댓글