顺序栈详细介绍
定义与特点
顺序栈（Sequential Stack）是一种基于数组实现的栈结构，利用数组的连续内存空间存储元素，遵循后进先出（LIFO）原则。其核心特点包括：
-
固定或动态容量：初始化时可指定最大容量（静态），或动态扩容（需额外实现）。
-
高效访问：通过索引直接操作栈顶，时间复杂度为 O(1)。
-
内存紧凑：元素连续存储，无额外指针开销。
程序结构
-
头文件
stack.h-
定义
stack类，包含私有成员：-
int *m_stack：动态数组实现的栈。 -
int topIndex：栈顶索引（初始化为-1，表示空栈）。 -
int m_maxsize：栈的最大容量。
-
-
公有成员函数包括构造函数、析构函数及栈的基本操作（入栈、出栈、查看栈顶等）。
-
-
实现文件
stack.cpp-
实现
stack类的成员函数：-
构造函数：根据用户输入的容量动态分配内存。
-
析构函数：释放动态数组内存。
-
核心操作：
push（入栈）、pop（出栈）、peek（查看栈顶）、isempty/isfull（栈状态检查）等。
-
-
主函数：提供交互式菜单，支持用户通过命令行操作栈。
-
核心功能实现
构造函数与析构函数
stack::stack(int size) {m_maxsize = size;m_stack = new int[m_maxsize]; // 动态分配内存
}stack::~stack() {delete[] m_stack; // 释放内存
}
入栈 (push)
检查栈是否已满，未满则将元素添加到栈顶，并更新 topIndex。
-
void stack::push(int element) {if (isfull()) {cout << "栈容量已满！";return;}m_stack[++topIndex] = element; // 先增索引，再赋值 }出栈 (
pop) -
检查栈是否为空，未空则移动栈顶指针
topIndex--（逻辑删除）。void stack::pop() {if (isempty()) {cout << "栈空" << endl;return;}topIndex--; // 仅移动指针，不实际删除数据 }查看栈顶 (
peek)void stack::peek() const {cout << "当前栈顶元素：" << m_stack[topIndex] << endl; } -
辅助功能
-
isempty()：通过topIndex == -1判断栈空。 -
isfull()：通过topIndex == m_maxsize - 1判断栈满。 -
size()：返回topIndex + 1（当前元素数量）。 -
getElement()：遍历栈并打印所有元素。
-
主函数交互逻辑
-
用户输入栈的最大容量后，进入循环菜单，支持以下操作：
-
1.入栈：输入数字并压入栈。
-
2.出栈：弹出栈顶元素。
-
3.查看栈顶：显示栈顶元素。
-
4-7：检查栈状态、元素数量或输出全部元素。
-
8.退出：结束程序。
-
STL对顺序栈的支持
在C++标准模板库（STL）中，虽然没有直接名为“顺序栈”的独立容器，但可以通过std::stack适配器结合顺序容器（如std::vector或std::deque）来实现顺序栈的功能。以下是具体说明：
1. STL中的栈实现：std::stack
std::stack是一个容器适配器（Container Adapter），它基于其他底层容器（如std::vector、std::deque或std::list）实现栈的后进先出（LIFO）特性。默认情况下，std::stack使用std::deque作为底层容器，但可以显式指定为std::vector以实现顺序存储。
定义与初始化
#include <stack>
#include <vector>// 默认使用 deque
std::stack<int> stack_default; // 显式指定 vector 作为底层容器（实现顺序栈）
std::stack<int, std::vector<int>> stack_vector;
2. 顺序栈的实现原理
若需严格实现顺序栈（基于连续内存的数组），可将std::vector指定为std::stack的底层容器：
-
底层存储：
std::vector通过动态数组实现，内存连续，支持随机访问。 -
操作效率：
-
push()：在尾部插入，时间复杂度 O(1)（摊还）。 -
pop()：在尾部删除，时间复杂度 O(1)。 -
top()：直接访问尾部元素，时间复杂度 O(1)。
-
示例代码
#include <iostream>
#include <stack>
#include <vector>int main() {std::stack<int, std::vector<int>> seq_stack;// 入栈seq_stack.push(10);seq_stack.push(20);seq_stack.push(30);// 查看栈顶std::cout << "栈顶元素: " << seq_stack.top() << std::endl; // 输出 30// 出栈seq_stack.pop();std::cout << "出栈后栈顶元素: " << seq_stack.top() << std::endl; // 输出 20// 检查栈是否为空std::cout << "栈是否为空: " << (seq_stack.empty() ? "是" : "否") << std::endl; // 输出 "否"// 栈内元素数量std::cout << "栈大小: " << seq_stack.size() << std::endl; // 输出 2return 0;
}3. 为什么默认使用std::deque？
STL默认选择std::deque作为std::stack的底层容器，原因包括：
-
平衡的性能：
std::deque在头部和尾部插入/删除的时间复杂度均为 O(1)。 -
内存管理：
std::deque由多个固定大小的块组成，避免std::vector扩容时的整体拷贝开销。 -
安全性：
std::deque不会因元素插入导致迭代器失效（与std::vector不同）。
但对于严格的顺序栈需求，std::vector是更合适的选择，因为其内存连续，访问局部性更好。
4. 顺序栈的核心操作与STL对比
| 操作 | 自定义顺序栈（基于数组） | STL std::stack（基于std::vector） |
|---|---|---|
| 入栈 | push()，需检查栈满并扩容 | push()，自动处理扩容 |
| 出栈 | pop()，仅移动指针 | pop()，直接删除尾部元素 |
| 查看栈顶 | peek()，返回m_stack[topIndex] | top()，返回vector.back() |
| 栈空检查 | topIndex == -1 | empty() |
| 动态扩容 | 需手动实现（如翻倍容量） | 自动扩容（vector的push_back()机制） |
5. 适用场景
-
需要严格顺序存储：例如对内存连续性有要求的算法（如缓存优化）。
-
已知最大容量：使用
std::vector的reserve()预分配内存，避免频繁扩容。 -
兼容STL算法：
std::stack可与其他STL组件（如迭代器、算法库）无缝协作。
总结
该程序完整实现了栈的基本功能（LIFO），代码结构清晰，适合初学者学习动态内存管理和栈的核心操作。主函数通过交互式菜单增强了实用性，但需进一步完善输入验证和内存管理。