Maximum sum of hour glass in matrix

Rather than explaining something more in detail, following sample input, output and explanation would help to understand what do we need to do for this problem.

Input:

int[][] input1 = {
    {1, 2, 3, 4, 5},
    {0, 5, 1, 5, 2},
    {0, 0, 0, 1, 3},
    {4, 1, 1, 0, 1},
    {0, 0, 0, 0, 3},
};

Output:
3   4   5
    5
0   1   3

Max Sum for input1 is: 21

Input:
int[][] input2 = {
    {3, 0, 0, 5},
    {2, 5, 5, 5},
    {0, 0, 0, 1},
    {4, 4, 0, 0},
    {0, 0, 3, 0},
};
Output:
2   5   5
    0
4   4   0

Max Sum for input2 is: 20

Input:
int[][] input3 = {
    {-1, -1, 0, -9, -2, -2},
    {-2, -1, -6, -8, -2, -5},
    {-1, -1, -1, -2, -3, -4},
    {-1, -9, -2, -4, -4, -5},
    {-7, -3, -3, -2, -9, -9},
    {-1, -3, -1, -2, -4, -5}
};

Output:
-1   -1   0
    -1
-1   -1   -1

Max Sum for input3 is: -6

Stack and Queue using Deque

Deque is double ended queue, which like the doubly linked list with having frond/head in the start and last/tail in the end of the list.

Stack using Deque

Input:
push(1)
push(2)
push(3)
push(4)

Output:
4
3->2->1



Queue using Deque

Input:
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)

Output:
1
2->3->4