美文网首页
Python Queue and Stack

Python Queue and Stack

作者: asuka_19d5 | 来源:发表于2018-11-09 08:17 被阅读0次
    Python Queue and Stack
    Queque
    • FIFO: first-in first-out the oldest one is the first one to be taken out. two ends, put into one end, take out from another
    • enqueue: put one element into our queue
    • dequeue: take one element out from our queue
    • why we choose queue: real world services require fairness; essential perce in asynchronous computation to keep the same speed of the producer and consumer
    Interface
    class Queue(object):
      def __init__(self):
        self._items = [] #python we use _ to denominate private members, but it is not compulsory
      def __len__(self):
        return len(self._items)
      def enqueue(self, item):
        self._item.append(item)
      def dequeue(self):
        if self.empty():
          return None
        item = self._items[0]
        del self._items[0]
        return item
      def empty(self): #return True if our queue is empty. False otherwise
        return len(self._items) == 0
      def front(self): #returns the oldest element without removing it
        if self.empty():
          return None
        return self._items[0]
    
    • readability, maintainability
    • O(n) for dequeue; O(1) for all the rest
    class ListNode(object):
      def __init__(self, value = None):
        self.next = None
        self.value = value
    
    class Queue(object):
      def __init__(self):
        self._size = 0
        self._head, self_tail = None, None
      def _len_(self):
        return self._size
      def empty(self):
        return self._size == 0
      def enqueue(self, value):
        if not self.empty():
          self._tail.next = ListNode(value)
          self._tail = self._tail.next
        else:
          self._head = ListNode(value)
          self._tail = self._head
        self._size += 1
      def dequeue(self):
        if self.empty():
          return None
        value = self._head.value
        self._head = self._head.next
        if not self._head:
          self._tail = None
        self._size -= 1
        return value
      def front(self):
        if self.empty():
          return None
        return self._head.value
    
    • 也有用双下划线表示private self.__value 这样系统不能直接print
    • if O(1) to find the minimum number: effective query operation means that we need to do indexing and prepare all the answers in advance
    • Solution:
    #deque means double-ended queue, it is an object
    from collections import deque
    class Queue(object):
      def __init__(self):
        self.__deque = deque()
        self.__mins = deque()
      def __len__(self):
        return len(self.__deque)
      def empty(self):
        return len(self.__deque) == 0
      def enqueue(self):
        self.__deque.append(value)
        while self.__mins and self.mins[-1] > value: #如果数组非空且最后一个元素大于当前value
          self.__mins.pop()
        self.__mins.append(value)
      def deque(self):
        value = self.__deque.popleft()
        #list del: O(n) 
        #deque,list pop: O(1)
        if value == self.__mins[0]:
          self.__mins.popleft()
        return value
      def front(self):
        return self.__deque[0]
      def min(self):
        return self.__mins[0]
    #O(1) for enqueqe and dequeue
    
    • recommended: using deque to form queue, list to form stack
    Stack
    • a pile of dishes: first-in-last-out
    • glossary:push and pop
    class Stack(object):
      def __init__(self):
        self.__items = []
      def __len__(self):
        return len(self.__items)
      def empty(self):
        return len(self.__items) == 0
      def push(self, item):
        self.__items.append(item)
      def pop(self):
        if self.empty():
          return None
        return self.__items.pop()
      def top(self):
        if self.empty():
          return None
        return self.__items[-1] 
    
    • porblem 1: push 0-9 in order on to a stack, which ones are impossible:
      • 4,3,2,1,0,9,8,7,6,5 ok
      • 4,6,8,7,6,3,2,9,0,1 no 0,1
      • 2,5,6,7,4,8,9,3,1,0 ok
      • 4,3,1,0,5,6,7,8,9 ok
      • 0,4,6,5,3,8,1,7,2,9 no
    • problem 2: check brackets to find if they match, "{]" "[[})" are invalid
    def is_valid(brackets):
      left_bracket = []
      matching_bracket = {'(' : ')', '{' : '}', '[' : ']'} #dictionary
      for b in brackets:
        if b in matching_bracket: #item in dictionary: look for the key
          left_bracket.append(b)
        elif not left_bracket or matching_bracket[left_bracket[-1]]:
    #dictionary[key] = value
          return False
        else:
          left_bracket.pop()
      return not left_bracket #true only if empty
    
    • problem 3: Assuming we have the following definition for a concept called arithmetic expression:
      An arithmetic expression is either a number, or a left parentheis followed by an arithmetic expression followed by an operatot followed by another arithmetic expression followed by a right parentheis.
      The arithmetic expression itself will be represented as a list of strings that only contains the following terms: '(', ')', '+', '-', '', '/', non-negetive integers.
      input: ['(', '1', '+', '(', '5', '
      ', '4', ')', ')']
      output: 21
    import operator
    def arithmetic_expression_evaluation(terms):
      operands = [] #操作数
      operators = []
      ops = {'+' : operator.add, '-' : operator.sub, '*' : operator. mul, '/' : operator.truediv}
      for term in terms:
        if terms == '(':
          continue
        elif term == ')':
          right, left = operands.pop(), operands.pop()
          operands.append(ops[operators.pop()](left, right))
    #operator.add(number1, number2)
        elif term in ops:
          operators.append(term)
        else:
          operands.append(int(term))
      return operands[0]
    
    Homework

    queue:leetcode 353 641 622
    stack 150 155 224 225 232

    Q: How to implement a queue using two stacks
    image.png
    class Queue:
      def __init__(self):
        self.s1 = []
        self.s2 = []
        self.head = None
    
    def enqueue(self.x):
      if len(self.s1) == 0:
        self.head = x
      self.s1.append(x)
    
    def deque(self):
       if len(self.s2) == 0:
        while self.s1:
          self.s2.append(self.s1.pop())
      return self.s2.pop()
    
    def is_empty(self):
      return not self.s1 and not self.s2
    
    def peek(self):
      if self.s2:
        return self.s2[len(s2) - 1]
      return self.head
    
    def size(self):
      return len(self.s1) + len(self.s2)
    
    • enqueue time: O(1)
    • dequeue time: worst case: O(n) amortized: O(1) (same as using deque)
    Q: implement a stack with MAX API

    Soln1: brute-force: max() iterate each element in the stack to find the maximum
    Soln2: trade space for time 把每一个stack成员变成tuple, (value, max)

    class Stack:
      def __init__(self):
        self.stack = []
    
      def is_empty(self):
        return len(self.stack) == 0
    
      def max(self):
        if not self.is_empty():
          return self.stack[len(self.stack) - 1][1]
        raise Exception('max(): empty stack')
    
      def push(self, x)
        tmp = x
        if not self.is_empty():
          tmp = max(tmp, self.max())
        self.stack.append((x, tmp))
    
      def pop(self):
        if self.is_empty():
          raise Exception('pop(): empty stack')
        elem = self.stack.pop()
        return elem[0]
    
    • time: O(1) for each one
    • space: O(n) for each one
    Q: non-recursion on tree tranversal: stack
    def preorder_tranversal(root):
      output = []
      if not root:
        return output
      stack = [(root, 1)]
      while stack:
        node, count = stack.pop()
        if count == 1:
          output.append(node.val)
          stack.append((node, count + 1))
          if node.left:
            stack.append((node.left, 1))
        if count == 2:
          if node.right:
            stack.append((node.right, 1))
      return output
    

    相关文章

      网友评论

          本文标题:Python Queue and Stack

          本文链接:https://www.haomeiwen.com/subject/uxkmxqtx.html