今天学习了数据结构栈和队列。
采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。
若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判断条件定位top等于-1。
#define MAXSIZE 50 //定义栈中元素的最大个数 typedef int ElemType; //ElemType的类型根据实际情况而定，这里假定为int typedef struct{ ElemType data[MAXSIZE]; int top; //用于栈顶指针 }SqStack;
判断栈为空
bool StackEmpty(SqStack S){ if(S.top == -1){ return true; //栈空 }else{ return false; //不空 } }
进栈
/*插入元素e为新的栈顶元素*/ Status Push(SqStack *S, ElemType e){ //满栈 if(S->top == MAXSIZE-1){ return ERROR; } S->top++; //栈顶指针增加一 S->data[S->top] = e; //将新插入元素赋值给栈顶空间 return OK; }
共享栈（两栈共享空间）
（1）共享栈概念
利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空；仅当两个栈顶指针相邻（top0+1=top1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减一再赋值出栈时则刚好相反。
/*两栈共享空间结构*/ #define MAXSIZE 50 //定义栈中元素的最大个数 typedef int ElemType; //ElemType的类型根据实际情况而定，这里假定为int /*两栈共享空间结构*/ typedef struct{ ElemType data[MAXSIZE]; int top0; //栈0栈顶指针 int top1; //栈1栈顶指针 }SqDoubleStack;
三、栈的链式存储结构
采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头节点，Lhead指向栈顶元素，如下图所示。
进栈：
/*插入元素e为新的栈顶元素*/
Status Push(LinkStack *S, ElemType e){
LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode));
p->data = e;
p->next = S->top; //把当前的栈顶元素赋值给新节点的直接后继
S->top = p; //将新的结点S赋值给栈顶指针
S->count++;
return OK;
}
出栈：
/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(LinkStack *S, ElemType *e){
LinkStackPtr p;
if(StackEmpty(*S)){
return ERROR;
}
*e = S->top->data;
p = S->top; //将栈顶结点赋值给p
S->top = S->top->next; //使得栈顶指针下移一位，指向后一结点
free(p); //释放结点p
S->count--;
return OK;
}