【问题描述】
设一个顺序栈，进行出栈和入栈操作。
【输入形式】
输入若干个整数（不超过1000），依次入栈；（提示：scanf("%d",&e)==1来作为输入判断）
【输出形式】
依次出栈并输出元素值，以空格分隔。
【样例输入】
23 45 67 14 -9 20 100 89 45 30
【样例输出】
30 45 89 100 20 -9 14 67 45 23
一、顺序栈
顺序栈主要运用顺序表实现，我们需要一个指向栈底的指针和一个指向栈顶的指针。
1.1 初始化顺序栈
#include<stdio.h>
#include<malloc.h>
#define SIZE 10
#define INCREAM 10
typedef struct stack{
int *base; //栈底指针
int *top; //栈顶指针
int size; //初始空间大小
}stack,*Pstack;
void Init_stack(Pstack s){
s->base=(int *)malloc(sizeof(int)*SIZE);
s->top=s->base; //初始化栈顶指针在栈底位置
s->size=SIZE;
}1.2 判断是否空栈
int Empty_stack(Pstack s){
if(s->base==s->top) //当栈顶指针在栈底时，栈空
return 1;
else
return 0;
}1.3 入栈
void Push_stack(Pstack s,int x){
if(s->top-s->base>=s->size){ //首先要判断栈满，栈满要重新开辟空间
s->base=(int *)realloc(s->base,(s->size+INCREAM)*sizeof(int));
s->top=s->base+s->size;
s->size+=INCREAM;
}
*s->top=x; //压栈
s->top++; //栈顶指针加一
}1.4 出栈
void Pop_stack(Pstack s,int *x){
if(s->base==s->top){ //出栈要先判断栈是否为空，空栈无法出栈
return ;
}
s->top--; //先让栈顶指针指向最后一个压进去的值
*x=*s->top; //然后再输出这个值
}1.5 获取栈顶元素
void Get_top_stack(Pstack s,int *x){
if(s->base==s->top){
return ;
}
*x=*(s->top-1);
}1.6 代码实现
1.6.1 完整代码
#include<stdio.h>
#include<malloc.h>
#define SIZE 10
#define INCREAM 10
typedef struct stack{
int *base;
int *top;
int size;
}stack,*Pstack;
void Init_stack(Pstack s){
s->base=(int *)malloc(sizeof(int)*SIZE);
s->top=s->base;
s->size=SIZE;
}
int Empty_stack(Pstack s){
if(s->base==s->top)
return 1;
else
return 0;
}
void Push_stack(Pstack s,int x){
if(s->top-s->base>=s->size){
s->base=(int *)realloc(s->base,(s->size+INCREAM)*sizeof(int));
s->top=s->base+s->size;
s->size+=INCREAM;
}
*s->top=x;
s->top++;
}
void Pop_stack(Pstack s,int *x){
if(s->base==s->top){
return ;
}
s->top--;
*x=*s->top;
}
void Get_top_stack(Pstack s,int *x){
if(s->base==s->top){
return ;
}
*x=*(s->top-1);
}
int main(){
int x;
stack s;
Init_stack(&s);
while(scanf("%d",&x)==1){
Push_stack(&s,x);
}
while(!Empty_stack(&s)){
Pop_stack(&s,&x);
printf("%d ",x);
}
return 0;
}1.6.2 运行结果
二、链栈
链栈就相当于带头结点单链表的头插法，入栈就是每次都在头结点后面插入一个新元素，出栈就是每次让头结点的指针域指向第一个有效结点后面一个结点。
2.1 初始化链栈
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
typedef struct Stack{
int data;
struct Stack *next;
}Stack,*PStack;
PStack Init_Stack(){ //就是初始化一个带头结点的单链表
PStack S=(PStack)malloc(sizeof(Stack));
S->next=NULL;
return S;
}2.2 判断是否空栈
int Empty_Stack(PStack S){
if(!S->next) return 1;
else return 0;
}2.3 入栈
void Push_Stack(PStack S,int e){
PStack Pnew;
Pnew=(PStack)malloc(sizeof(Stack));
Pnew->next=NULL;
Pnew->data=e;
Pnew->next=S->next; //入栈就是头插法
S->next=Pnew;
}2.4 出栈
void Pop_Stack(PStack S,int *e){
if(S->next){ //先判断是否栈空
*e=S->next->data; //出栈就是头结点指针域指向第一个有效结点后面的结点
S->next=S->next->next; //相当于每次出栈都是删除掉第一个有效结点
}else{
return ;
}
}2.5 获取栈顶元素
void Get_Stack(PStack S,int *e){ //获取栈顶元素方法不用删除结点
if(S->next){
*e=S->next->data;
}else{
return ;
}
}2.6 代码实现
2.6.1 完整代码
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
typedef struct Stack{
int data;
struct Stack *next;
}Stack,*PStack;
PStack Init_Stack(){
PStack S=(PStack)malloc(sizeof(Stack));
S->next=NULL;
return S;
}
int Empty_Stack(PStack S){
if(!S->next) return 1;
else return 0;
}
void Push_Stack(PStack S,int e){
PStack Pnew;
Pnew=(PStack)malloc(sizeof(Stack));
Pnew->next=NULL;
Pnew->data=e;
Pnew->next=S->next;
S->next=Pnew;
}
void Pop_Stack(PStack S,int *e){
if(S->next){
*e=S->next->data;
S->next=S->next->next;
}else{
return ;
}
}
void Get_Stack(PStack S,int *e){
if(S->next){
*e=S->next->data;
}else{
return ;
}
}
void Print_Stack(PStack S){
PStack p=S->next;
while(p){
printf("%d ",S->data);
p=p->next;
}
printf("\n");
}
int Match_Stack(PStack S,char ch[]){
int i,e;
for(i=0;i<strlen(ch);i++){
if(ch[i]=='('||ch[i]=='['||ch[i]=='{'){
Push_Stack(S,ch[i]);
}
if(ch[i]==')'||ch[i]==']'||ch[i]=='}'){
if(Empty_Stack(S)==1) return 0;
Get_Stack(S,&e);
switch(ch[i]){
case ')':
if(e!='(')
return 0;
break;
case ']':
if(e!='[')
return 0;
break;
case '}':
if(e!='{')
return 0;
break;
}
Pop_Stack(S,&e);
}
}
if(!Empty_Stack(S)){
return 0;
}
return 1;
}
int main(){
char ch[1000];
PStack S;
while(scanf("%s",&ch)==1){
S=Init_Stack();
if(!Match_Stack(S,ch)){
printf("not match\n");
}else{
printf("match\n");
}
}
return 0;
}2.6.2 运行结果
