Stack and queue.

Table of content

#Basic concepts

Array

1. Array is a random accres data structure (like a book) in which each element in the array can be accessed in constant time.

Linked list

1. Linked list is a sequential access data structure (like a tape) in which elements are accessible in particular order. One element can be accessed only if all prior elements are visited.

Stack

1. Stack is a limit access data structure that stores and processes the data according to ‘first come last served’ policy.
2. We usually talk about Stack by comparing it to Queue which implements according to ‘first come first served’ policy.
3. Operations with Stack
   1. push(), push an element on top of the stack
   2. pop(), remove an element from top of the stack
   3. top(), get an element from top of the stack
   4. empty(), check if the stack is empty
   5. Stack can be implemented with Array, Linked list, or Queue.

Queue

1. Queue is a limit access data structure that implements a _first come first served_ principle.
2. Operation with Queue
   1. push(), push an element to the tail of the queue
   2. pop(), remove an element from the top of the queue
   3. peek(), get an element from the top of the queue
   4. empty(), check if the queue is empty
3. Queue can be implemented with Array, Linked list, or Stack.

Circular queue

1. Circular queue is a special queue where, e.g.,
   1. the queue is implemented with an array of fixed length
   2. keeping the index of first and last elements
   3. removing an element is by increasing the index of the first element
   4. adding an element is by inserting it into the next position of the last element
   5. wrap around with a modulo operation.

Deque

1. Deque stands for double ends queue where item can be pushed/popped from both end.
2. Python implements deque as in collections 1.

Additional reading materials

1. Lecture note about Stacks and Queues.

#Possible applications

1. Depth first search with Stack
2. Breath first search with Queue
3. Evaluate arithmetic operation with ‘stack’
   1. Change infix expression into postfix expression with Stack
   2. Evaluate the postfix expression with Stack

#Related coding exercises

Here are some interesting/difficult problems from LeetCode related to Stack.

##Binary Tree Preorder Traversal

1. Binary Tree Preorder Traversal problem is defined as given a binary tree, return the preorder traversal of its nodes’ values.
2. Orders of traversal of a binary tree include
   1. The preorder is by the order of root, left child, right child.
   2. The inorder is by the order of left child, root, right child.
   3. The postorder is by the order of left child, right child, root.
3. This can be tackled by recursion or stack.
4. An example Python solution is given as the following which includes both recursion solution and stack solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # @param {TreeNode} root
    # @return {integer[]}
    def preorderTraversal(self, root):
        if root == None: return []
        rtn = []
        #solution_recursion(root,rtn)
        rtn = solution_stack(root)
        return rtn
def solution_recursion(root,rtn):
    '''
    preorder travesal
    07-11: 4 thinking + coding
    '''
    rtn.append(root.val)
    if root.left != None:
        solution(root.left,rtn)
    if root.right != None:
        solution(root.right,rtn)
    pass
def solution_stack(root):
    '''
    preorder traversal by stack
    13-18: 5 thinking + coding
    '''
    stack = [root]
    res = []
    while len(stack)>0:
        # top()
        node = stack[0]
        stack = stack[1:]
        res.append(node.val)
        if node.right != None:
            stack = [node.right] + stack
        if node.left != None:
            stack = [node.left] + stack
    return res

##Binary Tree Inorder Traversal

1. Binary Tree Inorder Traversal is defined as given a binary tree, return the inorder traversal of its nodes’ values.
2. Orders of traversal of a binary tree include
   1. The preorder is by the order of root, left child, right child.
   2. The inorder is by the order of left child, root, right child.
   3. The postorder is by the order of left child, right child, root.
3. An example Python solution is given as the following which includes both recursion solution and stack solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # @param {TreeNode} root
    # @return {integer[]}
    def inorderTraversal(self, root):
        # special case
        if root == None: return []
        # other cases in recursion
        #return solution_recursion(root)
        # other cases in stack
        return solution_stack(root)
