C++ STL 프로그래밍(덱)

6. 덱(deque : Double Ended Queue)
    - 서버는 클라가 보낸 패킷을 순서대로 처리하므로 STL중 deque 가 적합하다.
    - 하지만 현업에서는 더 성능이 빠르길 원하므로 직접 자료구조를 만들어 쓴다.
    - 덱 2개를 사용하혀 횟수 제한 없는 undo와 redo 구현 가능


6.1 deque의 자료구조
    - 큐(queue)의 자료구조(선입 선출)와 비슷
    - OS의 작업 스케줄링처럼 입력 순서대로 처리할 때 큐 사용
        

    - 덱은 앞 뒤에서 삽입 삭제 다 되므로 FIFO와 LIFO 둘 다 사용 가능
        


6.2 Deque의 특징
    1) 크기 가변적
    2) 앞 뒤 삽입 삭제 좋다
    3) 중간 데이터 삽입, 삭제 안좋다.(앞 뒤 데이터 이동 시켜야 한다)
    4) 구현이 어렵다(Stack과 Queue가 결합된 구조로 연결 리스트보다 구현 힘들다)
    5) 랜덤 접근 가능하다.


6.3 deque를 사용하는 경우
    1) 앞, 뒤에서 삽입 삭제 한다.(STL 중 성능이 가장 좋다)
    2) 데이터 개수 가변적
    3) 검색을 하지 않는다.(탐색은 느리므로 map, set, hash_map 써라)
    4) 데이터 랜덤 접근 시



6.4 deque vs. vector
    - 벡터는 삽입 삭제를 뒤에서만 해야 성능이 좋다.
    - deque는 삽입 삭제를 뒤에서 해도 벡터보다 성능 좋다.
    - 중간 삽입, 삭제는 벡터보다 성능이 구리다.(앞 뒤를 제외하고는 벡터보다 안좋다)
        


6.5 deque 사용방법
    - deque 헤더 파일 포함 : #include <deque>
    - 선언 : deque<int> 변수이름;
    - 동적할당 : deque<자료형>* 변수이름 = new deque<자료형>;


    6.5.1 deque의 주요 멤버들
        - 벡터에 없는 pop_front, push_front
            

    6.5.2 기본 사용 멤버
        

        insert, erase
            - vector 와 사용법 동일하나, 성능은 벡터보다 안좋다