清华大学数据结构第三章：栈和队列解析

"数据结构课件第三章，清华版，严蔚敏" 在计算机科学中，数据结构是组织、管理和存储数据的重要方式，它对高效算法的设计至关重要。本资源是清华大学出版社出版的严蔚敏教授编著的数据结构教程的第三章，主要讲解了两种基本但非常重要的数据结构——栈和队列。 栈是一种被称为“后进先出”（LIFO，Last In First Out）或“先进后出”（FILO，First In Last Out）的数据结构。栈的定义是仅允许在表的一端进行插入和删除操作，这一端被称为栈顶，另一端称为栈底。栈在没有元素时为空栈。在栈的操作中，新元素总是被压入栈顶，而弹出操作则总是从栈顶开始，因此，最后进入栈的元素会最先被移出。 栈的存储结构通常有两种实现方式：顺序栈和链栈。顺序栈使用一维数组实现，数组中的一个特定位置（初始为0）作为栈顶指针，当栈满（数组满）时会发生上溢，而栈空时如果尝试出栈则会导致下溢。链栈则是通过链表结构实现，每个节点包含数据和指向下一个节点的指针，同样，链栈的栈顶由一个指针来标识。 栈在计算机程序中有多种应用，例如在括号匹配、回文判断、函数调用栈、深度优先搜索（DFS）等方面。在回文判断中，可以将字符串的字符依次压栈，然后与原字符串的字符进行比较，如果栈为空且所有字符都匹配，则为回文。对于多进制转换，如将十进制数转化为八进制，也可以利用栈来实现。 队列是另一种特殊线性表，被称为“先进先出”（FIFO，First In First Out）的数据结构。与栈不同，队列的插入（入队）操作发生在一端（队尾），而删除（出队）操作发生在另一端（队头）。队列常用于模拟现实世界中的排队现象，例如任务调度、打印队列等。 在实际编程中，栈和队列可以用来解决很多问题，比如在表达式求值中，中缀表达式转后缀表达式（也称为逆波兰表示法，RPN）就需要使用栈来处理运算符和操作数。例如，计算2+4-3*6的过程可以通过维护两个栈来实现：一个操作数栈用于存储数字，另一个运算符栈用于临时存储运算符。按照运算符的优先级和结合性，将运算符压入运算符栈，当遇到操作数时将其压入操作数栈。当遇到运算符时，将栈顶的两个操作数弹出并进行相应的运算，结果再压回操作数栈。如此反复，直至表达式解析完毕。 本章详细介绍了栈和队列的概念、特点、存储结构以及各种操作的算法实现，对于学习数据结构和理解计算机内部工作原理具有重要价值。无论是教师教学还是学生自学，这份资料都是一个宝贵的资源。