堆栈（顺序存储）数组方式
typedef struct{
int Data[MAXSIZE];
int Top;
}Stack;
void Push(Stack *stack,int value){
if(stack->Top==MAXSIZE-1){//数组有界
printf("堆栈满");
}else{
stack->Data[++(stack->Top)]=value;
return;
}
}
int Pop(Stack *stack){
if(stack->Top==-1){//为空检查
printf("堆栈为空");
return ERROR;
} else
return stack->Data[stack->Top--];
}
一个有界数组存储两个堆栈
#define MAXSIZE 50
/*一个有界数组存储两个堆栈，如果数组有空间则执行入栈操作，（一个向右增长，一个向左增长）
* */
typedef struct DStack{
int data[MAXSIZE];
int Top1;
int Top2;
}Stacks;
void Push(Stacks *stacks,int value,int Tag){
if(stacks->Top2-stacks->Top1==1){
printf("堆栈满");return;
}
if(Tag==1)
stacks->data[++stacks->Top1]=value;
else
stacks->data[--stacks->Top2]=value;
}
int Pop(Stacks *stacks,int Tag){
if(Tag==1){
if(stacks->Top1==-1){
printf("堆栈1空");
return NULL;
}else {
return stacks->data[stacks->Top1--];
}
}else{
if(stacks->Top2==MAXSIZE){
printf("堆栈2空");
return NULL;
}else{
return stacks->data[stacks->Top2++];
}
}
}
int main() {
Stacks *stacks;
stacks->Top1=-1;
stacks->Top2=MAXSIZE;//初始化两个堆栈头指针
return 0;
}
堆栈（链式存储）
/*用单向链表表示栈时候，栈Top结点一定是链头结点
* */
typedef struct Node{
int value;
struct Node *next;
}LinkedStack;
LinkedStack * CreateLinkedStack(){
LinkedStack *stack;
stack=(LinkedStack *)malloc(sizeof(LinkedStack));
stack->next=NULL;
return stack;
};
int isEmpty(LinkedStack *stack){//注意Top结点没有值，只有一个单链表的头指针
return (stack->next==NULL);
}
void Push(LinkedStack *stack,int value){
LinkedStack *insertElement;
insertElement=malloc(sizeof(LinkedStack));//分配内存空间
insertElement->value=value;//插入的值赋值给结点
insertElement->next=stack->next;//将已存在链表链接到插入的结点
stack->next=insertElement;//改变Top结点
}
int Pop(LinkedStack *stack){
int result;
LinkedStack *popElement;
if(isEmpty(stack)){
printf("链表为空");
return ERROR;
}else{
popElement=stack->next;
result=popElement->value;
stack->next=popElement->next;
free(popElement);//记得释放无用内存空间
return result;
}
}
中缀表达式如何转换为后缀表达式
从头到尾读取中缀表达式的每一个对象
1.运算数：直接输出
2.左括号：压入堆栈
3.右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈不输出）
4.运算符：
若优先级大于栈顶运算符，则压栈
若优先级小于等于栈顶运算符，将栈顶运算符弹出，
再比较新的栈顶运算符，直到改运算符大于栈顶运算符优先级为止，然后压栈5.若个对象处理完毕，则把堆栈中存留的运算符一并输出
堆栈用途：
- 函数调用及递归实现
- 深度优先搜索
- 回溯算法
