栈与队列

栈（Stack）

栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

由于使用顺序表的栈易于实现，所以许多地方都默认使用顺序表构建栈，但如果你想用链表实现也不是不可以。以下为一个基本的基于顺序表的栈实现（思考一下，为什么要从顺序表的尾部进行插入和删除操作而不是头部？）

class Stack:
    def __init__(self):
        self.__data = []

    @property
    def length(self):
        return len(self.__data)

    @property
    def top(self):
        """
        仅返回栈顶元素而不出栈, 若栈为空则返回None
        """
        return None if self.length == 0 else self.__data[-1]

    def push(self, data):
        self.__data.append(data)

    def pop(self):
        return self.__data.pop()

队列（Queue）

队列，是先进先出的线性表。队列只允许在尾部进行插入操作，在头部进行删除操作。由于在头部进行删除操作对于顺序表而言，开销较大，所以往往使用链表实现。

class Node:

    def __init__(self, data=None):
        self.data = data
        self.next: Node = None

    def __str__(self):
        return f"[{self.data}]"


class Queue:

    def __init__(self):
        self.__head = Node()
        self.__end = self.__head
        self.length = 0

    @property
    def head(self):
        return None if self.__head.next is None else self.__head.next.data

    def append(self, data):
        self.__end.next = Node(data)
        self.__end = self.__end.next
        self.length += 1

    def poll(self):
        if self.length == 0:
            raise IndexError("Queue is empty")
        data = self.__head.next.data
        self.__head = self.__head.next
        self.length -= 1
        return data