手撕数据结构—栈
Tips
不得不再次提一下这个语法问题，当数组创建的时候，进行初始化的时候，分为全部初始化或者说部分初始化，对于不完全初始化而言，剩下的部分就全部默认为零。现在比如说你想对整型数组的1万个元素把它全部变成-1，不能够仅仅在一个花括号里面写个-1，只是第一个元素变成-1，然后其他的都变成0了。之后你只能用memset
栈以及先进后出原则
栈和队列其实也是一个线性表。线性表也就是说你这个数据至少在逻辑上都是依次线性存储，一个一个挨着挨着这样存储这么一个概念。
栈作为一种特殊的线性表，它只允许在固定的一端进行数据的插入或删除元素操作。进行数据插入和删除操作的那一端就被称为栈顶。因此很容易理解栈中的数据元素遵守后进先出原则。
压栈与出栈
栈的插入操作叫做进栈/压栈/入栈，这是在栈顶完成的。
栈的删除操作叫做出栈，这也是在栈顶完成的。所以说它是在同一端进行操作。
在这边值得一提的是，比如说现在有一堆元素，对于同一进栈的顺序，但是出栈序列可以多种多样，因为并没有规定什么时候可以出栈，你可以使所有元素放进栈里面之后再依次出栈；当然你也可以是在边进栈的过程中可以出栈。我随便举个例子好了：比如说进栈序列为1234，那么出栈序列可以比如为1432，2341，3421，但是断然断然不可能是3124。
栈的实现
栈的话可以用数组去实现，也可以用链表去实现。肯定是数组，用数组来实现栈的话嘎嘎香啊，比如说你就可以把数组的右端当成一个栈的栈顶。如果要说真有一个弊端的话，那就是说用数组来模拟栈的话需要扩容。
那如果非要用链表去实现，也是完全可以的：能用单链表就用单链表，你用双向链表的话，还多一个指针呢，能省一点就是一点。
但是用单链表的话由于尾删啊尾插啊这些操作都需要去从phead开始去往后去遍历去找尾（注意链表不支持下标访问操作），这会相当的麻烦，因此就想了一个办法。把整个链表的左端当成栈顶，那么这样子的话，我的入栈与出栈相当于单链表的头插头删，效率非常之高。
但如果说非要选一个的话，用数组和链表来模拟的话都非常可以，因为都是O(1)的插入删除（数组的话可以支持下标访问，把数组的右端当成栈顶；链表的话把他的左端当成栈顶，头插头删也是O(1)）。可能你还是会选择链表，但是别忘了数组的缓存命中率与利用率比链表要高。
栈的创建(创建结构体)
凡是有多个数据，都放到一个结构体里面。
对于这个结构体有三个要素，一个是容量，一个是栈顶top，还有一个我是等会儿从堆区开辟内存空间之后返回来的地址，需要用一个指针接收一下，标记一下地址。
typedef int STDataType;
typedef struct Stack
{STDataType* p;int top;int capacity;
}ST;栈的初始化
在初始化的时候有一个比较容易出错的地方，就是必须得先搞清楚这个top到底是什么东西，我就假定这个top指向此时此刻的栈顶元素。那么这时候由于要初始化，此时栈顶也压根儿没有任何元素，因此top就指向-1/那如果我说这个top是栈顶元素的下一个位置，那此时此刻初始化的时候，这个top应该指向0。
我们为了跟之前的顺序表保保持一致，初始化的时候，这个top就给他弄成0。此时此刻，你只需要记住top的一个含义：他现在就表示栈中的元素个数
#define INIT_CAPACITY 5
void STInit(ST* ps)
{assert(ps);ps->p = (STDataType*)malloc(sizeof(STDataType) * INIT_CAPACITY);if (ps->p == NULL){perror("STInit::Malloc");return;}ps->top = 0;ps->capacity = INIT_CAPACITY;
}栈的销毁
void STDestroy(ST* ps)
{assert(ps);free(ps->p);ps->p = NULL;ps->top = 0;ps->capacity = 0;
}入栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* pp = (STDataType*)realloc(ps->p, sizeof(STDataType) * (ps->capacity) * 2);if (pp == NULL){perror("STPush::Realloc");return;}ps->p = pp;ps->capacity *= 2;}ps->p[ps->top] = x;ps->top++;
}栈的判断是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top==0;
}栈的求元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}出栈
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}栈的求栈顶元素
int STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->p[ps->top - 1];
}注：
虽然从代码上看起来与顺序表非常非常的相像。但是栈的话一定要记住他的特性，那就是后进先出。比如说：23458，我如果要访问5，那么8就必须先出去，如果说我要访问3，那么458就必须先出去。正是因为这种后进先出的特性，这也导致了我们没有写打印栈这种函数，因为栈这种玩意儿，他是不支持去遍历的，这是规定死的。
这些都是由栈的性质决定的，否则他就不叫做栈了。对于先进栈的数据，想要对他进行任何的操作，包括访问与打印，都必须把它之前栈顶的元素全部弹出去才可以，不然永远只能对栈顶的那个元素动手。