【数据结构】数据结构中的栈

前言

该篇文章来了解数据结构中的栈，栈与队列都为一种线性存储结构，同时栈与队列在逻辑结构上，都只能在头或者尾进行对数据的操作；

什么是栈

栈是一种LIFO（Last in,First
out）的结构，翻译过来即是后进先出的一种结构；栈无论是出数据还是入数据都只能从栈顶位置按顺序进行操作；

假设若是需要在一个栈中按顺序一次性存放1，2，3，4，5五个数据，则因为LIFO的规律，出栈时的顺序即为5，4，3，2，1；栈也可以在数据入栈时进行出栈，即若是只是入栈这5个数的话出栈的顺序不一定是5，4，3，2，1；

A. 可以在入栈时同时做到出栈，A入A出，B入B出…E入E出，A正确。

B.将数据按顺序一次性入栈再逐个出栈则为EDCBA，B正确。

C.入栈ABCD，此时栈内为ABCD，按顺序出栈D与C，此时栈内为AB，入栈E，此时栈内为ABE，出栈E后依次出栈B与C，C正确。

D.入栈ABCDE，此时栈内为ABCDE，出栈E，此时栈内为ABCD，C不为下一个出栈顺序，故D错误。

栈的实现

栈的实现可以用链表与数组，若是用单链表进行实现的话，入栈的时间复杂度为O(1)，但是若只是单单用单链表进行栈的实现的话，在出栈时，只能依靠遍历链表并释放尾节点，时间复杂度为O(N)。

若是用数组来实现的话，入栈的时间复杂度只需要O(1)，出栈的时间复杂度也只需要O(1)。

所以本次栈的实现使用顺序表进行实现。

栈的初始化

栈的初始化与顺序表的初始化相同，创建一个动态数组存储数据，创建一个变量top记录栈顶的位置。创建一个变量capacity记录栈是否放满，若是放满则需要扩容。

typedef int STDataType;//重命名需要存放的数据类型便于更改
typedef struct Struct 
{
  STDataType* a;//动态数组
  int top;//栈顶数据
  int capacity;//容量
}STNode;
void STInit(STNode* ps)//初始化
{
  STDataType* tmp = (STDataType*)malloc(4 * sizeof(STDataType));
  if (tmp == NULL) {
    perror("malloc");
    exit(-1);
  }
  ps->a = tmp;
  ps->capacity = 4;
  ps->top = 0;
}

栈的初始化在初始化数组时可不开数据空间也可先开一块空间当不够存放再进行扩容。

栈在初始化时可以定义栈顶的位置，栈顶位置是指向栈顶数据之后还是在栈顶位置，若是初始化栈顶为-1时，则栈指向的位置即为栈顶数据（-1位置不存放数据，存放数据时先++后赋值）。

该处初始化初始化为0，即栈顶指向栈顶数据后。

入栈

入栈时则需要对栈的空间进行判断，若数组为满则需要对数组进行扩容。否则只需要入数据并++top。

void STPush(STNode* ps, STDataType x)
{
  assert(ps);
  if (ps->capacity == ps->top) {
    STDataType* tmp = (STDataType*)realloc(ps, ps->capacity * 2 * sizeof(STDataType));
    if (tmp == NULL) {
      perror("realloc");
      exit(-1);
    }
    ps->a = tmp;
  }
  ps->a[ps->top++] = x;
}

该处不需要将扩容封装为一个函数（此处扩容只在入栈时用到）。

出栈

栈的出栈只需要将top进行-1，原数据并不需要抹去；但需要注意的时应该对top进行断言，若是栈已经为空则不能再进行出栈；

void STPop(STNode* ps)
{
  assert(ps);
  assert(ps->top);
  ps->top--;
}

栈的判空

栈的判空只需要判断top是否为空并返回布尔值即可；

栈为空返回true，否则返回false；

bool STEmpty(STNode* ps)
{
  assert(ps);
  return ps->top == 0;
}

栈内有效数据个数

栈内有效数据个数即为top所在的位置（栈顶数据下标位置+1）；

STDataType STTop(STNode* ps)
{
  assert(ps);
  return ps->a[ps->top - 1];
}

返回栈顶数据

STDataType STTop(STNode* ps)
{
  assert(ps);
  return ps->a[ps->top - 1];
}

栈的销毁

void SDestroy(STNode* ps) 
{
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}