数据结构复习笔记 - 顺序栈

数据结构复习笔记 - 顺序栈

简单介绍

顺序栈是基于 vector 实现的栈数据结构，采用下标 _topIndex 标记栈顶位置，-1 表示空栈。入栈和出栈操作都在栈顶进行，时间复杂度为 O(1)。

方法列表

方法	功能	返回值
push(T entity)	入栈	bool
pop()	出栈	bool
top()	获取栈顶元素	T
isEmpty()	判空	bool
size()	元素数量	int

重点注意

• _topIndex 初始化为 -1，表示空栈
• pop() 前必须先判空，否则 _topIndex 可能越界
• top() 返回栈顶元素但不出栈，空栈返回 T() 默认构造

完整代码

#include <vector>

/**
 * 顺序栈模板类
 * 采用 vector 作为底层存储，_topIndex 标记栈顶位置
 * @tparam T 元素类型
 */
template <class T> class Stack {
private:
  int _topIndex;          // 栈顶下标，-1 表示空栈
  std::vector<T> _data;   // 存储元素的 vector

public:
  /**
   * 默认构造函数
   * 初始化栈顶下标为 -1（空栈）
   */
  Stack() : _topIndex(-1) {}

  /**
   * 出栈操作
   * 移除栈顶元素，_topIndex 减 1
   * @return 成功返回 true，空栈返回 false
   */
  bool pop() {
    if (!isEmpty()) {
      _data.pop_back();   // vector 弹出最后一个元素
      _topIndex--;        // 栈顶下标前移
      return true;
    }
    return false;
  }

  /**
   * 入栈操作
   * 将元素压入栈顶，_topIndex 加 1
   * @param entity 要入栈的元素
   * @return 成功返回 true
   */
  bool push(T entity) {
    _data.push_back(entity);  // vector 尾部添加元素
    _topIndex++;              // 栈顶下标后移
    return true;
  }

  /**
   * 判空操作
   * @return 栈为空返回 true，否则返回 false
   */
  bool isEmpty() { return _topIndex == -1; }

  /**
   * 获取栈顶元素
   * @return 栈顶元素，空栈返回 T() 默认构造
   */
  T top() {
    if (isEmpty()) {
      return T();
    } else {
      return _data[_topIndex];
    }
  }

  /**
   * 获取栈中元素数量
   * @return 元素个数
   */
  int size() { return _topIndex + 1; }
};