如何使用链表实现丢弃堆栈？

链表实现的丢弃堆栈（Discard Stack）是一种数据结构，它结合了链表的动态性和堆栈的后进先出（LIFO）特性。在这种结构中，当堆栈达到其容量上限时，最早添加的元素会被丢弃，而不是像传统堆栈那样导致溢出。

基础概念

链表是一种线性数据结构，其中每个元素都包含一个数据部分和一个指向下一个元素的指针。丢弃堆栈使用链表来实现，每个节点代表堆栈中的一个元素。

优势

动态大小：链表允许堆栈动态地增长和缩小，不需要预先分配固定大小的内存。
丢弃旧元素：当堆栈满时，可以自动丢弃最早的元素，这在某些实时系统中非常有用，例如日志记录或缓存系统。

类型

单链表丢弃堆栈：每个节点只有一个指向下一个节点的指针。
双链表丢弃堆栈：每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。

应用场景

日志系统：当存储空间有限时，可以丢弃旧的日志条目。
缓存系统：在内存有限的情况下，可以丢弃不常用的缓存数据。
实时数据处理：在处理实时数据流时，可以丢弃旧数据以保持系统响应性。

实现示例（单链表丢弃堆栈）

以下是一个简单的单链表丢弃堆栈的实现示例，使用Python语言：

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

class DiscardStack:
    def __init__(self, capacity):
        self.top = None
        self.capacity = capacity
        self.size = 0

    def push(self, value):
        new_node = Node(value)
        if self.size == self.capacity:
            self.top = self.top.next
            self.size -= 1
        else:
            self.size += 1
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.top is None:
            return None
        value = self.top.value
        self.top = self.top.next
        self.size -= 1
        return value

    def peek(self):
        if self.top is None:
            return None
        return self.top.value

# 示例使用
stack = DiscardStack(3)
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 输出 3
stack.push(4)
print(stack.peek())  # 输出 4，因为1被丢弃了