C++ 자료구조 3 - 덱(deque)

이거 수업시간에 배웠을 때는 교수님이 데크라고 부르시던데 남들은 다 덱이라고 쓰니까 나도 덱이라고 써야지!!ㅋㅋㅋㅋㅋ

덱(deque)은 double-ended queue의 약자로 양방향 큐이다!!

그러니까 큐에서는 앞에서 pop이 일어나고 뒤에서 push가 일어나는 대기줄이라고 말했었는데 덱은 앞에서도 pop과 push가 가능하고 뒤에서도 pop과 push가 가능하다.

 

덱의 method는

push_front : 덱의 앞에 자료를 넣는 연산

push_back : 덱의 뒤에 자료를 넣는 연산

pop_front : 덱의 앞에서 자료를 빼는 연산

pop_back : 덱의 뒤에서 자료를 빼는 연산

front : 덱의 가장 앞에 있는 자료를 보는 연산

back : 덱의 가장 뒤에 있는 자료를 보는 연산

등이 있다.

큐, 스택과 다르게 앞뒤에서 모두 pop과 push가 일어날 수 있으므로 push와 pop이 두 개씩 있다.

 

그림으로 그려보자!!

먼저 덱에 1 2 3 4 5를 넣었다고 가정한다.

여기서 push_front(0)을 해보자(덱의 앞에 0을 넣는다).

그럼 이렇게 원래 제일 첫 번째에 있었던 1 앞에 0이 들어갈 것이다.

push_back(6)을 해보자(덱의 뒤에 6을 넣는다).

원래 맨 뒤에 있었던 5 뒤에 6이 들어갈 것이다.

pop_front()를 하면 맨 앞의 0이 사라질 것이다.

pop_back()을 하면 맨 뒤의 6이 사라질 것이다.

pop_front()를 다시 해보면 맨 앞의 1이 사라질 것이다.

여기서 empty()를 해보면 덱이 비지 않았으니까 false가 리턴될 것이고 size()는 4이다.