第2关：实现一个链接存储的栈

在第2关中，通常会要求你实现一个数据结构，即链接列表（Linked List）版本的栈（Stack）。链接列表作为动态数组的一个变种，非常适合用于实现栈，因为它支持高效的插入和删除操作，尤其是在头部（顶部）。

下面是一个简单的Python实现：

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

class LinkedListBasedStack:
    def __init__(self):
        self.top = None

    # 添加元素到栈顶
    def push(self, item):
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node

    # 删除并返回栈顶元素
    def pop(self):
        if not self.is_empty():
            popped_data = self.top.data
            self.top = self.top.next
            return popped_data
        else:
            raise IndexError("Stack is empty")

    # 检查栈是否为空
    def is_empty(self):
        return self.top is None

    # 返回栈顶元素，但不删除
    def peek(self):
        if not self.is_empty():
            return self.top.data
        else:
            raise IndexError("Stack is empty")

# 使用示例
stack = LinkedListBasedStack()
stack.push(1)
stack.push(2)
print(stack.pop())  # 输出：2

在这个实现中，`push`方法将新元素添加到链表的开头，而`pop`方法则移除并返回当前栈顶的节点。`is_empty`和`peek`方法分别检查栈是否为空以及查看栈顶元素但不删除它。