线性表之顺序栈

基本思想：顺序栈相当于顺序表的子集，是限制了相关操作，只允许在栈顶操作元素，基本的操作有入栈、出栈、获取栈顶元素等。 　　和链栈相比03除了不能动态增长外（目前为止），其余的操作时间复杂度都一样。 　　实现功能： 　　1.void InitStack(); 初始化栈 　　1）.new一块连续的空间存放数据。 　　2）.初始化栈顶指针（这里的指针并不是真的指针，而是一个指示变量） 　　如图： 　　2.void DestroyStack(); 销毁栈 　　1）.delete m_data。 　　2）.把栈顶指针指向-1 　　3.bool IsEmpty(); 栈是否为空 线性表之顺序栈是一种基于数组的数据结构，它在计算机科学中被广泛应用于各种算法和程序设计中。顺序栈作为线性表的一个特例，其核心特性在于它仅允许在表的一端，即栈顶进行元素的添加和移除，这种操作方式也被称为后进先出（LIFO）原则。 在顺序栈的设计中，主要有以下几个关键的操作： 1. **初始化栈（InitStack）**： 初始化栈通常涉及到分配一块连续的内存空间来存储栈中的元素，并设置一个栈顶指针来跟踪栈顶位置。这个指针不是真正的C++指针，而是一个用来指示当前栈顶元素位置的变量，初始时通常设置为-1，表示栈为空。 2. **销毁栈（DestroyStack）**： 销毁栈意味着释放之前分配的内存空间，并将栈顶指针重置为-1，以表示栈已无元素。 3. **判断栈是否为空（IsEmpty）**： 当栈顶指针top等于-1时，说明栈中没有元素，此时栈为空。 4. **判断栈是否已满（IsFull）**： 如果栈顶指针top等于预先设定的最大容量stackSize减1，说明栈已满，无法再添加新的元素。 5. **获取栈的大小（GetSize）**： 栈的大小可以通过返回栈顶指针top加1来得到，这表示栈中元素的个数。 6. **入栈（Push）**： 向栈中添加元素时，需要首先检查栈是否已满，然后将元素存入m_data数组的栈顶位置（m_top加1后的位置），并更新栈顶指针m_top。 7. **出栈（Pop）**： 出栈操作仅需将栈顶指针m_top减1，表示栈顶元素已被移除，但不实际删除元素，因为数组中的元素并未移动。 8. **带返回值的出栈（PopE）**： 在出栈的同时返回栈顶元素，此时需要先保存栈顶元素，然后执行出栈操作。 9. **获取栈顶元素（GetTop）**： 获取栈顶元素而不移除它，只是简单地返回栈顶指针指向的数组元素。 10. **遍历栈（Print）**： 遍历栈通常是为了调试或输出栈中所有元素，可以依次访问从栈底到栈顶的所有元素。 11. **清空栈（ClearStack）**： 清空栈只需将栈顶指针重置为-1，表示栈内没有元素，但不涉及释放内存空间，因为数组仍然保留。 顺序栈相对于链栈的优势在于，由于元素存储在连续的内存空间中，其元素访问速度较快。然而，顺序栈的缺点在于其大小固定，无法动态扩展，当预设的容量不足时，需要重新分配更大的内存空间，这一过程可能导致效率下降。相比之下，链栈可以方便地添加和删除节点，实现动态增长，但访问速度相对较慢。因此，根据具体的应用场景和性能需求，选择使用顺序栈还是链栈至关重要。