栈和队列代码

栈的顺序存储结构：

typedef struct stack{int*a;int top; int capacity;
}ST;

栈的初始化：

//每一次扩容需要增加四个
void initstack(ST*ps){assert(ps);ps->a=(int*)malloc(sizeof(int)*4);if(ps->a==NULL){printf(“fail”);exit(-1);
}ps->capacity==4;ps->top=0;}

入栈：

//入栈操作
void stackpush(ST*ps,int e){assert(ps);//判断是否已经满了if(ps->top==ps->capacity){//把原来的空间增加为两倍int*tmp=(int*)realloc(ps->a,sizeof(int)*2*ps->capacity);if(tmp==NULL){printf("fail");exit(-1);}else{ps->a=tmp;ps->capacity*=2;}}
ps->a[ps->top]=e;
ps->top++;}

出栈：

//出栈按照先进后出原则
//assert判断指针是否为空如果为空就暂停
void stackpop(ST*ps){assert(ps);assert(ps->top>0);ps->top--;}

栈的链式存储结构：

//节点代码
typedef struct stacknode{int data;struct stacknode*next;//指向下一个节点的指针}s;
typedef struct stack{stack*top;  //指向栈顶的指针};

入栈：

void push(Stack* stack, int data) {  //入栈相当于要有一个新节点s*newnode=(int*)malloc(sizeof(s));newnode->data=data;  //添加的新数据给到新节点指向的datanewnode->nex=stack->top; //新节点的指向的下一个位置为原来栈顶的指针stack->top=newnode;  //新节点成为栈顶}

案例：有效的括号！！20. 有效的括号 - 力扣（LeetCode）

队列结构与栈相似，只不过是先进先出：

typedef struct node{int data;struct node*next;
}q;
typedef struct queue{q*head; //头指针q*tail;  //尾指针
}qu;

为什么要设立头指针、尾指针呢？

头指针用于头出队列：

void queuepop (qu*r){assert(r);q*h =r->head->next //把头节点指针给一个指针暂存int*e=h->data  //头结点的数据暂存r->head->next=h->next;  //r->head->next= r->head->next->next;  但是这样就无法free了free(h);}

尾指针用于尾插操作：

void queuepush(qu*r,int e){assert(r);
//节点插入都需要扩容节点q*s=(q*)malloc(sizeof(q*)); if(s==NULL){exit(-1);}r->tail->next=s;s->data=e;s->next=NULL;r->tail=s;}

通过这两段代码来理解为什么用两个指针，本质上就是为了进行插入和删除本质上就是增删查改这一套。