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