1.3 栈（20题）

<h1>什么是栈？</h1> <p>栈（Stack）是一种抽象数据类型和线性数据结构，它只允许在一端（称为栈顶）进行数据的插入和删除操作。栈遵循后进先出（LIFO, Last In First Out）的原则，即最后插入的元素会是第一个被删除的元素。</p> <h1>栈的特点是什么？</h1> <p>栈的主要特点包括：</p> <ul> <li>后进先出（LIFO）：新添加或待删除的元素都保存在栈的同一端，即栈顶，最后添加进去的元素将会最先被移除。</li> <li>限定性：栈的操作是受限的，只能在栈顶进行插入（push）和删除（pop）操作。</li> <li>动态大小：栈的大小通常是动态的，可以根据需要增长和缩减，但在某些实现中，栈的大小可能是固定的。 <h1>栈的基本操作有哪些？</h1> <p>栈的基本操作主要包括：</p></li> <li>push（入栈）：将元素添加到栈顶。</li> <li>pop（出栈）：移除并返回栈顶的元素。</li> <li>peek（查看栈顶）：返回栈顶的元素但不移除它（有时也称为top操作）。</li> <li>isEmpty（判断栈是否为空）：检查栈是否包含任何元素。</li> <li>size（获取栈的大小）：返回栈中元素的数量。 <h1>栈的两种主要实现方式是什么？</h1> <p>栈的两种主要实现方式是：</p></li> <li>基于数组（Array-based）：使用数组来存储栈中的元素，并维护一个指向栈顶的索引。</li> <li>基于链表（Linked-list-based）：使用链表来存储栈中的元素，每个节点包含数据部分和指向下一个节点的指针，栈顶元素位于链表的头部。 <h1>如何用数组实现栈？</h1> <p>用数组实现栈的基本思路是：</p></li> <li>定义一个数组来存储栈的元素。</li> <li>维护一个整数变量（如top）来指示栈顶元素的位置。初始时，top通常被设置为-1，表示栈为空。</li> <li>当进行push操作时，将新元素添加到数组的top + 1位置，并递增top的值。</li> <li>当进行pop操作时，返回数组的top位置的元素，并递减top的值。</li> <li>peek操作返回数组的top位置的元素而不改变top的值。</li> <li>isEmpty操作检查top是否为-1。</li> <li>size操作返回top + 1的值，表示栈中元素的数量。 <h1>如何用链表实现栈？</h1> <p>用链表实现栈时，我们通常使用单链表。在这种实现中，每个节点包含两部分：数据域（存储栈中的元素）和指针域（指向下一个节点）。栈顶元素位于链表的头部。为了实现栈的操作，我们需要一个指针（通常称为top或head）来跟踪链表的头部节点。当进行栈操作时，我们总是在链表的头部添加或删除节点。</p> <h1>栈的初始化步骤是什么？</h1> <p>栈的初始化步骤通常包括：</p></li> <li>分配一个固定大小的数组来作为栈的存储空间。</li> <li>初始化一个栈顶指针（通常称为top），并将其设置为-1，表示栈为空。这个指针用于指示栈顶元素在数组中的位置。 <h1>如何在栈中进行入栈操作？</h1> <p>在栈中进行入栈操作时，需要：</p></li> <li>首先检查栈是否已满（即栈顶指针是否等于数组的最大索引）。如果栈已满，则无法进行入栈操作。</li> <li>如果栈未满，则将栈顶指针加1，并将新元素存储在栈顶指针所指示的数组位置上。 <h1>如何在栈中进行出栈操作？</h1> <p>在栈中进行出栈操作时，需要：</p></li> <li>首先检查栈是否为空（即栈顶指针是否为-1）。如果栈为空，则无法进行出栈操作。</li> <li>如果栈不为空，则取出栈顶指针所指示的数组位置上的元素，并将其作为出栈操作的结果。</li> <li>将栈顶指针减1，以更新栈顶位置。 <h1>如何判断栈是否为空？</h1> <p>判断栈是否为空非常简单： 只需检查栈顶指针是否为-1。如果栈顶指针为-1，则栈为空；否则，栈不为空。</p> <h1>如何判断栈是否已满？</h1> <p>判断栈是否已满需要： 检查栈顶指针是否等于数组的最大索引（或数组长度减1，因为数组索引通常从0开始）。如果栈顶指针等于数组的最大索引，则栈已满；否则，栈未满。</p> <h1>栈的顶元素是如何获取的？</h1> <p>栈的顶元素可以通过以下方式获取： 检查栈是否为空。如果栈不为空，则栈顶指针所指示的数组位置上的元素即为栈的顶元素。通常，可以通过一个特定的函数（如peek或top）来返回栈顶元素而不改变栈的状态。</p> <h1>栈的遍历方法有哪些？</h1> <p>栈的遍历方法主要有两种：</p></li> <li>非破坏性遍历：通过重复执行出栈操作并访问每个元素，直到栈为空，然后再通过入栈操作将元素恢复到栈中。这种方法会改变栈的状态，但可以在遍历后恢复。</li> <li>使用辅助栈的遍历：创建一个辅助栈，将原栈中的所有元素依次出栈并入辅助栈，然后遍历辅助栈以访问原栈中的元素。这种方法不会改变原栈的状态，但需要额外的空间来存储辅助栈。</li> </ul> <p>在实际应用中，由于栈的后进先出（LIFO）特性，通常不需要对栈进行遍历操作。如果需要遍历栈中的元素，可能需要考虑使用其他数据结构（如队列、链表或数组）来辅助实现。</p> <h1>栈的入栈和出栈操作的时间复杂度是多少？</h1> <p>入栈操作：在栈不满的情况下，入栈操作的时间复杂度是O(1)。因为入栈只是将新元素放到栈顶，并更新栈顶指针，这是一个常数时间的操作。然而，如果栈支持动态扩容，当栈满时需要重新分配内存并搬移数据，此时最坏情况下的时间复杂度会变为O(n)，但均摊时间复杂度仍然是O(1)。 出栈操作：出栈操作的时间复杂度也是O(1)。因为出栈只是移除栈顶元素，并更新栈顶指针，这同样是一个常数时间的操作。</p> <h1>栈的空间复杂度是多少？</h1> <p>栈的空间复杂度是O(n)，其中n是栈的最大容量。这是因为栈需要预先分配一个固定大小的数组来存储元素，这个数组的大小就决定了栈的空间复杂度。在入栈和出栈过程中，除了这个数组外，只需要一两个临时变量来存储栈顶指针或临时元素，所以额外的空间复杂度是O(1)。</p> <h1>栈的应用场景有哪些？</h1> <p>栈的应用场景非常广泛，包括但不限于：</p> <ul> <li><strong>函数调用</strong>：在程序调用函数时，会将当前的状态（如局部变量、返回地址等）压入栈中，当函数执行完毕返回时，再从栈中弹出这些信息，恢复到调用前的状态。</li> <li><strong>表达式求值和编译器</strong>：编译器在解析源代码时会使用栈来处理运算符优先级和括号匹配问题。</li> <li><strong>深度优先搜索（DFS）</strong>：在图或树的遍历算法中，深度优先搜索策略自然地使用了栈。</li> <li><strong>回溯算法</strong>：回溯算法在解决问题的过程中，会尝试各种可能的解决方案，当发现当前路径不可行时，会“回退”到上一步，这个过程可以通过维护一个状态栈来实现。</li> <li><strong>内存管理</strong>：操作系统中的某些内存管理技术，如某些类型的动态内存分配，会使用栈来跟踪已分配和未分配的内存块。</li> </ul> <h1>栈如何实现括号匹配？</h1> <p>栈可以实现括号匹配的检查。具体方法是，从左到右扫描字符串，遇到左括号就压栈，遇到右括号就检查栈顶是否有对应的左括号，有的话就弹出，否则匹配失败。当所有的括号都扫描完成之后，如果栈为空，则说明字符串中的括号匹配；否则，说明有未匹配的左括号。</p> <h1>栈如何实现表达式求值？（自学，上课没讲）</h1> <p>栈可以实现表达式求值。通常使用两个栈，一个用于存储操作数，另一个用于存储操作符。从左到右扫描表达式，遇到操作数就压入操作数栈，遇到操作符则根据操作符的优先级与栈顶操作符进行比较，决定是否弹出栈顶操作符并进行计算，然后将结果压回操作数栈。最终，操作数栈中剩下的唯一一个元素就是表达式的最终结果。</p> <h1>栈如何实现字符串的逆序？</h1> <p>栈可以实现字符串的逆序。具体方法是，将字符串中的每个字符依次入栈，然后依次出栈，并将出栈的字符按顺序连接起来，就得到了逆序后的字符串。</p> <h1>栈如何实现回文字符串的判断？</h1> <p>栈可以实现回文字符串的判断。具体方法是，将待判断的字符串依次入栈，然后从字符串的开头开始，依次将字符出栈，并与字符串中对应位置的字符进行比较。如果出栈的字符与字符串中对应位置的字符不相等，则说明该字符串不是回文；如果所有字符都相等，则说明该字符串是回文。</p>