def solution_recursion(root):
    if root.left == None and root.right == None: return [root.val]
    if root.left == None and root.right != None: return [root.val] + solution_recursion(root.right)
    if root.left != None and root.right == None: return solution_recursion(root.left) + [root.val]
    if root.left != None and root.right != None: return solution_recursion(root.left) + [root.val] + solution_recursion(root.right)
def solution_stack(root):
    stack = [root]
    res = []
    while len(stack) > 0:
        # top()
        node = stack[0]
        stack = stack[1:]
        if node.left == None: res.append(node.val)
        if node.right!=None: stack = [node.right] + stack
        if node.left != None: stack = [node] + stack
        if node.left!=None: stack = [node.left] + stack
        node.left,node.right = None,None
    return res

##Binary Tree Postorder Traversal

1. Binary Tree Postorder Traversal is defined as given a binary tree, return the postorder traversal of its nodes’ values.
2. Orders of traversal of a binary tree include
   1. The preorder is by the order of root, left child, right child.
   2. The inorder is by the order of left child, root, right child.
   3. The postorder is by the order of left child, right child, root.
3. An example Python solution is given as the following which includes both recursion solution and stack solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # @param {TreeNode} root
    # @return {integer[]}
    def postorderTraversal(self, root):
        if root == None: return []
        #return solution_recursion(root)
        return solution_stack(root)
def solution_recursion(root):
    if root.left == None and root.right == None: return [root.val]
    if root.left == None and root.right != None: return solution_recursion(root.right) + [root.val]
    if root.left != None and root.right == None: return solution_recursion(root.left) + [root.val]
    if root.left!= None and root.right!=None: return solution_recursion(root.left) + solution_recursion(root.right) + [root.val]
def solution_stack(root):
    stack = [root]
    res = []
    while len(stack) > 0:
        node = stack[0]
        stack = stack[1:]
        if node.left == None and node.right == None:
            res.append(node.val)
            continue
        stack = [node] + stack
        if node.right != None: stack = [node.right] + stack
        if node.left != None: stack = [node.left] + stack
        node.left,node.right = None,None
    return res

##Largest Rectangle in Histogram

1. Largest Rectangle in Histogram problem is defined as given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
2. An example Python code is given as the following

class Solution:
    # @param {integer[]} height
    # @return {integer}
    def largestRectangleArea(self, height):
        return solution(height)
def solution(height):
    height = [0] + height + [0]
    stack = [0]
    rtn = 0
    for i,x in enumerate(height):
        while x<height[stack[-1]]:
            # do something
            j = stack.pop()
            h = height[j]
            w = i-stack[-1]-1
            rtn = max(rtn,w*h)
        stack.append(i)
    return rtn
    pass

##Maximal Rectangle

1. Maximal Rectangle problem is defined as given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.
2. This problem can be reduced to Largest Rectangle in Histogram by summing up and analyze rows one by another with a subroutine that compute the largest rectangle in Histogram.
3. An example Python code is given as the following

class Solution:
    # @param {character[][]} matrix
    # @return {integer}
    def maximalRectangle(self, matrix):
        '''
        codeing 29
        '''
        if len(matrix) == 0: return 0
        # initialization
        m,n = len(matrix),len(matrix[0])
        row = [0]*n
        val = 0
        # 
        for i in xrange(m):
            for j in xrange(n):
                if matrix[i][j] == '1':
                    row[j] += 1
                else:
                    row[j] = 0
            curval = process_a_row(row)
            if curval > val:
                val = curval
        return val
def process_a_row(xs):
    xs = [0] + xs + [0]
    stack = [0]
    res = 0
    for i, x in enumerate(xs):
        while x < xs[stack[-1]]:
            y = xs[stack.pop()]
            res = max(res, (i-1-stack[-1])*y)
        stack.append(i)
    return res

##Trapping Rain Water

1. Trapping Rain Water is defined as 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.
2. The idea is quite similar to Largest Rectangle in Histogram.
3. An example Python solution is given as the following:

class Solution:
    # @param {integer[]} height
    # @return {integer}
    def trap(self, height):
        return solution(height)
