[Data Structure] Deque ์ฌ์ฉ๋ฒ
- c++ STL ์ค ํ๋์ธ Deque์ ๋ํ ์ค๋ช ์ ๋๋ค.
Deque
Deque๋ Double-ended queue์ ์ฝ์๋ก ์์ชฝ ์ด๋์์๋ ์ถ๊ฐ, ์ญ์ ๊ฐ ๊ฐ๋ฅํ ๊ตฌ์กฐ์ธ ํ์ ๋๋ค.
Queue ์์๋ ์์๋ฅผ ์ ๊ทผํ๊ธฐ ์ํด์ front๋ฅผ ํตํด ํ๋์ฉ ๊ฐ์ ธ์๋ค๋ฉด, Deque๋ iterator์ index ์ ๊ทผ์ด ๋ชจ๋ ๊ฐ๋ฅํฉ๋๋ค. push_back, push_front, pop_back, pop_front์ ๊ฐ์ API๋ฅผ ์ฌ์ฉํ์ฌ ์ด๋์์๋ ์ถ๊ฐ๊ฐ ๊ฐ๋ฅํ๊ณ front, back ํจ์๋ฅผ ํตํด ์์๋ฅผ ์ฝ๊ฒ ๊ฐ์ ธ์ฌ ์ ์์ต๋๋ค.
API ํํ๋ index ์ ๊ทผ์ด ๊ฐ๋ฅํ๊ฒ๋ง ๋ณด๋ฉด Queue ๋ณด๋ค๋ Vector์ ํํ์ฒ๋ผ ๋ณด์ด๊ณ , ์คํ๋ ค vector๋ณด๋ค ์์ชฝ ๋ ์์๋ ์ฝ๊ฒ ๊ฐ์ ธ์ฌ ์ ์๊ธฐ ๋๋ฌธ์ ์์ํธํ์ฒ๋ผ ๋ณด์ผ ์ ์์ต๋๋ค.
ํ์ง๋ง, Deque์ Vector์์ ์ฐจ์ด์ ์ ๋ช ํํ๊ฒ ์กด์ฌํ๊ณ ์ทจ์ ๋ฉด์ ์ CS(Computer Science) ์ง๋ฌธ์ผ๋ก ๋์ฌ ์ ์์ด์ ๋ฏธ๋ฆฌ ์์๋๋ฉด ์ ์ฉํฉ๋๋ค.
Deque vs Vector
Deque๋ ์ํ์ค์ ๋ ๋ถ๋ถ ๋ฟ๋ง ์๋๋ผ ์ ๋ถ๋ถ์์๋ ์ถ๊ฐ, ์ญ์ ๊ฐ ํจ์จ์ ์ ๋๋ค.
Vector๋ ๋ฐฐ์ด์ฒ๋ผ ์ฐ์๋ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ์ฐจ์งํ๋ ๋ฐ๋ฉด, Dequeue๋ ๋ชจ๋ ์์๋ค์ด ์ฐ์๋ ๊ณต๊ฐ์ ์ ์ฅ๋์ง ์์ต๋๋ค. ๊ทธ๋งํผ ์ฃผ์๊ณต๊ฐ์ offset์ ๋์ด์ ์ ๊ทผํ ์ ์๊ณ , Cache ์ ์ฉ ์์๋ Cache hit์จ์ด ๋จ์ด์ง ์๋ฐ์ ์์ต๋๋ค.
๋ฐ๋๋ก, vector๋ ์ํ์ค๋ฅผ ์ฆ๊ฐ์ํค๊ธฐ ์ํด์๋ ๋ฐฐ์ด ์์ฒด์ ์ผ๋ก ์ฌํ ๋นํด์ผ ํ๋ ๊ฒฝ์ฐ๊ฐ ์์ง๋ง Deque๋ chunk ๋จ์๋ก ๋ฉ๋ชจ๋ฆฌ๊ฐ ํฉ์ด์ ธ ์๊ธฐ ๋๋ฌธ์ ๊ธธ์ด๊ฐ ๊ธด ์ํ์ค์ผ ๊ฒฝ์ฐ๋ Deque๊ฐ ํจ์จ์ ์ผ ์ ์์ต๋๋ค.
์์ธํ ๋ด์ฉ์ ๋ ํผ๋ฐ์ค๋ฅผ ์ฐธ์กฐํ๋ฉด ์ข์ต๋๋ค.
API
operator= : ๋์ ์ฐ์ฐ์๊ฐ ์ ์๋์ด ์์ด ์๋ก์ด deque ์ธ์คํด์ค์ ๋์ ์ด ๊ฐ๋ฅ
Iterators : begin, end, rbegin, rend์ ๊ฐ์ iterator๋ก ์์๋ค ์ ๊ทผ ๊ฐ๋ฅ
size : deque์ size ๋ฐํํ๋ ํจ์
empty : deque์ ์์ ์ ๋ฌด ํ์ธํ๋ ํจ์
operator[] : ์ฐ์ฐ์๊ฐ ์ ์๋์ด ์์ด์ index๋ก ์ ๊ทผ ๊ฐ๋ฅ
front : deque์ ์ ๋ถ๋ถ์ ์์๋ฅผ ๋ฐํํ๋ ํจ์
back : deque์ ๋ท ๋ถ๋ถ์ ์์๋ฅผ ๋ฐํํ๋ ํจ์
push_back : deque์ ๋ท ๋ถ๋ถ์ ์์ ์ถ๊ฐํ๋ ํจ์
push_front : deque์ ์ ๋ถ๋ถ์ ์์ ์ถ๊ฐํ๋ ํจ์
pop_back : deque์ ๋ท ๋ถ๋ถ ์์ ์ญ์ ํ๋ ํจ์
pop_front : deque์ ์ ๋ถ๋ถ ์์ ์ญ์ ํ๋ ํจ์
insert : ๋งค๊ฐ๋ณ์ iterator์ ์์ ์ถ๊ฐํ๋ ํจ์
erase : ๋งค๊ฐ๋ณ์ iterator์ ์์ ์ญ์ ํ๋ ํจ์
clear : ์ด๊ธฐํํ๋ ํจ์
Example
- ์ถ๊ฐ๋ก ๊ถ๊ธํ ์ ์ด๋ ์์ ํ ๋ถ๋ถ ์์ผ๋ฉด ๋๊ธ๋ก ๋จ๊ฒจ์ฃผ์ธ์.