数据结构和算法 -- 栈和队列

Stack implementation

实现一个 stack 可以用两种数据结构，array(dynamic or fixed) 或者是 linked list。

dynamic array 的优势是支持 random access，因为可以通过 index 获取数据，然而 stack 主要作用是 pop，所以 dynamic array 的这个优势 gains you little。dynamic array 另一个优势是 resize，这个非常的 time-consuming 因为需要 copy array to a new one。

linked list 会为每一个元素分配内存，这比 dynamic array 的 resize 更费时，因此基于 dynamic array 的 stack 通常要比基于 linked list 的 stack 快一些。然而，基于 linked list 的 stack 更容易实现。

Proper functionality
基本方法：

• push
  allocate new element, checks for failure, sets the data of the new element, places it at the top of the stack, adjust the stack pointer
• pop
  check the stack isn’t empty, fetches data from top element, adjusts the stack pointer, free the element that is no longer on the stack

完整方法：

• createStack
  push a null pointer
• deleteStack
  call pop repeatedly

Error handling

• pop
  如果 stack 为空，返回 null? 问题是需要保证 stack 里没有存 null pointer；返回 special value(or negative value)？问题是需要 assume stack 里没有这些元素。感觉 raise error 比较简单。
• push
  如果传进去的值为 null，raise error

# implement a stack using linkedlist
class Stack(object):

    class Node(object):

        def __init__(self, val=None, next=None):
            self.val = val
            self.next = next

    def __init__(self):
        self.head = None

    '''
    check the stack isn't empty, fetches data from top element, adjusts the stack pointer, free the element that is no longer on the stack
    '''

    def pop(self):
        if not self.head: raise ValueError("Empty stack!")
        val = self.head.val
        self.head = self.head.next
        return val

    '''
    allocate new element, checks for failure, sets the data of the new element, places it at the top of the stack, adjust the stack pointer
    '''

    def push(self, val):
        if not val:
            raise ValueError("Invalid value!")
        node = self.Node(val, self.head)
        self.head = node

'''
push a null pointer
'''

def createStack(stack):
    stack.head = Node()
    return True

'''
call pop repeatedly
'''

def deleteStack(stack):
    while stack.head:
        stack.pop()
    return True

stack=Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print stack.pop()
print stack.pop()
print stack.pop()
print stack.pop()

# implement a stack using fixed-size array
class Stack(object):

    def __init__(self, capacity=None):
        if capacity:
            self.elements = [None] * capacity
        else:
            self.elements = [None] * 10
        # set the top to be -1, indicating the stack is empty
        self.top = -1

    def isEmpty(self):
        return self.top == -1

    def push(self, item):
        if self.top == len(self.elements):
            raise ValueError("Full stack!")
        self.top += 1
        self.elements[self.top] = item

    def pop(self):
        if self.isEmpty():
            raise ValueError("Empty stack!")
        # get the element on the top
        item = self.elements[self.top]
        self.elements[self.top] = None
        # reduce the top variable
        self.top -= 1
        return item

    def peek(self):
        if self.isEmpty():
            raise ValueError("Empty stack!")
        return self.elements[self.top]

Queue implementation

# implement a queue using fixed-size array
class Queue(object):

    def __init__(self, capacity=None):
        if capacity:
            self.elements = [None] * capacity
        else:
            self.elements = [None] * 5
        self.front = 0
        self.back = -1
        self.nItems = 0

    def enqueue(self, item):
        if self.isFull():
            raise ValueError("Queue is full")
        self.back += 1
        index = self.back % len(self.elements)
        self.elements[index] = item
        self.nItems += 1

    def dequeue(self):
        if self.isEmpty():
            raise ValueError("Queue is empty")
        index = self.front % len(self.elements)
        result = self.elements[index]
        self.elements[index] = None
        self.front = index + 1
        self.nItems -= 1
        return result

    def peekFront(self):
        if self.isEmpty():
            raise ValueError("Queue is empty")
        return self.elements[self.front % len(self.elements)]

    def isEmpty(self):
        return self.nItems == 0

    def isFull(self):
        return self.nItems == len(self.elements)


q=Queue()
q.enqueue(4)
q.enqueue(5)
q.enqueue(6)
print q.elements
q.dequeue()
print q.elements
q.dequeue()
print q.elements
q.enqueue(10)
q.enqueue(11)
q.enqueue(12)
print q.elements

Leetcode 实例

232.Implement Queue using Stacks

Problem

