首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

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

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

基础概念

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

优势

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

类型

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

应用场景

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

实现示例(单链表丢弃堆栈)

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

代码语言:txt
复制
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被丢弃了

参考链接

通过上述代码和解释,你可以理解如何使用链表实现一个丢弃堆栈,并了解其基础概念、优势、类型和应用场景。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

  • ucosii操作系统内核源码学习第一篇

    1. 操作系统默认定义了64个TCB块(为全局变量,编译时候以及分配了,创建一个任务就使用一个,删除一个任务就归还一个)(为什么最大只支持64个任务呢,我们可能想到去更改OS_MAX_TASKS宏的值,但是任务就绪表OSRdyTbl[8]既然已经这样定义了,说明此系统初衷只能最大管理64个任务,而且为了加快查找最高优先级任务定义的OSUnMapTbl[ ]数组(这个数组比较难理解)也是专门为64个任务二设定的,所以要想修改系统支持的最大任务数,就得修改多处,自己慢慢琢磨吧!),每个TCB里面包括了所有的属性,所以会占用大量的单片机ram空间,包括OS_STK *ptos这个指针变量,只是这个任务自己的堆栈指针没有指向任何分配的空间(这个空间由我们创建任务时候才自己定义一个大数组,这个更浪费ram空间)。

    01

    VC 在调用main函数之前的操作

    title: VC 在调用main函数之前的操作 tags: [VC++, 反汇编, C++实现原理] date: 2018-09-16 10:36:23 categories: VC++反汇编分析 keywords: VC++, 反汇编, C++实现原理, main函数调用, VC 运行环境初始化 --- 在C/C++语言中规定,程序是从main函数开始,也就是C/C++语言中以main函数作为程序的入口,但是操作系统是如何加载这个main函数的呢,程序真正的入口是否是main函数呢?本文主要围绕这个主题,通过逆向的方式来探讨这个问题。本文的所有环境都是在xp上的,IDE主要使用IDA 与 VC++ 6.0。为何不选更高版本的编译器,为何不在Windows 7或者更高版本的Windows上实验呢?我觉得主要是VC6更能体现程序的原始行为,想一些更高版本的VS 它可能会做一些优化与检查,从而造成反汇编生成的代码过于复杂不利于学习,当逆向的功力更深之后肯定得去分析新版本VS 生成的代码,至于现在,我的水平不够只能看看VC6 生成的代码 首先通过VC 6编写这么一个简单的程序

    02

    Java大数据面试复习30天冲刺 - 日积月累,每日五题【Day02】——JavaSE

    数组: 数组是最常用的数据结构,数组的特点是长度固定,可以用下标索引,并且所有的元素的类型都是一致的。数组常用的场景有:从数据库里读取雇员的信息存储为EmployeeDetail[ ];把一个字符串转换并存储到一个字节数组中便于操作和处理等等。尽量把数组封装在一个类里,防止数据被错误的操作弄乱。另外,这一点也适合其他的数据结构。 列表: 列表和数组很相似,只不过它的大小可以改变。列表一般都是通过一个固定大小的数组来实现的,并且会在需要的时候自动调整大小。列表里可以包含重复的元素。常用的场景有,添加一行新的项到订单列表里,把所有过期的商品移出商品列表等等。一般会把列表初始化成一个合适的大小,以减少调整大小的次数。 集合: 集合和列表很相似,不过它不能放重复的元素。 堆栈: 堆栈只允许对最后插入的元素进行操作(也就是后进先出,Last In First Out – LIFO)。如果你移除了栈顶的元素,那么你可以操作倒数第二个元素,依次类推。这种后进先出的方式是通过仅有的peek(),push()和pop()这几个方法的强制性限制达到的。 队列: 队列和堆栈有些相似,不同之处在于在队列里第一个插入的元素也是第一个被删除的元素(即是先进先出)。这种先进先出的结构是通过只提供peek(),offer()和poll()这几个方法来访问数据进行限制来达到的。例如,排队等待公交车,银行或者超市里的等待列队等等,都是可以用队列来表示。 链表: 链表是一种由多个节点组成的数据结构,并且每个节点包含有数据以及指向下一个节点的引用,在双向链表里,还会有一个指向前一个节点的引用。例如,可以用单向链表和双向链表来实现堆栈和队列,因为链表的两端都是可以进行插入和删除的动作的。当然,也会有在链表的中间频繁插入和删除节点的场景。Apache的类库里提供了一个TreeList的实现,它是链表的一个很好的替代,因为它只多占用了一点内存,但是性能比链表好很多。也就是说,从这点来看链表其实不是一个很好的选择。

    02

    【编程入门】C语言堆栈入门——堆和栈的区别

    在计算机领域,堆栈是一个不容忽视的概念,我们编写的C语言程序基本上都要用到。但对于很多的初学着来说,堆栈是一个很模糊的概念。堆栈:一种数据结构、一个在程序运行时用于存放的地方,这可能是很多初学者的认识,因为我曾经就是这么想的和汇编语言中的堆栈一词混为一谈。我身边的一些编程的朋友以及在网上看帖遇到的朋友中有好多也说不清堆栈,所以我想有必要给大家分享一下我对堆栈的看法,有说的不对的地方请朋友们不吝赐教,这对于大家学习会有很大帮助。 数据结构的栈和堆 首先在数据结构上要知道堆栈,尽管我们这么称呼它,但实际上堆栈

    06

    一个线程有几个threadlocal_thread线程

    程序是指令的有序集合,其本身没有任何运行的含义,是一个静态的概念。而进程是程序在处理机上的一次执行过程,它是一个动态的概念。进程是由程序、数据和进程控制块三部分组成的。 进程是操作系统资源分配的基本单位,而线程是任务调度和执行的基本单位。 每个进程都有独立的代码和数据空间(程序上下文),程序之间的切换会有较大的开销;线程可以看做轻量级的进程,同一类线程共享代码和数据空间,每个线程都有自己独立的运行栈和程序计数器(PC),线程之间切换的开销小。 系统在运行的时候会为每个进程分配不同的内存空间;而对线程而言,除了CPU外,系统不会为线程分配内存(线程所使用的资源来自其所属进程的资源),线程组之间只能共享资源。 在rtos threadx中,只有一个程序,运行时可以看做只有一个进程,这个进程下包含多个线程。

    01
    领券