Stack and queue.

- Table of content
- Definition for a binary tree node.
- class TreeNode:
- def
**init**(self, x): - self.val = x
- self.left = None
- self.right = None

#Basic concepts

`Array`

`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`

`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`

`Stack`

is a*limit access*data structure that stores and processes the data according to ‘*first come last served*’ policy.- We usually talk about
`Stack`

by comparing it to`Queue`

which implements according to ‘*first come first served*’ policy. - Operations with
`Stack`

`push()`

, push an element on top of the stack`pop()`

, remove an element from top of the stack`top()`

, get an element from top of the stack`empty()`

, check if the stack is empty`Stack`

can be implemented with`Array`

,`Linked list`

, or`Queue`

.

`Queue`

`Queue`

is a*limit access*data structure that implements a`_first come first served_`

principle.- Operation with
`Queue`

`push()`

, push an element to the tail of the queue`pop()`

, remove an element from the top of the queue`peek()`

, get an element from the top of the queue`empty()`

, check if the queue is empty

`Queue`

can be implemented with`Array`

,`Linked list`

, or`Stack`

.

`Circular queue`

`Circular queue`

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

`Deque`

`Deque`

stands for*double ends queue*where item can be pushed/popped from both end.- Python implements
`deque`

as in`collections`

#Possible applications

- Depth first search with
`Stack`

- Breath first search with
`Queue`

- Evaluate arithmetic operation with ‘stack’
- Change infix expression into postfix expression with
`Stack`

- Evaluate the postfix expression with
`Stack`

- Change infix expression into postfix expression with

#Related coding exercises

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

.

##Binary Tree Preorder Traversal

- Binary Tree Preorder Traversal problem is defined as given a binary tree, return the preorder traversal of its nodes’ values.
- Orders of traversal of a binary tree include
- The
*preorder*is by the order of*root*,*left child*,*right child*. - The
*inorder*is by the order of*left child*,*root*,*right child*. - The
*postorder*is by the order of*left child*,*right child*,*root*.

- The
- This can be tackled by recursion or stack.
- 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

- Binary Tree Inorder Traversal is defined as given a binary tree, return the inorder traversal of its nodes’ values.
- Orders of traversal of a binary tree include
- The
*preorder*is by the order of*root*,*left child*,*right child*. - The
*inorder*is by the order of*left child*,*root*,*right child*. - The
*postorder*is by the order of*left child*,*right child*,*root*.

- The
- 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

- Binary Tree Postorder Traversal is defined as given a binary tree, return the postorder traversal of its nodes’ values.
- Orders of traversal of a binary tree include
- The
*preorder*is by the order of*root*,*left child*,*right child*. - The
*inorder*is by the order of*left child*,*root*,*right child*. - The
*postorder*is by the order of*left child*,*right child*,*root*.

- The
- An example Python solution is given as the following which includes both recursion solution and stack solution
```python# Definition for a binary tree node.
# 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

- 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.
- 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

- 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.
- 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.
- 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

- 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.
- The idea is quite similar to Largest Rectangle in Histogram.
- An example Python solution is given as the following:
```python
class Solution:
# @param {integer[]} height
# @return {integer}
def trap(self, height):
return solution(height)
def solution(height):
‘’’
time complexity is O(2n) in which
- I have to go through all elements in the array in O(n)
- 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

- 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.
- The idea is to use
`Stack`

to realize*inorder*traversal of a*binary search tree (BST)*. The traversal will output the ordered numbers. - 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. - The
*right child*will be generated during the search when the size of the stack is 0. - 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

- Basic Calculator problem is to implement a basic calculator to evaluate a simple expression string.
- The idea is to transform the original string into
`postfix`

expression using`stack`

, then evaluate the`postfix`

expression using`stack`

. - 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]`