Queue, Stack & Linked List Note

Queue

• Usages: Breadth-First Search related problems.

典型问题

• Tree printout by level (https://leetcode.com/problems/binary-tree-level-order-traversal/description/)
• 103. Binary Tree Zigzag Level Order Traversal (https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/)
• 232. Implement Queue using Stacks (https://leetcode.com/problems/implement-queue-using-stacks/description/)

• Stack1: is the only stack to store new elements when adding a new element into the queue.
• Stack2: is the only stack to pop old element out of the queue. (When stack2 is empty, we move all data from stack1 to stack2 (if any)) time complexity: Push(): O(1) Pop(): O(n) -> Amortized time complexity O(1)

Stack

• 什么问题要往Stack上考虑？ Answer：从左到右linear scan一个array／string时，如果要不断回头看左边最新的元素时，往往要用到stack。
  1. Histogram中找最大的长方形
  2. reverse polish notation 逆波兰表达式的计算 a*(b + c) -> abc+*
  3. String的repeatedly deduplication. cabba -> caa -> c

infix                      post-fix
a * (b + c)                abc+*
We can use stack to solve the problem.

Shunting Yard algorithm: convert a mid-fix expression to post-fix expression. (Reverse polish notation)
https://en.wikipedia.org/wiki/Shunting-yard_algorithm

Linked List

Key points:

• When you want to de-reference a ListNode, make sure it is not a NULL pointer.
• Never ever lost the control of the head pointer of the LinkedList E1 <- E2 E3->E4-> .... En->NULL Head
• Reverse a linked list template Iterative solution:

public ListNode reverseList(ListNode head) {
	if (head == null || head.next == null) {
		return head;
	}

	ListNode prev = null
	ListNode cur = head;

	while (cur != null) {
		ListNode next = cur.next;
		cur.next = prev;
		prev = cur;
		cur = next;
	}

	return prev;
}

Recursion Solution (Be careful!):

pubilc ListNode reverseList(ListNode head) {
	public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode nextNode = head.next;
        
        ListNode newHead = reverseList(nextNode);
        nextNode.next = head;
        head.next = null;
        return newHead;
    }
}

• Find the middle node of a linked list

public ListNode findMiddle(ListNode head) {
	if (head == null) {
		return head;
	}

	ListNode slow = head;
	ListNode fast = head;

	while (fast.next != null && fast.next.next != null) { // when returns the first median one. If we want to return the second median one, we need fast != null && fast.next != null
		slow = slow.next;
		fast = fast.next.next;
	}

	return slow;
}

Deque

• 239. Sliding Window Maximum (https://leetcode.com/problems/sliding-window-maximum/description/)

Need to Learn

• Histogram 中找最大的长方形
• reverse polish notation
• Shunting Yard algorithm