数据结构第三章：堆栈与队列解析

"本资源是关于数据结构课程的课件，重点关注堆栈和队列的概念。课件由西安电子科技大学理学院的hjTang@xidian.edu.cn提供。内容涵盖了函数调用的过程、线性表的操作、以及堆栈和队列这两种特殊线性表的特性。通过实例展示了堆栈在程序执行中的作用，并提到了队列的基本操作。" 在数据结构的学习中，堆栈和队列是非常基础且重要的概念，它们都是线性数据结构的特例，但限制了元素的插入和删除操作。 堆栈（Stack）被称为“后进先出”（Last In First Out，LIFO）的数据结构，它只允许在一端进行插入（称为进栈或压栈）和删除（称为出栈）。堆栈通常有栈顶和栈底两个端点，新的元素总是被添加到栈顶，而删除操作则总是从栈顶开始。堆栈在程序调用、表达式求解、内存管理等方面有着广泛应用。例如，在函数调用时，每次调用新函数都会将返回地址压入堆栈，当函数执行完毕后，返回地址会从堆栈顶部弹出，使得程序能够回到正确的执行位置。 队列（Queue）则遵循“先进先出”（First In First Out，FIFO）的原则。元素的插入发生在队列的一端（称为队尾），而删除发生在另一端（称为队头）。队列在操作系统中用于任务调度、打印队列等场景，例如，当多个进程请求CPU时，操作系统会按照它们到达的顺序来分配执行时间。 在实际应用中，堆栈常用于实现递归计算，如在程序2的ff函数中，通过递归调用来计算斐波那契数列，这里的函数调用链就形成了一个堆栈结构。而队列则常用于模拟等待服务的对象，例如在银行客户等待办理业务的情景中，新的客户不断加入队尾，而柜员优先服务队头的客户。 线性表的操作可以分为改变表的内容和不改变表的内容。改变内容包括插入和删除元素，不改变内容包括查找和获取元素。而堆栈和队列就是对这些操作进行了特定限制的线性表，使得它们在特定场景下表现出更高效和特殊的操作行为。 课件中还提到了堆栈在现实生活中的例子，比如书的堆叠、光盘的存放、甚至汽车零件的组织，都体现了堆栈的特性。这些生动的例子有助于我们更好地理解和应用堆栈这一抽象数据结构。