[대표 유형] 덱

문제 설명

다음 내용의 덱(Deque)에 적용되는 쿼리 정보 매개변수 queries로 주어질 때, 쿼리 수행 결과를 반환하는 solution 함수를 작성하시오.

쿼리 정보

• "addFirst x" (x는 자연수)
  • 자연수 x를 덱의 제일 앞부분에 삽입합니다.
  • 쿼리 수행 결과에는 아무 변화가 없습니다.
• "addLast x" (x는 자연수)
  • 자연수 x를 덱의 제일 뒷부분에 삽입합니다.
  • 쿼리 수행 결과에는 아무 변화가 없습니다.
• "removeFirst"
  • 덱의 제일 앞부분의 수를 쿼리 수행 결과에 추가하고 해당 숫자를 덱에서 삭제합니다.
  • 만일 덱이 비어있다면 쿼리 수행 결과에는 0을 추가합니다.
• "removeLast"
  • 덱의 제일 뒷부분의 수를 쿼리 수행 결과에 추가하고 해당 숫자를 덱에서 삭제합니다.
  • 만일 덱이 비어있다면 쿼리 수행 결과에는 0을 추가합니다.

개념 설명

덱(Deque)은 Double Ended Queue의 줄임말로 큐의 양쪽 모두에서 삽입과 삭제가 가능하게 한 자료구조를 말합니다. 따라서 덱은 사용 방법에 따라 스택 또는 큐로도 사용될 수도 있습니다. 대표적으로 덱에는 다음 네 가지 쿼리가 적용됩니다.

1. addFirst/offerFirst X (삽입) : 덱의 제일 앞부분에 객체 X를 삽입합니다.
2. addLast/offerLast X (삽입) : 덱의 제일 뒷부분에 객체 X를 삽입합니다.
3. removeFirst/pollFirst (삭제) : 덱의 제일 앞부분 객체를 추출하고 삭제합니다.
4. removeLast/pollLast (삭제) : 덱의 제일 뒷부분 객체를 추출하고 삭제합니다.

그 외에도 다음과 같은 다양한 쿼리가 적용되기도 합니다.

1. getFirst/peekFirst : 덱의 제일 앞부분 객체를 확인합니다. (pop과 달리 삭제하지 않습니다)
2. getLast/peekLast : 덱의 제일 뒷부분 객체를 확인합니다.
3. empty : 덱이 비어있는지 여부를 반환합니다.

덱에 다음과 같은 순서대로 쿼리가 적용된다고 가정합니다.

(addLast 4), (addFirst 10), (addLast 7), (removeFirst), (removeLast), (addFirst 5), (removeLast), (addFirst 15), (removeFirst)

이때 덱의 동작 과정은 다음과 같습니다.

일반적으로 덱은 이중 연결 리스트로 구현됩니다.
이렇게 이중 연결 리스트로 구현된 덱은 삽입 및 삭제 쿼리 모두 $O(1)$의 시간복잡도를 갖습니다.

제한 사항

• queries의 모든 원소는 0 이상 10,000 이하의 정수만 주어집니다.
• queries의 길이는 100,000 이하입니다.
• queries에는 0이 항상 1번 이상 포함되어 있습니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 위에서 제시된 예시와 동일합니다.

2번 테스트케이스 설명

• 아래와 같은 과정으로 쿼리가 동작합니다.

  쿼리	덱	결과
  addLast 5	[5]	[]
  addLast 5	[5,5]	[]
  addLast 5	[5,5,5]	[]
  removeFirst	[5,5]	[5]
  addFirst 3	[3,5,5]	[5]
  removeLast	[3,5]	[5,5]
  removeFirst	[5]	[5,5,3]

3번 테스트케이스 설명

• 아래와 같은 과정으로 쿼리가 동작합니다. 덱이 비어있다면, pop 쿼리는 0을 결과로 반환합니다.

  쿼리	덱	결과
  removeFirst	[]	[0]
  addFirst 1	[1]	[0]
  removeFirst	[]	[0,1]
  removeLast	[]	[0,1,0]