栈的概念及结构

栈：一种线性数据结构，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶 (Top）, 另一端称为栈底 [Bottom]。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。即最后进入的元素最先被访问。

• 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

• 栈具有以下几个特点：

1.后进先出（LIFO）：最后进入栈的元素最先被访问，而最先进入栈的元素最后被访问。

2.只允许在一端进行插入和删除操作：栈通常只允许在栈顶进行插入和删除操作，而不允许在其他位置进行操作。

3.栈顶指针：栈顶指针指向栈顶元素，它随着元素的插入和删除而改变。

• 栈的结构
  

对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化。特别是插入和删除操作.那栈的结构用数组还是链表实现？

使用数组可以比链表更快，因为数组的数据在内存中是连续存储的，下标可以随机访问。而链表的数据则是分散存储的。意味着，当CPU访问数组时，它可以利用缓存行（cache line）的特性，从内存中读取多个相邻的元素到缓存中，以便更快地访问这些元素。而对于链表，则需要在内存中跳跃，以获取每个元素的地址，这可能会导致缓存未命中（cache miss），从而降低访问速度。但是数组长度是固定的，如果需要动态扩展栈的大小，需要进行复制和移动操作，比较耗费时间和空间。链表实现的栈可以动态扩展大小，但是需要额外的指针空间来存储链表节点，访问元素时速度可能会比较慢.下面我总结下用数组和链表各自的优缺点。

• 用数组实现的优点

1 . 数组在内存中是连续存储的，因此访问元素时速度较快。CPU高速缓存命中率会更高。

2. 下标的随机访问。尾插尾删效率不错.

3. 数组实现相对简单，不需要额外的指针来维护元素之间的关系。

• 数组实现的缺点

1 . 数组的大小是固定的，因此在栈空间不足时需要进行扩容操作，这可能会导致性能下降。

2 . 在删除元素时，需要移动数组中的其他元素，这也可能会导致性能下降。

• 用链表实现的优点

1 .链表的大小可以动态调整，因此可以更好地利用空间。

2 . 任意位置插入删除O(1) ，链表的性能较高，因为不需要移动其他元素。

• 链表实现的缺点

1 . CPU高速缓存命中率会更低,不是连续存储的，因此访问元素时速度较慢。

2. 不支持下标的随机访问.

• 用链表还是用数组结构实现这个问题的答案取决于具体的应用场景和需求，本章节我们使

用数组存储结构来实现.
栈数组存储结构

typedef int STDateType; // 定义栈元素类型
typedef struct StackNode
{
  STDateType * a;  // 数组指针
  int top;     // 栈顶
  int capacity; // 栈的容量
}st;

a 是一个指向栈数据存储区的指针，top 是栈顶的索引值，capacity 是栈的容量。

栈接口的实现

栈的初始化

• 这里讲解下有的人是把top给成-1的，栈顶指针 top 被初始化为 -1，表示栈中没有任何元

素。当向栈中插入第一个元素时，我们需要将 top 的值加 1，然后将该元素存储在数组中 top 所指向的位置。此时，top 的值为 0，表示栈中有一个元素。因此，栈中有一个元素是因为插入了第一个元素。所以这里要取分一下.top给成0还是-1，根据场景应用给成多少。

void STInit(ST* pst)
{
  assert(pst);
  pst->a = NULL;  
  pst->top = 0;   // top 指向栈顶数据的下一个位置
  pst->capacity = 0;
}

入栈

• 入栈步骤

1.首先判断栈是否已满，即栈顶指针 top 是否等于栈的容量 capacity。如果栈已满，则需要扩容，这里的扩容策略是将栈的容量翻倍，如果栈的容量为 0，则新分配的容量为 4，将扩容后的数组 tmp 赋值给原来的数组 pst->a，并更新栈的容量为 newCapacity。

2.将元素 x 存储在栈顶指针 top 所指向的位置,然后将栈顶指针 top 加 1，指向下一个空闲位置，以便下一次入栈操作。

void STPush(ST* pst, STDataType x)
{
  if (pst->top == pst->capacity) //判断栈是否已满
  {
    int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));//扩容
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    pst->a = tmp; //赋值给原来的数组
    pst->capacity = newCapacity; //更新栈的容量
  }
  pst->a[pst->top] = x; //入栈
  pst->top++; //+1 指向下一个空闲位置
}

出栈

• 判断栈中是否存在元素，如存在我们将栈顶指针 top 减一，即 pst->top–，表示将栈顶元

素弹出。

void STPop(ST* pst)
{
  assert(pst); //断言判断是否指针为空
  assert(!STEmpty(pst)); //判断栈中是否存在元素
  pst->top--; //将栈顶元素弹出。
}

获取栈顶元素

• 首先确保栈不为空，如不为空返回栈顶元素的值，即数组 a 中下标为 top - 1 的元素。

STDataType STTop(ST* pst)
{
  assert(pst);  //断言判断是否指针为空
  assert(!STEmpty(pst)); //判断栈中是否存在元素
  return pst->a[pst->top - 1]; //返回栈顶元素的值
}

判断栈是否为空

• 如果栈顶值为0，就代表栈为空.返回真，反之返回假.

bool STEmpty(ST* pst)
{
  assert(pst);  //断言判断是否指针为空
  return pst->top == 0; //判断是否为空
}

获取栈中有效元素个数

• 该代码没有什么可说的…直接看吧

int STSize(ST* pst)
{
  assert(pst);   //断言判断是否指针为空
  return pst->top; //返回栈的元素个数
}

栈的销毁

• 当我们不打算使用这个栈时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便

于留出空间给其他程序或软件使用。 我们只需要把栈的数组空间释放，避免内存泄漏。同时将指向数组的指针 a 置为 NULL，避免出现野指针。最后，将栈的容量 capacity 和栈顶指针 top 置为 0，表示栈已经被销毁。

void STDestroy(ST* pst)
{
  assert(pst); //断言判断是否指针为空
  free(pst->a); //函数释放栈的数组空间
  pst->a = NULL; //置为NULL，避免出现野指针
  pst->top = pst->capacity = 0;  //将栈的容量 capacity 和栈顶指针 top 置为 0
}

总结

• 栈是一种简单但非常有用的数据结构，掌握它的基本概念、操作和实现方式对于编程学习

和刷题，后面的面试都非常重要。