---

---

一、栈

类似杯子装水

可以通过顺序表、单链表等线性表的进一步封装实现

eg:

class Stack:
    """
    栈
    1. 用列表实现，选择尾插法 O(1)
    2. 用链表实现，选择头插法 O(1)
    """
    def __init__(self):
        # self.__items = SingleLinkList()
        self.__items = []

    def is_empty(self):
        return self.__items == []

    def size(self):
        return len(self.__items)

    def push(self, item):
        self.__items.append(item)   # O(1),尾插法
        # self.__items.insert(0, item)  # O(n)，头插法

    def pop(self):
        return self.__items.pop()  # O(1)
        # return self.__items.pop(0)   # O(n)

    def peek(self):
        return self.__items[-1]
        # return self.__items[len(self.__items)-1]


if __name__ == '__main__':
    stack = Stack()
    stack.push('hello')
    print(stack._Stack__items)

---

二、队列

一种容器

eg:

class Queue:
    """
    队列
    """
    def __init__(self):
        # self.__items = SingleLinkList()
        self.__items = []

    def is_empty(self):
        return self.__items == []

    def size(self):
        return len(self.__items)

    def enqueue(self, item):
        self.__items.append(item)   # O(1),尾插法
        # self.__items.insert(0, item)  # O(n)，头插法

    def dequeue(self):
        # return self.__items.pop()  # O(1)
        return self.__items.pop(0)   # O(n)


if __name__ == '__main__':
    queue = Queue()
    queue.enqueue('hello')
    print(queue._Queue__items)

1.1 双端队列

eg:

class Deque:
    """
    队列
    """
    def __init__(self):
        # self.__items = SingleLinkList()
        self.__items = []

    def is_empty(self):
        return self.__items == []

    def size(self):
        return len(self.__items)

    def add_front(self, item):
        self.__items.insert(0, item)  # O(n)，头插法

    def add_rear(self, item):
        self.__items.append(item)   # O(1),尾插法

    def remove_front(self):
        return self.__items.pop(0)   # O(n)

    def remove_rear(self):
        return self.__items.pop()  # O(1)


if __name__ == '__main__':
    deque = Deque()
    deque.add_front('hello')
    print(deque._Deque__items)

---

更新中......

---