如果你正在悉尼大学USYD攻读计算机科学或相关专业或者你是一名对算法和数据结构感到既熟悉又陌生的开发者那么这门COMP2123: Data Structures and Algorithms课程的第一周公开课很可能就是你一直在寻找的那个“重启键”。很多同学对数据结构和算法的认知停留在“面试八股文”或“LeetCode刷题”的层面。这导致了一个普遍现象能写出快速排序的代码却说不清为什么在数据近乎有序时它的性能会急剧退化知道哈希表的时间复杂度是O(1)但在设计一个缓存系统时却对如何选择哈希函数、如何处理冲突感到茫然。这门课的价值恰恰在于它试图弥合“知道”与“理解”之间的鸿沟从计算机科学的底层逻辑出发重新构建你对程序效率的认知体系。本文将以COMP2123课程第一周公开课的核心内容为骨架结合当前工业界和学术界的热点如Redis数据结构、图算法在SLAM中的应用、机器学习中的优化算法等为你呈现一份不止于课堂笔记的深度解读与实践指南。你将不仅了解“栈和队列是什么”更能理解它们如何支撑浏览器的前进后退、如何管理函数调用你不仅能复现二叉搜索树更能洞察为何Redis选择跳表来实现有序集合。我们目标是让你在学完本文后能带着一套更系统、更本质的思维模型去应对实际的工程问题与算法挑战。1. 为什么COMP2123的第一课远比你想象的重要数据结构与算法常常被比作程序员的“内功”。但内功的修炼如果起点错了后面很容易事倍功半。第一周课程通常不会涉及复杂的红黑树或动态规划它往往从最基础的算法分析Algorithm Analysis和抽象数据类型Abstract Data Types, ADTs讲起。这部分内容看似理论化却是整个课程大厦的基石。核心价值在于建立“成本意识”。在资源无限的理想世界里我们不需要算法分析。但现实是CPU时间、内存空间、网络带宽都是有限的。算法分析教我们如何量化一个解决方案的“成本”。当你面对一个数据处理问题脑海中能本能地估算不同方法的时间时间复杂度和空间空间复杂度开销你就已经超越了大多数凭感觉写代码的开发者。连接理论与实践的桥梁抽象数据类型ADT。ADT定义了数据对象及其操作如栈的push/pop而不关心具体实现是用数组还是链表。这完美对应了软件工程中的“接口与实现分离”原则。理解ADT你就能看懂Java的List接口为什么有ArrayList和LinkedList两种实现也能理解为什么在设计系统API时首先要定义清晰的数据操作契约。第一周的内容正是在为你装备这两种最关键的武器评估工具算法分析和设计语言ADT。跳过这一周直接去啃排序和二叉树就像没学加减法就去学微积分虽然可能靠记忆公式做出一些题但无法真正理解其所以然。2. 核心概念精讲从复杂度分析到抽象数据类型2.1 算法复杂度分析超越O(n²)的直观理解时间复杂度的大O表示法Big O notation是入门第一关但很多人只记住了“O(1) O(log n) O(n) O(n log n) O(n²)”却不理解其内涵。大O的本质是描述增长趋势。它关注当输入规模n趋向于无穷大时算法运行时间的上界最坏情况。公式O(g(n))意味着存在常数c和n0使得当n n0时运行时间T(n) ≤ c * g(n)。为什么是上界因为工程上我们需要保证最坏情况下的性能可接受。例如一个实时交易系统必须能处理峰值流量。如何分析一段代码的复杂度记住几个关键法则顺序执行复杂度相加取最高阶项。O(n) O(n²)仍然是O(n²)。循环嵌套复杂度相乘。一个O(n)的外层循环套一个O(log n)的内层操作整体是O(n log n)。对数复杂度通常出现在“每次将问题规模减半”的情况下如二分查找。一个常被忽略的要点常数因子c。大O忽略了常数但在实际开发中常数因子至关重要。一个时间复杂度为O(n)但常数项巨大的算法在小数据量时可能远慢于一个O(n log n)但常数项小的算法。这就是为什么在数据量不大时插入排序有时比快速排序更快。2.2 抽象数据类型ADT接口与实现的哲学ADT是一种数学模型它只定义了一组数据对象和一组对这些数据对象的操作并规定了这些操作的行为语义但隐藏了数据的具体表示和操作的实现细节。为什么ADT如此重要封装与信息隐藏使用者只需关心“做什么”不用关心“怎么做”。这降低了模块间的耦合度。提供多种实现同一个ADT可以有多种实现适用于不同场景。例如StackADT可以用数组实现访问快大小固定也可以用链表实现动态扩容但访问稍慢。构成更复杂ADT的基础队列可以用两个栈来实现图可以用邻接矩阵或邻接表来实现。ADT是构建复杂系统的乐高积木。第一周常见的ADT示例栈StackLIFO后进先出。操作push,pop,peek/top,isEmpty。应用场景函数调用栈、浏览器历史记录前进后退、表达式求值、括号匹配。队列QueueFIFO先进先出。操作enqueue,dequeue,front,isEmpty。应用场景打印任务队列、消息队列如RabbitMQ、Kafka、BFS广度优先搜索算法。双端队列Deque两端都可以进行插入和删除。它融合了栈和队列的特性。应用场景实现一个高效的滑动窗口最大值算法。理解ADT是理解Java Collections Framework、C STL、Python内置数据类型设计思想的钥匙。3. 环境准备如何高效跟随课程进行实践COMP2123课程可能使用C或Java作为教学语言。为了获得最佳学习效果建议你搭建一个本地开发环境而不仅仅依赖于学校的在线评测系统。3.1 基础开发环境配置以C为例编译器推荐使用GCC(GNU Compiler Collection) 或Clang。Windows安装 MinGW-w64 或使用 WSL2 Windows Subsystem for Linux获得完整的Linux环境。macOS安装Xcode Command Line Tools终端执行xcode-select --install。Linux通常已预装GCC可通过包管理器安装如sudo apt install g。代码编辑器/IDEVisual Studio Code轻量、插件丰富。安装C/C扩展包即可。CLionJetBrains出品专为C/C设计功能强大学生可申请免费许可。终端Vim/Emacs适合喜欢纯键盘操作的高手。版本控制Git。从第一周就开始用Git管理你的代码这是工程师的基本素养。# 初始化一个仓库来存放你的课程练习代码 mkdir comp2123-notes cd comp2123-notes git init echo # COMP2123 Data Structures and Algorithms Notes README.md git add README.md git commit -m Initial commit3.2 构建工具入门对于小型练习直接使用命令行编译即可# 编译单个cpp文件 g -stdc11 -o my_program my_program.cpp # 运行 ./my_program但随着项目文件增多建议学习简单的Makefile或CMake来管理构建过程。这是一个最简单的Makefile示例CXX g CXXFLAGS -stdc11 -Wall -g # -g 用于调试 TARGET my_program SOURCES main.cpp stack.cpp HEADERS stack.h $(TARGET): $(SOURCES) $(HEADERS) $(CXX) $(CXXFLAGS) -o $(TARGET) $(SOURCES) clean: rm -f $(TARGET)使用make命令编译make clean清理。4. 栈Stack的深度剖析从ADT到两种经典实现让我们以栈为例将ADT的概念彻底落地。我们将定义栈的接口并用两种最经典的方式实现它基于数组和基于链表。4.1 栈的ADT定义C接口类首先我们定义一个纯粹的接口描述栈应该做什么。// File: stack_adt.h #ifndef STACK_ADT_H #define STACK_ADT_H template typename T class StackADT { public: virtual ~StackADT() default; // 虚析构函数确保正确释放资源 // 将元素e压入栈顶 virtual void push(const T e) 0; // 弹出栈顶元素并返回它 virtual T pop() 0; // 返回栈顶元素但不弹出 virtual T top() const 0; // 栈是否为空 virtual bool isEmpty() const 0; // 栈中元素数量 virtual int size() const 0; }; #endif // STACK_ADT_H这是一个抽象类包含纯虚函数它规定了栈的操作契约。任何具体的栈实现都必须继承并实现这些方法。4.2 实现一基于动态数组的栈ArrayStack数组实现的优势是内存局部性好访问速度快但需要处理扩容问题。// File: array_stack.h #ifndef ARRAY_STACK_H #define ARRAY_STACK_H #include stack_adt.h #include stdexcept // for std::out_of_range template typename T class ArrayStack : public StackADTT { private: T* data; // 指向堆上数组的指针 int capacity; // 数组总容量 int topIndex; // 栈顶索引指向下一个空闲位置 void resize(int newCapacity) { // 创建一个新的更大或更小的数组 T* newData new T[newCapacity]; // 复制旧数据 for (int i 0; i topIndex; i) { newData[i] data[i]; } // 释放旧数组指向新数组 delete[] data; data newData; capacity newCapacity; } public: // 构造函数初始容量为16 ArrayStack(int initCapacity 16) : capacity(initCapacity), topIndex(0) { data new T[capacity]; } // 析构函数释放动态数组 ~ArrayStack() { delete[] data; } // 拷贝构造函数和赋值运算符需要深拷贝此处省略Rule of Three/Five void push(const T e) override { // 如果栈满了扩容为原来的两倍摊销时间复杂度O(1)的关键 if (topIndex capacity) { resize(2 * capacity); } data[topIndex] e; // 在topIndex位置放入元素然后索引1 } T pop() override { if (isEmpty()) { throw std::out_of_range(Pop from empty stack); } // 如果元素数量过少例如少于容量的1/4可以缩容以节省空间 // if (topIndex 0 topIndex capacity / 4) { // resize(capacity / 2); // } return data[--topIndex]; // 先索引-1再返回该位置元素 } T top() const override { if (isEmpty()) { throw std::out_of_range(Top on empty stack); } return data[topIndex - 1]; // 栈顶元素在topIndex-1的位置 } bool isEmpty() const override { return topIndex 0; } int size() const override { return topIndex; } // 辅助方法获取当前容量用于观察扩容行为 int getCapacity() const { return capacity; } }; #endif // ARRAY_STACK_H关键点分析动态扩容push操作中当数组满时调用resize将容量翻倍。虽然单次扩容是O(n)操作但经过摊销分析Amortized Analysis每次push的摊销时间复杂度仍是O(1)。这是向量Vector和动态数组的经典策略。缩容策略注释中展示了缩容策略当元素数量降至容量的1/4时缩容一半。这可以避免在频繁push和pop后数组占用大量闲置空间。但需注意**震荡thrashing**问题在容量边界反复push和pop会导致频繁的扩容缩容。生产环境中缩容策略需要更谨慎。异常安全在pop和top中检查栈空并抛出标准异常。4.3 实现二基于单链表的栈LinkedStack链表实现的优势是动态增长无需预先分配固定大小每个操作都是严格O(1)但每个元素需要额外的指针空间且内存访问不连续。// File: linked_stack.h #ifndef LINKED_STACK_H #define LINKED_STACK_H #include stack_adt.h #include stdexcept template typename T class LinkedStack : public StackADTT { private: // 链表节点定义 struct Node { T data; Node* next; Node(const T d, Node* n nullptr) : data(d), next(n) {} }; Node* head; // 栈顶指针指向链表头部 int count; // 元素个数 public: LinkedStack() : head(nullptr), count(0) {} ~LinkedStack() { // 析构时释放所有节点 while (!isEmpty()) { pop(); } } void push(const T e) override { // 创建新节点其next指向原栈顶然后更新head指向新节点 head new Node(e, head); count; } T pop() override { if (isEmpty()) { throw std::out_of_range(Pop from empty stack); } Node* toDelete head; T retValue toDelete-data; head head-next; // 更新栈顶指针 delete toDelete; // 释放原栈顶节点 --count; return retValue; } T top() const override { if (isEmpty()) { throw std::out_of_range(Top on empty stack); } return head-data; } bool isEmpty() const override { return head nullptr; // 或者 count 0 } int size() const override { return count; } }; #endif // LINKED_STACK_H关键点分析头插法链表实现的栈通常将表头作为栈顶。push操作即在链表头部插入新节点pop操作即删除链表头节点。这两个操作都只涉及常数次指针修改是严格的O(1)操作。内存管理每个元素都是独立分配的Node对象析构函数必须遍历链表释放所有节点防止内存泄漏。空间开销每个元素除了存储数据T还需要一个next指针在64位系统上是8字节。如果存储的是小对象如int指针开销占比会很大。4.4 两种实现的对比与选型特性基于动态数组的栈 (ArrayStack)基于链表的栈 (LinkedStack)push/pop 平均时间复杂度O(1) (摊销)O(1)空间占用预分配连续内存可能有闲置空间每个元素额外指针开销无闲置内存局部性优秀数据连续缓存友好较差节点分散缓存不友好扩容开销需要复制数据偶有性能峰值无每次分配一个节点适用场景元素数量可预估或波动不大对性能要求高元素数量波动极大无法预估上限或元素很大复制成本高C STL对应std::stack默认基于std::deque但也可用std::vector可用std::list作为底层容器工程建议在大多数情况下基于动态数组或std::vector的实现是默认选择因为其出色的缓存性能往往能带来更大的实际速度提升。只有在极端情况下如元素非常大或需要绝对稳定的O(1)操作且不关心缓存才会选择链表实现。5. 实战演练利用栈解决经典问题理解了实现我们通过两个经典算法问题来巩固对栈的应用理解。5.1 问题一括号匹配Parentheses Matching给定一个只包含(){}[]的字符串判断括号是否有效匹配。// File: parentheses_checker.cpp #include iostream #include string #include array_stack.h // 使用我们实现的ArrayStack bool isValidParentheses(const std::string s) { ArrayStackchar stack; // 也可以用 std::stackchar stack; for (char c : s) { if (c ( || c [ || c {) { // 左括号入栈 stack.push(c); } else { // 遇到右括号 if (stack.isEmpty()) { return false; // 栈空说明右括号多余 } char topChar stack.pop(); // 检查是否匹配 if ((c ) topChar ! () || (c ] topChar ! [) || (c } topChar ! {)) { return false; // 不匹配 } } } // 最后栈必须为空否则左括号多余 return stack.isEmpty(); } int main() { std::string test1 {[()()]}; std::string test2 ([)]; std::string test3 (((; std::cout test1 is (isValidParentheses(test1) ? valid : invalid) std::endl; std::cout test2 is (isValidParentheses(test2) ? valid : invalid) std::endl; std::cout test3 is (isValidParentheses(test3) ? valid : invalid) std::endl; return 0; }编译与运行g -stdc11 -o parentheses_checker parentheses_checker.cpp ./parentheses_checker预期输出{[()()]} is valid ([)] is invalid (( is invalid算法思想栈的LIFO特性完美匹配了括号的嵌套关系。最后出现的左括号必须优先与最先出现的右括号匹配。5.2 问题二后缀表达式求值Postfix Expression Evaluation后缀表达式逆波兰表示法无需括号依靠操作符的位置即可明确计算顺序。例如中缀表达式(2 3) * 4的后缀形式是2 3 4 *。// File: postfix_evaluator.cpp #include iostream #include string #include sstream #include cctype // for isdigit #include array_stack.h int evaluatePostfix(const std::string expression) { ArrayStackint stack; std::istringstream iss(expression); std::string token; while (iss token) { // 按空格分割表达式 if (isdigit(token[0]) || (token[0] - token.size() 1)) { // 如果是数字包括负数转换为整数并入栈 stack.push(std::stoi(token)); } else { // 如果是操作符弹出两个操作数进行计算 if (stack.size() 2) { throw std::invalid_argument(Invalid postfix expression); } int right stack.pop(); // 注意顺序先弹出的是右操作数 int left stack.pop(); switch (token[0]) { case : stack.push(left right); break; case -: stack.push(left - right); break; case *: stack.push(left * right); break; case /: if (right 0) throw std::runtime_error(Division by zero); stack.push(left / right); break; default: throw std::invalid_argument(Unsupported operator: token); } } } if (stack.size() ! 1) { throw std::invalid_argument(Invalid postfix expression); } return stack.pop(); } int main() { std::string expr1 2 3 4 *; // (23)*4 20 std::string expr2 5 1 2 4 * 3 -; // 5 ((12)*4) - 3 14 try { std::cout expr1 evaluatePostfix(expr1) std::endl; std::cout expr2 evaluatePostfix(expr2) std::endl; } catch (const std::exception e) { std::cerr Error: e.what() std::endl; } return 0; }算法思想遍历后缀表达式遇到数字就压栈遇到操作符就弹出栈顶两个数字进行计算并将结果压回栈中。栈最后剩下的一个数字就是表达式的结果。这个过程清晰地展示了栈如何用于保存中间状态。6. 运行、调试与复杂度验证编写完代码后运行和调试是必不可少的环节。对于数据结构实现除了功能测试我们还应验证其时间复杂度是否符合预期。6.1 功能测试为ArrayStack编写一个简单的测试程序// File: test_stack.cpp #include iostream #include array_stack.h #include linked_stack.h template typename StackType void testStackBasic(StackType stack, const std::string name) { std::cout \n Testing name std::endl; std::cout Is empty? (stack.isEmpty() ? Yes : No) std::endl; stack.push(10); stack.push(20); stack.push(30); std::cout After pushes (10,20,30): Top is stack.top() , Size is stack.size() std::endl; std::cout Pop: stack.pop() std::endl; std::cout Now Top is stack.top() , Size is stack.size() std::endl; while (!stack.isEmpty()) { std::cout Popping: stack.pop() std::endl; } std::cout Is empty now? (stack.isEmpty() ? Yes : No) std::endl; } int main() { ArrayStackint arrayStack; LinkedStackint linkedStack; testStackBasic(arrayStack, ArrayStack); testStackBasic(linkedStack, LinkedStack); // 测试ArrayStack的扩容 ArrayStackint dynStack(2); // 初始容量很小 std::cout \n Testing ArrayStack Dynamic Resizing std::endl; std::cout Initial capacity: dynStack.getCapacity() std::endl; for (int i 0; i 10; i) { dynStack.push(i); std::cout Pushed i , size dynStack.size() , capacity dynStack.getCapacity() std::endl; } return 0; }运行此测试你可以直观看到两种栈的行为一致以及ArrayStack的动态扩容过程。6.2 性能分析与复杂度验证我们可以写一个简单的性能测试来感受一下O(1)操作和O(n)操作的区别以及不同实现的差异。// File: benchmark_stack.cpp #include iostream #include chrono #include array_stack.h #include linked_stack.h const int NUM_OPERATIONS 1000000; // 操作一百万次 template typename StackType void benchmarkPushPop(const std::string name) { StackType stack; auto start std::chrono::high_resolution_clock::now(); // 连续push for (int i 0; i NUM_OPERATIONS; i) { stack.push(i); } // 连续pop for (int i 0; i NUM_OPERATIONS; i) { stack.pop(); } auto end std::chrono::high_resolution_clock::now(); auto duration std::chrono::duration_caststd::chrono::milliseconds(end - start); std::cout name push pop NUM_OPERATIONS times took: duration.count() ms std::endl; } int main() { benchmarkPushPopArrayStackint(ArrayStack); benchmarkPushPopLinkedStackint(LinkedStack); return 0; }注意这个简单测试受很多因素影响编译器优化、内存分配器、缓存等。通常ArrayStack会因为更好的缓存局部性而更快。但这验证了两种实现的push/pop操作都是摊销常数时间因为操作次数与耗时基本呈线性关系。7. 常见问题、陷阱与排查思路在实现和使用栈时新手常会遇到以下问题问题现象可能原因排查方式解决方案程序崩溃Segmentation Fault1. 栈空时执行pop()或top()。2. 数组实现中访问了data[-1]或data[capacity]。3. 链表实现中访问了空指针head-data。1. 在pop和top方法开始处添加空栈检查。2. 使用调试器如gdb查看崩溃时的调用栈和变量值。3. 添加断言assert或打印日志。严格进行边界条件检查。使用try-catch捕获异常。内存泄漏链表实现的栈在析构时没有释放所有节点。使用内存检测工具如ValgrindLinux/macOS或Visual Studio Diagnostic Tools。确保析构函数正确遍历并delete所有节点。遵循RAII原则。性能低下1. 数组栈频繁扩容/缩容震荡。2. 链表栈每个节点单独分配开销大。1. 分析扩容/缩容策略调整阈值如1/4缩容2倍扩容。2. 对于链表考虑使用内存池object pool批量分配节点。根据实际场景选择合适实现。对于数组栈可设置合理的初始容量。多线程下数据竞争多个线程同时push/pop同一个栈对象。代码审查检查是否有共享的可变数据结构。为栈操作加锁如std::mutex或使用线程安全的容器如ConcurrentStack。括号匹配算法对类似“([)]”判断错误算法逻辑错误只检查了数量没检查顺序。用错误的用例单步调试观察栈内元素的变化。确保算法在遇到右括号时是与栈顶的左括号匹配而不是任意一个。8. 从课堂到工业栈在真实系统中的应用理解基础数据结构后看看它们如何应用于复杂的现实系统能极大提升你的认知深度。函数调用栈Call Stack这是栈最经典的应用。每次函数调用系统都会在栈上压入一个栈帧Stack Frame包含参数、局部变量和返回地址。函数返回时栈帧弹出。递归函数深度过深导致的“栈溢出Stack Overflow”错误正是调用栈空间耗尽的体现。浏览器历史记录浏览器的“后退”和“前进”功能可以用两个栈来实现。栈A记录已访问的页面点击新链接时压入栈A点击“后退”时从栈A弹出当前页并压入栈B点击“前进”时从栈B弹出并压回栈A。文本编辑器中的撤销Undo操作许多编辑器使用栈来保存历史状态。每次编辑操作将当前文档状态快照压入“撤销栈”执行撤销时从栈中弹出状态并恢复。Redis中的列表ListRedis的LPUSH/LPOP和RPUSH/RPOP命令使得其List可以轻松作为栈或队列使用。其底层实现是快速链表Quicklist一种结合了压缩列表和双向链表优点的数据结构是对基础数据结构的高效工程实现。深度优先搜索DFS图遍历算法DFS的非递归实现核心就是使用一个栈来保存待访问的节点。这比递归实现更能避免栈溢出问题。9. 总结与学习路线建议第一周的COMP2123课程看似只讲了算法分析和栈、队列等简单ADT实则为你铺设了一条通向高效、可靠软件开发的思维路径。从评估方案成本复杂度分析到定义组件契约ADT再到选择具体实现数组 vs 链表最后应用于实际问题括号匹配、表达式求值这是一个完整的“问题抽象-设计-实现-应用”闭环。给你的后续学习建议动手实现不要满足于看懂代码。亲自动手将课程中的每个数据结构队列、链表、树、图用两种或以上方式实现一遍。遇到Bug并解决它的过程是最好的学习。可视化工具利用 VisuAlgo 等在线工具动态观察数据结构的操作过程建立直观感受。联系实际每学一个数据结构主动思考它在熟悉的开源项目如Redis、Nginx、Linux内核或日常使用的软件如编译器、数据库中可能的应用。复杂度分析成为本能在写任何循环或递归函数前先下意识地分析其时间复杂度。这能帮你提前规避性能瓶颈。向下一周迈进在巩固栈和队列后预习下一周 likely 会讲到的链表Linked List和递归Recursion。递归是理解树和图相关算法的关键而链表是许多高级数据结构的基础。数据结构与算法的学习是一场马拉松。第一周建立正确的思维模式和扎实的基础远比快速刷完所有知识点重要。当你未来面对一个需要设计缓存淘汰策略LRU Cache用到哈希表双向链表或实现一个任务调度器用到优先队列/堆的系统问题时你会感谢自己在这一周所投入的、深入理解每一个细节的时间。
