(2020.04.18)
*注: 除了本文中提到的list表达，还可以用linked list实现stack/queue。

Stack

Stack: Last In First Out (LIFO)
Stack的array-based实现方法:
直接用Python的list实现。注意到stack.push()可用list.append()实现，而stack.pop()可用list.pop()实现。这种一种类的方法实为对另一种类的方法的调用，称为设计模式中的适配器模式 (adapter pattern)。

class Empty(Exception):
    pass

class array_stack:
    def __init__(self):
        self._data = []
    def __len__(self):
        return len(self._data)

    def is_empty(self):
        return len(self._data) == 0

    def push(self, p):
        return self._data.append(p)

    def pop(self):
        if self.is_empty():
            raise Empty('Stack empty')
        return self._data.pop()

    def top(self):
        return self._data[-1]

复杂度分析:
考虑到该方法的base是Python list，所以操作可以参考list对应的操作。
stack.push(p): O(1) amortised
stack.pop(): O(1) amortised
stack.is_empty(): O(1)
stack.top(): O(1)
stack._ _ len _ _(): O(1)
提速方法:
初始化过程中将hidden list从长度0改为长度n (用户定义)，这种方式比从长度0开始的list更高效 (但复杂度保持不变?)。
应用: reverse a sequence反转，matching parentheses and HTML tags检查括号匹配。
括号匹配的算法和实例:
对序列做扫描从左到右，每次遇到左括号(open symbol)，push it into stack。每次遇到右括号(close symbol)，pop a symbol from the stack(非空)，并检测popped symbol和右括号是否是valid pair。如果完成扫描并且均是匹配，则该序列的括号合理匹配。

def is_match(seq):
    lefty, righty = '([{', ')]}'
    s = array_stack()
    for oc in seq:
        if oc in lefty:
            s.push(oc)
        elif oc in righty:
            if s.is_empty(): 
                return False
            if righty.index(oc) != lefty.index(s.pop()):
                return False
    return s.is_empty()

Queue

Queue: First In First Out (FIFO)
操作: queue.enqueue(p)从尾部加入p, queue.dequeue()剔除头部点。
Queue的低效实现方法:

• 直接用list实现，queue.push(a)参考list.append(a)，queue.pop()参考list.pop(0)。.push复杂度O(1) amortised，.pop复杂度是O(n)，其中n表示list长度，因为list.pop(0)在删除了index=0元素后便将从index=1开始到结尾平移到index=0开始。
• 与前一种方法相似，queue.push(a)相同，但queue.pop()的方法不同于list.pop(0)。queue.pop()时queue的头部元素变成None，同时head index加1。这种方法的特点是push次数越多，list长度越长，pop次数越多list头部的None越多。

一种高效的实现方式: using an array Circularly
一个list，有头、尾两个指针，记录头、尾的位置，初始为0、0。每次push操作尾index+1，每次pop操作头index+1，前提是index+1之后的指针值没超过list长度。或者不设置尾指针，而有头指针结合queue length计算尾指针。如果超过list长度，则执行求模module操作，tail = (tail+1) % len(list)，这种操作可以保证在index=9之后+1操作回到index=0的职位，成为一个circule。每次push操作后queue length += 1，每次pop操作后queue length -= 1。

class circular_array_queue:
    DEFAULT_CAPACITY = 20
    def __init__(self):
        self._data = [None] * circular_array_queue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0
    def __len__(self):
        return self._size
    def is_empty(self):
        return self._size == 0
    def first(self):
        if self.is_empty():
            raise Empty('Queue empty')
        return self._data[self._front]
    def dequeue(self):
        if self.is_empty():
            raise Empty('Queue empty')
        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1) % len(self._data) 
        # len(self._data) not exactly circular_array_queue.DEFAULT_CAPACITY, 
        # which depends on whether the queue is resized or not
        self._size -= 1
        return answer
    def enqueue(self, e):
        if self._size == len(self._data):
            self._resize(2*len(self._data))
        tail = (self._front + self._size) % len(self._data)
        self._data[tail] = e
        self._size += 1
    def _resize(self, newlen):
        old = self._data
        self._data = [None] * newlen
        walk = self._front
        for k in range(self._size):
            self._data[k] = old[walk]
            walk = (walk+1) % len(old)
        self._front = 0

复杂度分析:
queue.enqueue(n): O(1) amortised
queue.dequeue(): O(1) amortised
queue.first(): O(1)
queue.is_empty(): O(1)
queue.is_empty(): O(1)
queue.len(): O(1)

reference:

1. M.T. Goodrich and etc., Data Structures and Algorithms.