Java Deque example

Sometimes, it is good to return to basics and review how java util call work, and some basic algorithms, so that we don’t make stupid mistakes when trying to resolve Leetcode question.

Java Deque is an interface that implements LIFO and FIFO data structure by being able to quickly add and remove elements from both ends (first and last elements).

The main method we are going to use are these add and remove for both ends:

void addFirst(e);
E removeFirst();
void addLast(e);
E removeLast();

A concrete example where it is useful if for some Tree traversals. Here is the code. Enjoy!

class Test {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        
        TreeNode(int val) {
            this.val = val;
        }
    }
    
    public void testDeque() {
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(3);
        TreeNode rightLeft = new TreeNode(4);
        TreeNode rightRight = new TreeNode(5);
        root.left = left;
        left.left = new TreeNode(6);
        root.right = right;
        right.left = rightLeft;
        right.right = rightRight;
        
        Deque<TreeNode> q = new ArrayDeque<>();
        q.addLast(root);
        
        // bfs
        System.out.println("bfs");
        while (!q.isEmpty()) {
            TreeNode n = q.removeFirst();
            // n cannot be null
            System.out.println(n.val);
            if…