225. Implement Stack using Queues

使用queue来构造stack, 我们就只能使用queue的特性，stack需要实现的功能有push(), pop(), top(), empty(), 注意pop是从栈顶pop, top也是指栈顶元素。
queue的特性是first in first out
这里我们用deque来实现。self.stack = collections.deque()
因为stack是pop出最后一个元素，而deque总是pop出第一个元素，所以在实现pop()时，我们要先把最后一个元素之前的所有元素都pop出来并append到后边去，这样原来的最后一个元素就可以被pop出来了。

for i in range(len(stack) - 1):
      temp = self.stack.popleft()
      self.stack.append(temp)
return self.stack.popleft()

Hey you are implementing a stack thus you don't have stack.pop() yet right? That's the function you are currently implementing ;) You can only do standard queue operations which means pop from the head only (popleft())

232. Implement Queue using Stacks

需要实现的方法有push(), pop(), peek(), empty(), pop和peek都是从fron end开始。因为stack只能从back end操作，所以我们使用两个stack，实现pop()时，我们将Instack中的元素全部pop出来，append到outstack中去，此时outstack中最后一个元素就是我们想要的队列首元素。新加了一个move()方法来实现这个操作。所以执行pop()和peek()时，要先执行move()方法。

• 需要注意的是empty(): 因为我们有两个stack, 所以要判断两个stack都为空时才返回真return len(self.instack) == 0 and len(self.outsatck) == 0

为什么要用两个stack来实现queue?
The application for this implementation is to separate read & write of a queue in multi-processing. One of the stack is for read, and another is for write. They only interfere each other when the former one is full or latter is empty.

When there's only one thread doing the read/write operation to the stack, there will always one stack empty. However, in a multi-thread application, if we have only one queue, for thread-safety, either read or write will lock the whole queue. In the two stack implementation, as long as the second stack is not empty, push operation will not lock the stack for pop.

155. Min Stack

Min stack 需要在constant time内取得stack中的最小值。普通stack的min([])是需要O(n)时间的，是linear time.
做法就是stack中存入数值对[num1, nums2]，nums1是当前append进去的数字，nums2是nums1入栈后当前的最小值。

• push()
  要先获得curmin，即先执行getMin函数。

curmin = self.getMin()
if not curmin or x < curmin:
         curmin = x
self.stack.append([x, curmin])

• top()

if len(self.stack) == 0:
    return None
else:
    return self.stack[-1][0]

208. Implement Trie (Prefix Tree)

设计一个前缀树，实现insert, search, startwith功能。
首先初始化TrieNode类：
self.children = {}, self.is_word = False
self.is_word用来判断单词是否结束

• insert：对单词中的字母一个一个进行插入，插入后及时更新current结点
• search: 针对单词中的每一个字母，在当前结点的孩子中寻找对应字母，如果不存，就返回False，如果存在，就对current结点进行更新。这里需要注意，最后返回的是return current.is_word， 因为就算单词中的所有字母都存在，但在trie中寻找到单词中的最后一个字母时，这个path/word还没有结束，也就是trie中的这个字母不是这条path/word的终点，此时我们也认为要搜索的单词是不存在的。
• startwith：实现的步骤和search完全一样，只是最后返回的是return True，因为这次我们要找的只是一个prefix, 不是一个完整的单词，这个prefix只要存在就可以返回true, 并不需要检查最后一个节点的is_word是否为真。