def solution(height):
    '''
    time complexity is O(2n) in which
    1. I have to go through all elements in the array in O(n)
    2. I have to compute the volumn for all elements in the array in O(n) 
    '''
    if len(height) <=2: return 0
    vol = 0
    stack = []
    for i in xrange(len(height)):
        print '-->',stack
        if len(stack) == 0:
            stack.append(i)
        else:
            if height[stack[0]]>=height[i]:
                stack = [i] + stack
                continue
            else:
                # height[stack[0]]<height[i]
                while height[stack[0]]<height[i]:
                    #top()
                    pos = stack[0]
                    stack = stack[1:]
                    if len(stack) == 0:
                        break
                if len(stack) == 0:
                    for j in xrange(pos+1,i):
                        vol = vol + height[pos]-height[j]
                stack = [i] + stack
    # pop all
    print ':',stack,vol
    while len(stack) > 1:
        pos = stack[0]
        stack = stack[1:]
        print stack[0]+1,pos
        for j in xrange(stack[0]+1,pos):
            if height[pos] > height[j]:
                vol = vol + height[pos]-height[j]
    return vol
    pass

##Binary Search Tree Iterator

1. Binary Search Tree Iterator problem is defined as implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
2. The idea is to use Stack to realize inorder traversal of a binary search tree (BST). The traversal will output the ordered numbers.
3. In particular, the stack will only keep the left child and the root of the tree. Therefore the space complexity is O(h) where h is the height of the tree.
4. The right child will be generated during the search when the size of the stack is 0.
5. An example Python code is given as the following

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class BSTIterator:
    '''
    00-23
    '''
    # @param root, a binary search tree's root node
    def __init__(self, root):
        if root == None:
            self.stack = []
        else:
            self.stack = [root]
            while self.stack[0].left != None:
                self.stack = [self.stack[0].left] + self.stack
                self.stack[1].left = None
    # @return a boolean, whether we have a next smallest number
    def hasNext(self):
        return bool(len(self.stack))
    # @return an integer, the next smallest number
    def next(self):
        if self.stack[0].left == None and self.stack[0].right == None:
            node = self.stack[0]
            self.stack = self.stack[1:]
            return node.val
        if self.stack[0].left == None and self.stack[0].right != None:
            node = self.stack[0]
            self.stack = [node.right]+self.stack[1:]
            return node.val
        if self.stack[0].left!=None:
            while self.stack[0].left != None:
                self.stack = [self.stack[0].left] + self.stack
                self.stack[1].left = None
            node = self.stack[0]
            if node.right == None:
                self.stack = self.stack[1:]
                return node.val
            else:
                self.stack = [node.right] + self.stack[1:]
                return node.val
# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())

##Basic Calculator

1. Basic Calculator problem is to implement a basic calculator to evaluate a simple expression string.
2. The idea is to transform the original string into postfix expression using stack, then evaluate the postfix expression using stack.
3. An example Python code using stack is given as the following

class Solution:
    # @param {string} s
    # @return {integer}
    def calculate(self, s):
        '''
        12-52: 40
        '''
        return solution(s)
import re
def solution(s):
    newslist = postorder(s)
    return processPostOrder(newslist)
    pass
def postorder(s):
    s = re.sub(' ','',s)
    slist = re.sub(r'([\+|\-\(\)])',r' \1 ',s).split(' ')
    #
    newslist = []
    stack = []
    for item in slist:
        if item == '': continue
        if item not in ['+','-','(',')']:
            newslist.append(item)
            if len(stack) > 0 and stack[0] in ['+','-']:
                newslist.append(stack[0])
                stack = stack[1:]
        elif item in [')']:
            while len(stack) >0 and stack[0] == '(':
                stack = stack[1:]
            if len(stack) >0:
                newslist.append(stack[0])
                stack = stack[1:]
        elif item in ['(']:
            stack = [item] + stack
        elif item in ['+','-']:
            stack = [item] + stack
    return newslist
def processPostOrder(s):
    stack = []
    for item in s:
        if item not in ['+','-']:stack = [eval(item)] + stack
        elif item=='+': stack = [stack[1] + stack[0]] + stack[2:]
        elif item=='-': stack = [stack[1] - stack[0]] + stack[2:]    
    return stack[0]