2. stack.py

LIFO: Last In First Out
The last item added would be the first to be removed

Push: place a new item at the top of the stack
Pop: remove the next item from the top of the stack
  
* Array
a series of objects all of which are the same size and type

* linked list
a linked list consists of nodes where,  each node contains a data field and a reference(link) to the next node in the list.

* vector(dynamic arrays e.g. c++)
vector containers have their elements stored in contiguous storage locations, 
their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.

* implementation
if array is full, push() returns false
if array is empty, pop() returns null

operation   array    linked list
clear       O(1)     O(n)
isFull      O(1)     O(1)
isEmpty     O(1)     O(1)
Push        O(1)     O(1)
Pop         O(1)     O(1)

other.py

42. Trapping Rain Water
https://leetcode.com/problems/trapping-rain-water/
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        ans = 0
        stack = []
        for i, h in enumerate(height):
            temp = bar = 0
            while stack and h >= stack[-1][1]:
                p_i, p_h = stack.pop()
                temp += (i - p_i - 1) * (p_h - bar)
                bar = p_h
                
            if stack:
                temp += (i - stack[-1][0] - 1) * (h - bar)
                
            stack.append((i, h))
            ans += temp

        return ans