[일반] deque는 왜 랜덤 액세스가 가능한거야?

[익명(118.235)]

옛날에 수업에서 구현할때는

그냥 linked list에 양방향에서 push pop 다 가능하게 하고 parent*도 저장하는 식으로 만들었었는데

저번에 누가 덱은 랜덤 액세스 가능하다고 해서 찾아보니까

진짜 가능한 것처럼 적혀있던데

[익명(118.235)]

vector 기반 구현인갑지

[익명(118.235)]

vector기반이면 push pop하다가 느려질거 같은데 또 그렇지도 않잖아

[익명(211.210)]

여러 개의 버켓에 데이터를 나눠 저장함. i번째 원소는 i/n번째 버켓의 i%n번 인덱스에 저장된다고 생각하면 돼. 물론 offset 생각해야해서 저기에 추가적인 연산이 들어가

[익명(118.235)]

그럼 입 출력이 일반 queue보다 느린대신 랜덤 엑세스가 가능한거?

[익명(211.210)]

queue는 deque기반이야. 둘이 같은 구조임

[익명(118.235)]

queue나 stack은 랜덤 액세스 지원 안해줘서 다른가 했는데 뭐야 ㅋㅋㅋㅋ

[익명(183.105)]

deque, queue, stack, vector, string은 전부 같은 자료구조라고 생각하는게 편함

[익명(121.188)]

벡터는 맨 앞 삽입이 O(N) 이자너

[pichulia(49.172)]

std::deque가 이렇게 해롭습니다.