栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据，最后一个数据被第一个读出来。栈的一个最重要的特征就是栈的插入和删除只能在栈顶进行，所以每次删除的元素都是最后进栈的元素。理解与临摹
1.1栈的定义
typedef struct CharStack {
int top;
int data[STACK_MAX_SIZE]; //The maximum length is fixed.
} *CharStackPtr;
1.2初始化
CharStackPtr charStackInit() {
CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack));
resultPtr->top = -1;
return resultPtr;
}//Of charStackInit
1.3输出
void outputStack(CharStackPtr paraStack) {
for (int i = 0; i <= paraStack->top; i ++) {
printf("%c ", paraStack->data[i]);
}// Of for i
printf("rn");
}// Of outputStack
1.4压栈（判断栈满，压栈操作）
void push(CharStackPtr paraStackPtr, int paraValue) {
// Step 1. Space check.
if (paraStackPtr->top >= STACK_MAX_SIZE - 1) {
printf("Cannot push element: stack full.rn");
return;
}//Of if
// Step 2. Update the top.
paraStackPtr->top ++;
// Step 3. Push element.
paraStackPtr->data[paraStackPtr->top] = paraValue;
}// Of push
1.5弹栈（判断，操作）
char pop(CharStackPtr paraStackPtr) {
// Step 1. Space check.
if (paraStackPtr->top < 0) {
printf("Cannot pop element: stack empty.rn");
return ' ';
}//Of if
// Step 2. Update the top.
paraStackPtr->top --;
// Step 3. Push element.
return paraStackPtr->data[paraStackPtr->top + 1];
}// Of pop
1.6操作测试
void pushPopTest() {
printf("---- pushPopTest begins. ----rn");
// Initialize.
CharStackPtr tempStack = charStackInit();
printf("After initialization, the stack is: ");
outputStack(tempStack);
// Pop.
for (char ch = 'a'; ch < 'm'; ch ++) {
printf("Pushing %c.rn", ch);
push(tempStack, ch);
outputStack(tempStack);
}//Of for i
// Pop.
for (int i = 0; i < 3; i ++) {
ch = pop(tempStack);
printf("Pop %c.rn", ch);
outputStack(tempStack);
}//Of for i
printf("---- pushPopTest ends. ----rn");
}// Of pushPopTest
1.7结果
1.8理解图示
2.1应用-括号匹配问题。原理同代码基础上直接加一个匹配函数和一个测试函数即可，能使对栈的理解更清晰。
Status bracketMatch(SqStack *S,const char *string){
//输入字符串string中的括号匹配，返回TRUE；否则返回FALSE
const char *p=string;
SElemType e;
InitStack(S);
while(*p!=' '){//遍历字符串
switch(*p){//判断p的值
case '('://左括号，入栈
case '[':
case '{':
Push(S,*p);
//printf("Push %c",*p);
break;
case ')':
if(FALSE==GetTop(*S,&e))
return FALSE;
if(e=='('){
if(ERROR==Pop(S,&e))
return FALSE;
//printf("Push %c",*p);
}else
return FALSE;
break;
case ']':
if(FALSE==GetTop(*S,&e))
return FALSE;
if(e=='['){
if(ERROR==Pop(S,&e))
return FALSE;
//printf("Push %c",*p);
}else
return FALSE;
break;
case '}':
if(FALSE==GetTop(*S,&e))
return FALSE;
if(e=='{'){
if(ERROR==Pop(S,&e))
return FALSE;
//printf("Push %c",*p);
}else
return FALSE;
break;
default:
;
}//switch
p++;
}//while
if(!StackEmpty(*S))//字符串遍历完，栈非空，不匹配
return FALSE;
return TRUE;
}
2.2结果
3.1栈的应用-表达式求值
思路：若遇到’(’ ，直接将’('进栈；
若遇到’)’,一直出栈元素，并将出栈了的元素存入数组newexp中，直至出栈元素为’(’。
若遇到’+‘或’-’，判断运算符栈是否为空，若为空，则直接进栈；若不为空，判断栈顶元素是否为’(’,将不为’(‘的字符全部出栈存于newexp中，再将’+‘或’-‘进运算符栈,如果栈顶元素是’(’，则直接将’+‘或’-'进栈。
若遇到’*‘或’/’,判断运算符栈是否为空，若为空，则直接进栈；若不为空，判断栈顶元素是否为’‘或’/’,若是，则将栈顶元素出栈存于newexp中，再将当前的’‘或’/'存于运算符栈，若不是，直接进栈。
若遇到数字字符，则依次存于newexp中，并用’#'来标识字符串的结束。
当exp扫描结束时，判断运算符栈是否为空，若为空增，则给newtexp表达式添加结束标识，如果不为空，则依次出栈元素存于newtexp表达式中，再给newtexp表达式添加结束标识。
3.2数组和链表的区别
数组必须实现定于固定的长度，不能适应数据动态增减的情况，即数组的⼤⼩⼀旦定义就不能改变。当数据增加是，可能超过原先定义的元素的个数；当数据减少时，造成内存浪费；链表动态进⾏存储分配，可以适应数据动态地增减的情况，且可以⽅便地插⼊、删除数据项。
数组从栈中分配空间（⽤new则在堆上创建），对程序员⽅便快速，但是⾃由度⼩；链表从堆中分配空间，⾃由度⼤但是申请管理⽐较⿇烦。
数组在内存中是连续的存储，因此可以利⽤下标索引进⾏访问；链表是链式存储结构，在访问元素时候只能够通过线性⽅式由前到后顺序的访问，所以访问效率⽐数组要低。
3.3严谨细致，认真理解
