1.栈
定义：是限定仅在表尾进行插入和删除操作的线性表，我们允许插入和删除的一端称为栈顶(top)，另一端称为端底（bottom），（Last In First Out）。
1.2栈的顺序存储
//结构定义
typedef struct {
int data[MAXSIZE];
int top;
}SqStack;
//push
Status Push(SqStack *s,int e){
if(s->top == MAXSIZE -1){
return ERROR;
}
s->top++;
s->data[s->top] = e;
return OK;
}
//pop
Status Pop(SqStack *s,int *e){
if(s->top == -1)
return ERROR;
*e = s->data[s->top];
s->top--;
return OK;
}
//计算栈的长度
int QueueLength(SqQueue Q){
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}z
1.3两栈共享空间
typedef struct{
int data[MAXSIZE];
int top1;
int top2;
}SqDoubleStack;
1.3栈的链式存储
定义：就是用链表实现栈
看栈和队列
栈的应用：
1.递归
2.四则运算表达式求值
后缀表达式计算结果规则： 9 3 1 - 3+ 10 2 / +;
从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到获得结果。
中缀表达式转后缀表达式： “9 + (3 - 1) * 3 + 10 /2” -> “9 3 1 - 3+ 10 2 / +”
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分，若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。
2队列
定义：是只允许在一端进行插入操作，而在另一端进行删除操作的线性表，队列是一种先进先出（First In First Out）,允许插入的一端称为队尾，允许删除的一端称为队头。
循环队列
看栈和队列
链式队列
定义
typedef int QElemType;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front,rear;
}LinkQueue;
入队
Status EnQueue(LinkQueue *Q,QElemType e){
QueuePtr s = (QueuePtr)malloc(sizeof(Qnode));
if(!s){
exit(-1);
}
s->data = e;
s->next = NULL;
Q->rear->next = s;
Q->rear = s;
return Ok;
}
出队
Status DeQueue(LinkQueue *Q,QElemType *e){
QueuePtr p;
if(Q->rear == Q->front){
return ERROR;
}
p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if(Q->rear = =p){
Q->rear = Q->front;
}
free(p);
return Ok;
}
