Python Queue and Stack
2018-11-09 本文已影响0人
asuka_19d5
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.pngclass 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