[c++] 백준 덱(10866)

문제  https://www.acmicpc.net/problem/10866

간단히 덱의 기본동작을 구현하는 문제이다. 

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

풀이

1. 배열을 이용한 덱 구성. head와 tail이 핵심.

2. STL <deque>를 이용한 구성. 

 

코드

1. 배열을 이용한 구성. head와 tail이 핵심.

 

2. STL <deque>를 이용한 구성.

 

알게 된 점

1. 덱에서 head는 배열의 맨 앞을 가르키고, tail은 배열의 맨 뒤의 다음 인덱스를 가르킨다.

2. 덱에서 특이하게 insert, erase 가능하다.(stack, queue에서는 안됨), stl vector와 비슷함.

    다른 점은, 덱은 메모리상에 연속되어 배치되어 있지만, 벡터는 연속되지 않음.

3. 언제 덱을 사용?, 삽입이 앞쪽과 뒤쪽에 필요한 경우에만 덱을, 나머지는 벡터를 사용하면 된다.

4. 덱에서는 head와 tail만 잘 고려한다면 문제없게 구현 가능하다.

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/7.%20%EB%8D%B1/%EB%8D%B1(10866).cpp