1.什么是栈

栈是一种特殊的线性表，其中只允许固定的一端进行插入与删除，进行输出插入删除的那一端我们称为栈顶，与之相反的一端称为栈底。在栈中，元素遵循先进后出的原则即LIFO（last in first out）。

栈因为是一种操作受到限制的线性表：栈的特点是先进后出，类似于堆盘子，先放到地上的盘子最后被取走。栈的操作有两种：入栈和出栈。入栈就是把元素放到栈顶，出栈就是把栈顶元素取出来。我们也可以想象成弹夹，先装的子弹最后射出，后装的先射出。

2.栈的基本操作

对于栈，我们对他的操作只有入栈与出栈，就栈里的元素，增加与删除，需要注意的是因为规定的特殊结构

压栈，也称入栈，进栈，(增加元素)

出栈（删除元素）

因为这种特殊的结构，我们会发现在操作时栈底的元素永远也不可能在他的前一个出栈，无论何时出栈还是入栈。

3.栈的实现

栈的实现也是多种多样：

1.数组实现：数组实现优点较为明显，我们可以下标访问每个栈中的元素，且结构简单，空间利用率高，唯一的缺点是当容量不足时我们需要扩容。

2..单链表实现：单链表也可以实现栈这种结构，但需要注意我们在出栈与入栈的时候，是需要知道为节点的前一个元素，而单链表是无法直接访问的，需要遍历时间复杂度为O(n)，于是我们在实现时，是利用头节点作为栈顶的，入栈即就是头插的方式可以实现栈的结构，对于入栈与出栈时间复杂度为O(1)，不过单链表在访问栈中的元素时时间复杂度还是O(n).

3.双链表实现：最不建议的一种实现方式，因为对于双链表不仅增加了节点里的指针，结构更复杂，空间利用也不高，且也就是双链表的头插方式实现的，相对于前两种实现，没这个必要。

所以今天我们就用优点较为明显的数组来实现栈，我们也会发现栈的实现其实是非常简单的。

1.结构体与函数接口

我们在定义栈的结构体时，发现还是跟顺序表的定义一样，不过表示实际元素大小我们这里用top表示，即我们称为栈顶也是大小，同时给出总容量。

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
#define DATAtype int 
typedef struct Stack
{
  DATAtype* a;//实现栈的数组
  int top;//记录栈顶
  int capacity;//总空间
}ST;
void Stackinit(ST**p);//初始化栈
void Stackdetroy(ST** p);//销毁栈
void Stackpush(ST** p, DATAtype x);//入栈
void Stackpop(ST** p);//出栈
int Stacksize(ST** p);//栈大小的返回
bool Stackempety(ST** p);//栈判空

2.初始化栈

我们这里初始化栈有 5个元素的大小空间，需要注意的是top的定义，因为在每次入栈之后top++，在进行打印时我们需要给它在减1，实现坐标的对应。top是当前元素的后一个元素的位置坐标，我们将这里定义为负1，打印时刚好打印a[0]元素，在进行迭代。

void Stackinit(ST* p)
{
  (p)->a = (DATAtype*)malloc(sizeof(DATAtype) * 5);
  (p)->capacity = 5;
  (p)->top = -1;//记录栈中数组位置
}

3.销毁栈

直接判空后free，在置为空。实现简单，不做赘述

//销毁栈
void Stackdetroy(ST* p)
{
  assert(p);
  free((p)->a);
  (p)->a = NULL;
  (p)->capacity = 0;
  (p)->top = 0;
}

4.入栈

入栈首先要对容量判断。因此这里还需要实现容量判断并扩容的操作，这里我直接定义一个函数。

入站的具体操作很简单，赋值并加加。

判断容量：

void chckcapacity(ST* p)
{
  //若容量不够，则扩容
  if ((p)->top == (p)->capacity)
  {
    DATAtype*tmp= (DATAtype*)realloc((p)->a,sizeof(DATAtype) * (p)->capacity * 2);
    if (tmp == NULL)
    {
      printf("realloc fail");
      return;
    }
    (p)->a = tmp;
    (p)->capacity = (p)->capacity * 2;
    printf("容量不够，已自动扩容，当前容量：%d\n", (p)->capacity);
  }
}

入栈：

void Stackpush(ST* p, DATAtype x)
{
  //检查容量
  chckcapacity(p);
  (p)->a[(p)->top] = x;
  (p)->top++;
}

5.出栈

操作也是简单，只要让数组访问不到即可，直接减减。

//出栈
void Stackpop(ST*p)
{
  (p)->top--;
  assert((p)->top);
  assert(p);
  //检查是否过量出栈
}

6.返回栈元素数量大小

很简单，返回top即可

//返回大小
int Stacksize(ST* p)
{
  assert(p);
  return (p)->top;
}

7.判空

bool Stackempety(ST* p)
{
  assert(p);
  if ((p)->top == NULL)
  {
    return true;
  }
  else
  {
    return false;
  }
}

8.打印栈

这个操作在定义top时需要注意一下，top是指向当前栈顶的下面那一个元素，在迭代打印时，注意访问是否越界的问题。

oid stackprintf(ST* p)
{
  assert(p);
  while ((p)->top>=0)
  {
    printf("%d->", (p)->a[(p)->top-1]);
    (p)->top--;
  }
}