文章目录
1.栈的定义
栈可以看作是一个受约束的线性表，插入和删除操作都在栈顶进行。
怎么理解呢？我梦可以将栈理解成一个箱子，每次只能将一本书从箱子放入或拿出，并且每次只能在箱子顶上将书放入或拿出，如图：
简单介绍：
- 由上图这种特性可知，栈具有数据后入先出，先入后出的特点，通常将数据插入称为压入栈(push)，将数据取出叫做弹出栈(pop)，栈也被称为后入先出表。
- 栈顶指针，通常是指向栈顶的元素。用数组实现栈时，指向最后一个下标，用链表实现栈时，指向链表头，方便实现出栈与出栈。
2.栈的主要操作
- 栈的初始化：生成空栈。
- 判断栈是否满：数组实现判断即数据长度等于数据容量时，链表实现时，不需要判断。(我将其写入入栈代码里了)。
- 入栈：数组实现，将数据插入栈顶位置，链表实现，使用头插法，将数据插入链表头。
- 判断栈是否为空：数组，栈顶指针TOP=-1时，链表，链表为空(NULL)时。(我将其写入出栈代码里了)
- 出栈：数组：将栈顶指针的数据返回，并且将TOP减1，链表，将链表头删除即可。
3.栈的代码实现
用C语言数组实现栈：
typedef int Elementtype;//方便维护
struct Node{
int top;//栈顶指针
int capacity;//最大容量
Elementtype *data;//保存数据的数组
};
用链表实现栈
//将表头视为栈顶，不需要定义栈顶指针
typedef int Elementtype;
struct Node {
Elementtype data;
struct Node *next;
};
1.栈的初始化：
数组：
这里申请了一个栈空间stack，符号初值后将其返回，也可以在main函数中定义一变量，在将其作为参数传入(注意是地址)，在进行初始化，这样就不需要返回值了。
Stack Stackinit(){
Stack stack = (Stack)malloc(sizeof(struct Node));
stack->data = (Elementtype *)malloc(sizeof(Elementtype)* 4);
stack->capacity = 4;//最大容量设为4
stack->top = -1;//开始栈顶指针为-1
return stack;
}
链表：
Stack Stackinit(){//带头节点
Stack stack = (Stack)malloc(sizeof(struct Node));
stack->next = NULL;
return stack;
}
2.入栈与判断栈满
数组：
入栈时要判断栈里是否满了，在决定是否插入数据。
插入数据只需要先将top+1，再在top位置赋值即可
void Stackpush(Stack stack, int x){
assert(stack);
if (stack->top == stack->capacity){//满了加空间
stack->data = realloc(stack->data, sizeof(Elementtype)*stack->capacity * 2);//扩容
stack->capacity *= 2;
}
stack->top++;
stack->data[stack->top] = x;
}
链表：
注意使用的是头插法，定义一个头节点，先将插入节点指向头节点的下一个，再将头节点指向插入节点。
static Stack Stackcreat(int x){//创造一节点
Stack stack = (Stack)malloc(sizeof(struct Node));
stack->data = x;
stack->next = NULL;
return stack;
}
void Stackpush(Stack stack, int x){
assert(stack);
Stack ass = Stackcreat(x);
ass->next = stack->next;
stack->next = ass;
}
3.出栈与判断栈空
数组：
出栈的时候先判断是否栈为空，即top减为-1时。
先将数据取出，再将top减减即可。
Elementtype Stackpop(Stack stack){
assert(stack);
if (stack->top == -1){
printf("empty!\n");
}
Elementtype ass = stack->data[stack->top];
stack->top--;
return ass;
}
链表：
出栈时也需要判断栈是否为空。即判断链表是否为空。
Elementtype Stackpop(Stack stack){
assert(stack);
if (stack->next == NULL){
printf("empty\n");
}
Stack temp = stack->next;
stack->next = temp->next;
Elementtype ass = temp->data;
free(temp);//注意要释放
return ass;
}