2.2.4 入栈
//入栈 void SeqStackPush(seqstack *s,DataType value) { if(SeqStackIsFull(s)) { printf("栈满了!\n"); return; } s->pos++; s->data[s->pos] = value; return; }
2.2.5 出栈
//出栈 DataType SeqStackPop(seqstack *s) { if(SeqStackIsEmpty(s)) { printf("栈为空!\n"); return (DataType)-1; } DataType value = s->data[s->pos]; s->pos--; return value; }
2.3 链栈(链式栈)
整体代码
mian.c //main.c #include "linkstack.h" int main(int argc, char const *argv[]) { stack s; InitStack(&s); push(&s,100); push(&s,200); push(&s,300); push(&s,400); push(&s,500); push(&s,600); push(&s,700); while(!EmptyStack(&s)) { printf("出栈:%d\n",pop(&s)); } return 0; }
linkstack.c
//linkstack.c #include "linkstack.h" //初始化栈信息 void InitStack(stack *s) { s->length = 0; s->top = NULL; } //入栈 void push(stack *s,DataType value) { if(NULL == s) { printf("栈空间分配失败,初始化失败!\n"); return ; } Node *tmp = (Node *)malloc(sizeof(Node)); tmp->next = NULL; tmp->data = value; tmp->next = s->top; s->top = tmp; s->length++; } //获取栈顶元素 DataType GetTop(stack *s) { if(NULL == s) { return (DataType)-1; } if(s->top == NULL) { return (DataType)-1; } return s->top->data; } //出栈 DataType pop(stack *s) { if(NULL == s) { return (DataType)-1; } if(s->top == NULL) { return (DataType)-1; } Node *tmp = s->top; s->top = tmp->next; DataType value = tmp->data; free(tmp); tmp = NULL; s->length--; return value; } //判断栈是否为空 int EmptyStack(stack *s) { return s->top == NULL ? 1 : 0; } //清空栈 int ClearStack(stack *s) { if(NULL == s) { return (DataType)-1; } if(s->top == NULL) { return (DataType)-1; } Node *tmp = s->top; while(tmp) { s->top = tmp->next; free(tmp); tmp = s->top; s->length--; } return 1; }
练习 四则运算器
//判断符号的优先级 int Priority(char ch) { switch (ch) { case '(': return 3; case '*': case '/': return 2; case '+': case '-': return 1; default: return 0; } } //四则混合计算器 void calculator() { stack s_sum, s_opt; InitStack(&s_sum); InitStack(&s_opt); char opt[128] = {0}; printf("请输入表达式:\n"); scanf("%s",opt); int i = 0,tmp = 0,num1,num2; while(opt[i] != '\0' || EmptyStack(&s_opt) != 1) { if(opt[i] >= '0' && opt[i] <= '9') //运算数 { tmp = tmp *10 + opt[i] - '0'; i++; if(opt[i] < '0' || opt[i] > '9') { push(&s_sum,tmp); tmp = 0; } } else //操作符 { if(EmptyStack(&s_opt) == 1 || Priority(opt[i]) > Priority(GetTop(&s_opt))|| (GetTop(&s_opt) == '(' && opt[i] != ')')) { push(&s_opt,opt[i]); i++; continue; } if(GetTop(&s_opt) == '(' && opt[i] == ')') { pop(&s_opt); i++; continue; } if(Priority(opt[i]) <= Priority(GetTop(&s_opt)) ||opt[i] == ')' && GetTop(&s_opt)!= '('|| opt[i] == '\0' && EmptyStack(&s_opt) != 1) { switch (pop(&s_opt)) { case '+': num1 = pop(&s_sum); num2 = pop(&s_sum); push(&s_sum,num1 + num2); break; case '-': num1 = pop(&s_sum); num2 = pop(&s_sum); push(&s_sum,num2 - num1); break; case '*': num1 = pop(&s_sum); num2 = pop(&s_sum); push(&s_sum,num1 * num2); break; case '/': num1 = pop(&s_sum); num2 = pop(&s_sum); push(&s_sum,num2 / num1); break; default: break; } } } } printf("%d\n",GetTop(&s_sum)); }