CS50x - 第5讲 - 数据结构

数据结构：没有万能的答案，只有合适的选择

CS50x第5周的课程聚焦于计算机科学中最核心的概念之一——数据结构。这同时也是本周C语言课程的收官之作，下周将正式转入Python的学习。贯穿这一阶段的主题，始终是编程世界中无处不在的权衡取舍。

课程以一段巧妙的动画故事开场：一个叫Jack的年轻人因为交友困难找到了学校最受欢迎的Lou，Lou发现Jack的衣柜里衣服堆成一堆，每次穿的都是最上面那件，导致其他衣服从未被穿到。问题的根源在于Jack把衣物当作"栈"来使用——后放进去的反而先拿出来。

Lou给出的解决方案是建立"队列"：每天把穿过的衣服挂在衣柜左侧，第二天从右侧取用。这样一来，每件衣服都能轮到一次，体现了公平性。这个故事的背后，是两个重要抽象数据类型的直观呈现。

队列（Queue）的核心特性是先进先出（FIFO）。就像现实中的排队买票，先到的人先服务，后到的人在队尾等待。在计算机中，队列有两个基本操作：入队（enqueue）和出队（deque），分别对应排到队尾和从队首离开。

栈（Stack）则遵循后进先出（LIFO）原则。正如故事中Jack把衣服一件件堆进箱子，每次取用的都是最后放上去的那件。生活中的例子比比皆是：邮箱里新邮件默认显示在顶部、食堂里叠放的托盘、浏览器的前进后退按钮。栈的两个基本操作是"压栈"（push）和"弹栈"（pop）。

理解概念只是第一步，如何用代码实现它们才是关键。课程展示了一段用C语言实现的队列代码：定义一个最多容纳50人的结构体，包含一个固定大小的数组、当前队列大小和容量。这种实现方式看似简洁，却暴露了一个根本性问题——静态数组的大小在编译时就已确定。

如果来了第51个人怎么办？结构体无法记录。如果把容量改成5000，又可能在人少时造成大量内存浪费。这就是编程语言设计中的经典权衡：静态分配简单高效，但缺乏灵活性；动态分配可以按需伸缩，却需要更复杂的内存管理。

有趣的是，栈的实现几乎可以照搬队列的结构，只需重命名即可。由于栈只从一端操作，实现起来反而更简单——新元素总是添加到数组末尾，删除也始终从末尾进行，第一个元素可以安心待在位置0。

课程反复强调一个关键区分：抽象数据类型（ADT）描述的是"是什么"，而数据结构实现解决的是"怎么做"。队列和栈作为抽象概念，可以借助数组、链表甚至动态内存等多种方式来实现。选择的实现方式会直接影响性能表现，比如在动态增长的队列中，如何高效地扩容和缩容就是一个值得深入研究的问题。

这一周的学习为后续内容奠定了坚实基础。当同学们下周进入Python的学习时，会发现高级语言自动处理了许多内存管理的细节，让人能把精力集中在算法逻辑本身。但正是C语言中那些"麻烦"的手动操作，让我们真正理解了数据结构的本质——每一种设计都是特定场景下的最优解，不存在放之四海而皆准的完美方案。

📺 观看原视频：在 shipin.5l5l.net 观看