Deque

Problem

Given a deque (Double Ended Queue) with the following query operations provided as the parameter queries, write a solution function that returns the results of executing these queries.

Query Information

• "addFirst x" (x is a natural number)
  • Inserts the natural number x at the front of the deque.
  • There is no change in the query result.
• "addLast x" (x is a natural number)
  • Inserts the natural number x at the end of the deque.
  • There is no change in the query result.
• "removeFirst"
  • Adds the number at the front of the deque to the query result and removes that number from the deque.
  • If the deque is empty, adds 0 to the query result.
• "removeLast"
  • Adds the number at the end of the deque to the query result and removes that number from the deque.
  • If the deque is empty, adds 0 to the query result.

Concept Explanation

A deque (Double Ended Queue) is a data structure that allows insertion and deletion from both ends, enabling it to function as either a stack or a queue depending on usage. Typically, the following four queries are applied to a deque:

1. addFirst/offerFirst X (Insert): Inserts object X at the front of the deque.
2. addLast/offerLast X (Insert): Inserts object X at the end of the deque.
3. removeFirst/pollFirst (Delete): Extracts and removes the object at the front of the deque.
4. removeLast/pollLast (Delete): Extracts and removes the object at the end of the deque.

Additionally, various other queries can be applied:

1. getFirst/peekFirst: Views the object at the front of the deque without removing it. (Unlike pop, it does not remove the object)
2. getLast/peekLast: Views the object at the end of the deque without removing it.
3. empty: Returns whether the deque is currently empty.

Assume that the following queries are applied to the deque in order:

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

The deque operation process is as follows.

Generally, a deque is implemented as a doubly linked list.

• The addFirst and addLast queries operate at the front and back of the deque, respectively.
• The removeFirst and removeLast queries remove objects from the front and back of the deque, respectively.

A deque implemented as a doubly linked list has a time complexity of $O(1)$ for both insertion and deletion queries.

Constraints

• All elements in queries are either "addFirst x" or "addLast x" where x is a natural number between 0 and 10,000 inclusive, or "removeFirst", "removeLast".
• The length of queries is at most 100,000.
• queries always contain at least one "removeFirst" or "removeLast".

Test Case

Explanation for Test Case 1

• This is identical to the example provided above.

Explanation for Test Case 2

• The queries operate in the following manner.

  Query	Deque	Result
  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]

Explanation for Test Case 3

• The queries operate in the following manner. If the deque is empty, a pop query returns 0 as the result.

  Query	Deque	Result
  removeFirst	[]	[0]
  addFirst 1	[1]	[0]
  removeFirst	[]	[0,1]
  removeLast	[]	[0,1,0]