Python Queue and Stack

2018-11-09  本文已影响0人  asuka_19d5
Python Queue and Stack
Queque
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]
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
#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
Stack
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] 
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
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)
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]
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
上一篇下一篇

猜你喜欢

热点阅读