Deque

Array

Oct 17

Replaces Stack, Queue, and LinkedList

O(1)

	# Stack
	s = deque()
	s.append(1); # 1
	s.append(2); # 1,2
	s.append(3); # 1,2,3
	s.pop(); # 1,2
	s.pop(); # 1

view raw DequeAsStack.py hosted with ❤ by GitHub

	# Queue
	q = deque()
	q.append(1); # 1
	q.append(2); # 1,2
	q.append(3); # 1,2,3
	q.popleft(); # 2,3
	q.popleft(); # 3

view raw DequeAsQueue.py hosted with ❤ by GitHub

	# LinkedList
	ll = deque()
	ll.append(1); # 1
	ll.append(2); # 1,2
	ll.appendleft(0); # 0,1,2
	ll.pop(); # 0,1
	ll.popleft(); # 1

view raw DequeAsLinkedList.py hosted with ❤ by GitHub

Java

	// Stack
	Deque<Integer> s = new ArrayDeque<>();
	s.addLast(1); // 1
	s.addLast(2); // 1,2
	s.addLast(3); // 1,2,3
	s.removeLast(); // 1,2
	s.removeLast(); // 1

view raw DequeAsStack.java hosted with ❤ by GitHub

	// Queue
	Deque<Integer> q = new ArrayDeque<>();
	q.addLast(1); // 1
	q.addLast(2); // 1,2
	q.addLast(3); // 1,2,3
	q.removeFirst(); // 2,3
	q.removeFirst(); // 3

view raw DequeAsQueue.java hosted with ❤ by GitHub

	// LinkedList
	Deque<Integer> ll = new ArrayDeque<>();
	ll.addLast(1); // 1
	ll.addLast(2); // 1,2
	ll.addFirst(0); // 0,1,2
	ll.removeLast(); // 0,1
	ll.removeFirst(); // 1

view raw DequeAsLinkedList.java hosted with ❤ by GitHub

One data structure to rule them all. A Deque (pronounced "Deck") is a double-ended queue that can add or remove elements from both ends in amortized constant time O(1). This allows us to replace Stack, Queue, and LinkedList with just four interfaces:

· addFirst()
· addLast()
· removeFirst()
· removeLast()

LeetCode

103. Binary Tree Zigzag Level Order Traversal

Python | Java

	def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
	if not root: return []
	result = []
	# use deque as a queue
	q = deque([root])

	while q:
	size = len(q)
	# use deque as a linked list
	ll = deque()

	for i in range(size):
	node = q.popleft()
	if len(result) % 2 == 0: ll.append(node.val)
	else: ll.appendleft(node.val)
	if node.left: q.append(node.left)
	if node.right: q.append(node.right)

	result.append(ll)

	return result

view raw ZigzagLevelOrderTraversal.py hosted with ❤ by GitHub

	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
	if (root == null) return new ArrayList<List<Integer>>();
	List<List<Integer>> result = new ArrayList<>();
	// use ArrayDeque as a Queue
	Deque<TreeNode> q = new ArrayDeque<>();
	q.addLast(root);
	while (q.isEmpty() == false) {
	int size = q.size();
	// use ArrayDeque as a Linked List
	Deque<Integer> ll = new ArrayDeque<>();
	for (int i = 0; i < size; i++) {
	TreeNode node = q.removeFirst();
	if (result.size() % 2 == 0) ll.addLast(node.val);
	else ll.addFirst(node.val);
	if (node.left != null) q.addLast(node.left);
	if (node.right != null) q.addLast(node.right);
	}
	result.add(new ArrayList<Integer>(ll));
	}
	return result;
	}