栈和队列的链表实现

1. 抽象基类

首先为每种数据结构定义一个公共的抽象基类, 并定义判空、判等、加法操作等常用基础接口．

class  AbstractCollection(object):
    def __init__(self, source_collection=None):
        self._size = 0
        if source_collection:
            for x in source_collection:
                self.add(x)

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

    def __len__(self):
        return self._size

    def __str__(self):
        return '[' + ', '.join(map(str, self)) + ']'

    def __add__(self, other):
        if type(self) != type(other):
            raise KeyError('Type Error')

        result = type(self)(self)
        for item in other:
            result.add(item)
        return result

    def __eq__(self, other):
        if self is other:
            return True

        if type(self) != type(other) or len(self) != len(other):
            return False

        other_iter = iter(other)
        for item in self:
            if item != next(other_iter):
                return False

        return True

2. 链式栈

• 维护一个(头插法)链表
• 栈顶操作位于表头
• iter遍历顺序是从表尾到表头, 故可使用递归生成一个依次存储表尾至表头节点数据的列表, 返回其迭代器

class Node(object):
    """singly linked node"""
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class LinkedStack(AbstractCollection):
    def __init__(self, source_collection=None):
        self._items = None
        super().__init__(source_collection)

    # Accessors
    def __iter__(self):
        def visit_nodes(node):
            if node != None:
                visit_nodes(node.next)
                temp_list.append(node.data)

        temp_list = list()
        visit_nodes(self._items)
        return iter(temp_list)

    def peek(self):
        if self.is_empty():
            raise KeyError("The stack is empty.")

        return self._items.data

    # Mutators
    def clear(self):
        self._size = 0
        self._items = None

    def push(self, item):
        self._items = Node(item, self._items)
        self._size += 1

    def add(self, item):
        self.push(item)

    def pop(self):
        if self.is_empty():
            raise KeyError("The stack is empty.")

        pop_item = self._items.data
        self._items = self._items.next
        self._size -= 1
        return pop_item

3. 链式队列

• 维护一个(尾插法)链表
• 队尾插入, 队首删除
• 设置尾指针以实现O(1)时间的插入操作

class LinkedQueue(AbstractCollection):
    def __init__(self, source_collection=None):
        self._head = self._rear = None
        super().__init__(source_collection)

    # Accessors
    def __iter__(self):
        probe = self._head
        while probe != None:
            yield probe.data
            probe = probe.next

    def peek(self):
        if self.is_empty():
            raise KeyError("The queue is empty")

        return self._head.data

    # Mutators
    def clear(self):
        self._size = 0
        self._head = self._rear = None

    def add(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            self._rear.next = node
        self._rear = node
        self._size += 1

    def pop(self):
        if self.is_empty():
            raise KeyError("The queue is empty")

        item = self._head.data
        self._head = self._head.next
        self._size -= 1
        if self.is_empty():
            self._rear = None
        return item