栈
先上官方定义：栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
举个例子向AK-47的弹夹那样，最后压（存）入的子弹最先被打出去，最开始压入的子弹，最后才能被射出。
用子弹弹夹来类比栈
再举一个例子，一个空盘子，每烙好一张饼都放在盘子最上面（这是push压入栈中），烙完后，盘子里堆了一叠饼，最下面的是最先烙好的，最上面的是刚烙好的，每一次吃只能从上面一张张拿，吃完一张拿下一张饼（这是Pop出栈），直到盘子为空。
图片来自百度，不做盈利
说了那么多，总结一下：这就是，先入后出，后入先出。
顺序存储栈
即物理结构是顺序存储，先开辟一块内存空间（和顺序存储链表一样有没有），每push一个新元素，栈顶标记top+1，直到开辟的空间被存满。每Pop一个栈顶元素，top-1，也就是下一个元素变成栈顶元素。
定义数据结构
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
/* 顺序栈结构 */
typedef struct
{
ElemType data[MAXSIZE];
int top; /* 用于栈顶指针 */
}Stack;
顺序存储栈，事先开辟空间，白色未使用
初始化
Status InitStack(Stack *S)
{
S->top = -1;
return OK;
}
清空
Status ClearStack(Stack *S)
{
S->top = -1;
return OK;
}
获取栈顶元素
Status GetTop(Stack S, ElemType *e)
{
if (S.top == -1) return ERROR;
*e = S.data[S.top];
return OK;
}
获取栈长度
int StackLength(Stack S)
{
return S.top+1;
}
Push
Status PushStack(Stack *S, ElemType e)
{
if (S->top == MAXSIZE -1) return ERROR;
S->top++;
S->data[S->top] = e;
return OK;
}
Pop
Status PopStack(Stack *S, ElemType *e)
{
if (S->top == -1) {
return ERROR;
}
*e = S->data[S->top];
S->top--;
return OK;
}
输出测试
int main(int argc, const char * argv[]) {
// 创建栈
Stack S;
InitStack(&S);
for (int i = 0; i < 10; i++) {
PushStack(&S, i);
}
StackPrint(S);
// 出栈
ElemType e;
PopStack(&S, &e);
printf("出栈：%d",e);
StackPrint(S);
// 获取栈顶元素
GetTop(S, &e);
printf("栈顶：%d\n",e);
// 输出长度
printf("栈长度：%d\n",StackLength(S));
return 0;
}
链式存储栈
以链表的形式，新入栈的节点，next指向原来的栈顶节点，插在链表的最前端，成为新的栈顶（和链表的头插法像不像？？！！！）。 用top标记栈顶节点，而不是上面顺序存储的位置，每一次入栈新节点，top指向新栈顶节点，count也随之+1。出栈时，top指向栈顶节点的next节点，count-1。
链式存储栈不同状态
Push与Pop操作
定义
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
/* 链栈的每一个节点，和单链表很像有没有 */
typedef struct StackNode {
ElemType data;
struct StackNode *next;
}StackNode;
typedef struct StackNode * StackNodePtr;
/* 栈结构 */
typedef struct
{
StackNodePtr top;
int count;
}LinkStack;
初始化
Status InitStack(LinkStack *S)
{
S->top = NULL;
S->count = 0;
return OK;
}
清空
Status ClearStack(LinkStack *S)
{
if (S->top == NULL) return ERROR;
StackNodePtr p;
while (S->count != 0) {
p = S->top;
S->top = S->top->next;
free(p);
S->count--;
}
return OK;
}
获取栈顶元素
Status GetTop(LinkStack S, ElemType *e)
{
if (S.top == NULL) return ERROR;
// if (S->count == 0) return ERROR; // 也可以
*e = S.top->data;
return OK;
}
获取栈长度
int StackLength(LinkStack S)
{
return S.count;
}
Push
Status PushStack(LinkStack *S, ElemType e)
{
// 创建新元素
StackNodePtr p = (StackNodePtr)malloc(sizeof(StackNode));
if (p == NULL) return ERROR;
p->data = e;
p->next = S->top;
S->top = p;
S->count++;
return OK;
}
Pop
Status PopStack(LinkStack *S, ElemType *e)
{
if (S->top == NULL) return ERROR;
// if (S->count == 0) return ERROR; // 也可以
/* 将栈顶指针指向新的栈顶 */
StackNodePtr temp = S->top;
S->top = S->top->next;
*e = temp->data;
free(temp);
S->count--;
return OK;
}
输出测试
int main(int argc, const char * argv[]) {
// 创建栈
LinkStack S;
InitStack(&S);
for (int i = 0; i < 10; i++) {
PushStack(&S, i);
}
StackPrint(S);
ElemType e;
PopStack(&S, &e);
printf("出栈：%d\n",e);
StackPrint(S);
// 获取栈顶元素
GetTop(S, &e);
printf("栈顶：%d\n",e);
// 输出长度
printf("栈长度：%d\n",StackLength(S));
return 0;
}
image