Implement the following operations of a queue using stacks.
push(x) – Push element x to the back of queue.
pop() – Removes the element from in front of queue.
peek() – Get the front element.
empty() – Return whether the queue is empty.
Notes:
You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Solution

class Queue(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack1=list()
        self.stack2=list()

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.stack1.append(x)

    def pop(self):
        """
        :rtype: nothing
        """
        self.helper()
        return self.stack2.pop()

    def peek(self):
        """
        :rtype: int
        """
        self.helper()
        '''
        element=self.stack2.pop()
        self.stack2.append(element)
        return element
        '''
        return self.stack2[-1]

    def empty(self):
        """
        :rtype: bool
        """
        if self.stack1 or self.stack2:
            return False
        return True

    def helper(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())

225.Implement Stack using Queues

Problem

Implement the following operations of a stack using queues.
push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
empty() – Return whether the stack is empty.
Notes:
You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.

用两个队列，push: O(n)，pop: O(1)，top: O(1)

Solution

from collections import deque
class Stack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.queue1=deque()
        self.queue2=deque()

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        if not self.queue2:
            self.queue2.append(x)
            while self.queue1:
                self.queue2.append(self.queue1.popleft())
            self.queue1,self.queue2=self.queue2,self.queue1


    def pop(self):
        """
        :rtype: nothing
        """
        self.queue1.popleft()

    def top(self):
        """
        :rtype: int
        """
        return self.queue1[0]


    def empty(self):
        """
        :rtype: bool
        """
        if not self.queue1:
            return True
        return False

155. Min Stack

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
getMin() – Retrieve the minimum element in the stack.
Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Solution

'''
Solution:
    Primitive idea would be to use a global varible to record current minimum value when push, but when pop value, the minimum value may change. One solution is when pop we empty the list and redo the push action for n-1 values but thus it takes O(n) time.

Followup:
    It would be perfect if we can keep track of the minmum value at each 'timestamp'. We can use tuple to record current minimum value for each value when push a new element.
'''
'''
class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack=list()
        self.min=float('inf')

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.stack.append(x)
        self.min=min(self.min,x)


    def pop(self):
        """
        :rtype: void
        """
        if not self.stack:
            return None
        if self.top()==self.min:
            cur=self.stack[::]
            self.stack=[]
            self.min=float('inf')
            for i in range(len(cur)-1):
                self.push(cur[i])
        else:
            del self.stack[-1]

    def top(self):
        """
        :rtype: int
        """
        if not self.stack: return None
        return self.stack[-1]


    def getMin(self):
        """
        :rtype: int
        """
        return self.min
'''



class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack=list()

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if not self.stack:
            self.stack.append((x,x))
            return
        self.stack.append((x,min(x,self.getMin())))

    def pop(self):
        """
        :rtype: void
        """
        if not self.stack:
            return None
        return self.stack.pop()[0]

    def top(self):
        """
        :rtype: int
        """
        if not self.stack: return None
        return self.stack[-1][0]


    def getMin(self):
        """
        :rtype: int
        """
        return self.stack[-1][-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

20.Valid Parentheses

Problem

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

Solution

'''
Solution:
- check when right meet; just need the last unpaired left => first in,last out => stack
- create a dictionary for parenthese pairs, for each element in s, if it exists in dictionary.keys(), then append it into the stack, else, pop from the stack and check if the popped value and current element is a pair. Time complexity: O(n)
- remember to check if stack is empty in every check and also in final check (look back for previous left parentheses)
'''
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return None
        dictionary={'(':')','[':']','{':'}'}
        s=list(s)
        stack=[]
        for i in s:
            if i in dictionary:
                stack.append(i)
            else:
                if not stack or dictionary[stack.pop()]!=i:
                    return False
        return not stack

150. Evaluate Reverse Polish Notation

Problem

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:
[“2”, “1”, “+”, “3”, “*“] -> ((2 + 1) * 3) -> 9
[“4”, “13”, “5”, “/“, “+”] -> (4 + (13 / 5)) -> 6

Solution

'''
Solution:
- each operation requires two operands and one operator, operator always appear after operands, so we search element from left to right, store numbers in the stack till we meet up with an operator, and with the operator, we pop two elements from the stack and caculate the results and push it back to stack, and continue, till the end of tokens, finally return the final value of the stack.

Attention(negative integer division):
- division in python, pls consider when one of the operand is negative, you would get surprising result. eg. -7/2=-4.
    in order to avoid that, use int(float(a)/b) whenever there's a division operation
'''
class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stack=[]
        for t in tokens:
            if t=='+':
                stack.append(stack.pop()+stack.pop())
            elif t=='-':
                a=stack.pop()
                b=stack.pop()
                stack.append(b-a)
            elif t=='*':
                stack.append(stack.pop()*stack.pop())
            elif t=='/':
                a=stack.pop()
                b=stack.pop()
                stack.append(int(float(b)/a))
            else:
                stack.append(int(t))
        return stack.pop()

Followup

'''
Followup:
- infix notation
    ( => operator stack
    number => number stack
    ) => pop and calculate till a '(' is met
    +,- => higher precedence met-> push into the operator stack, lower precedence met-> calculate higher operator in stack first and then push
- test case:
  input: ["(","(","3","+","4",")","*","(","4","+","1",")","-","4","*","2",")","+","1"]
  output: 28
'''
class Solution(object):
    def evalRPN(self,tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        op_stack=[]
        num_stack=[]
        for i in tokens:
            # case '('
            if i=='(':
                op_stack.append(i)
            # case ')'
            elif i==')':
                while op_stack[-1]!='(':
                    num_stack.append(self.cal(op_stack.pop(),num_stack.pop(),num_stack.pop()))
                op_stack.pop()
            # case '+','-','*','/'
            elif i=='+' or i=='-' or i=='*' or i=='/':
                while op_stack and self.isLowerThan(i,op_stack[-1]):
                    num_stack.append(self.cal(op_stack.pop(),num_stack.pop(),num_stack.pop()))
                op_stack.append(i)
            # case number
            else:
                num_stack.append(int(i))
        while op_stack:
            num_stack.append(self.cal(op_stack.pop(),num_stack.pop(),num_stack.pop()))
        return num_stack.pop()


    def cal(self,op,num1,num2):
        if op=='+':
            return num1+num2
        if op=='-':
            return num2-num1
        if op=='*':
            return num1*num2
        if op=='/':
            return int(float(num2)/num1)
        raise ValueError("Not valid operator")

    def isLowerThan(self,op1,op2):
        if (op1=='+' or op1=='-') and (op2=='*' or op2=='/'):
            return True
        return False

71. Simplify Path

Problem

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = “/home/“, => “/home”
path = “/a/./b/../../c/“, => “/c”
click to show corner cases.

Corner Cases:
Did you consider the case where path = “/../“?
In this case, you should return “/“.
Another corner case is the path might contain multiple slashes ‘/‘ together, such as “/home//foo/“.
In this case, you should ignore redundant slashes and return “/home/foo”.

Solution

'''
Solution:
- ignore '.', when met '..', pop from stack if stack is not empty, and finally join the stack

Attention:
- corner case: /../a => /a
- always remember if you wanna pop from a stack check if it is empty first
'''
class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        vals=path.split('/')
        stack=[]
        for v in vals:
            if v=='' or v=='.': continue
            if v=='..':
                if stack: stack.pop()
            else: stack.append(v)
        return '/'+'/'.join(stack)

84. Largest Rectangle in Histogram

Problem

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.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

Solution

'''
Solution:
- primitive idea: find all rectangles and get max one, time complexity O(n^2)

Followup:
- O(n)?
    - avoid repeated work
    - identify a rectangle: identify 2 boundaries
    - if cur>stack.peek() --> offer, else --> continously poll

Corner case: [0]
'''
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        if not heights: return 0
        stack=[]
        max_area=0
        for i in range(len(heights)+1):
            cur=0 if i==len(heights) else heights[i]
            while stack and cur<=heights[stack[-1]]:
                height=heights[stack.pop()]
                leftBound=0 if not stack else stack[-1]+1
                rightBound=i
                cur_area=(rightBound-leftBound)*height
                max_area=max(cur_area,max_area)
            stack.append(i)
        return max_area



    '''
    # primitive, 2 loops
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        if not heights: return 0
        max_area=0
        for i in range(len(heights)):
            max_area=max(heights[i],max_area)
            min_height=heights[i]
            for j in range(i,len(heights)):
                min_height=min(min_height,heights[j])
                max_area=max(min_height*(j-i+1),max_area)
        return max_area
        '''

Python stack & deque

这篇用到的 python 的知识点/需要注意的地方。

use lists as stacks

LIFO
add, use append()
retrieve, use pop()

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

use lists as queues

FIFO，python list 作 queue 并不 efficent，用 collections.deque

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.popleft()                 # The first to arrive now leaves
'Eric'
>>> queue.pop()                 # The second to arrive now leaves
'Graham'
>>> queue                           # Remaining queue in order of arrival
deque(['John', 'Michael', 'Terry'])