顺序表，链表的有点和缺点

链表

优点：
1、任意位置插入删除，时间复杂度位O(1)
2、按需申请释放空间
缺点：
1、不支持下标的随机访问
2、CPU的高速缓存命中率更低

顺序表

优点:
1、支持下标的随机访问
2、尾插尾删的时间复杂度位O(1)
3、CPU高速缓存的命中率更高
缺点：
1、前面部分插入删除数据，时间复杂度位O（N），需要挪动数据
2、空间不够，需要扩容
a、扩容是需要付出代价的
b、一般还会伴随空间浪费

这里的命中率涉及到了计算机组成原理的存储器的内容。大家可以去看看。

栈和队列

栈的概念：栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。
后进先出，先进后出

栈的实现

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
//定义栈的类型
typedef int STDataType;typedef struct stack
{STDataType* a;int top;int capacity;
}ST;//函数接口的声明
void STInit(ST* pst);
void STDestory(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);
STDataType STTop(ST* pst);

在对栈初始化时我们需要考虑top的值初始化为多少，如果初始化为-1指向的就是栈顶的元素，初始化为0指向的就是栈顶元素的下一个位置。
栈的接口实现：

#include "Stack.h"
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = pst->top = 0;
}
void STDestory(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;
}
void STPush(ST* pst, STDataType x)
{assert(pst);//考虑扩容if (pst->capacity == pst->top){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//当a为空指针时，realloc的作用和malloc的作用一样STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp==NULL){perror("realloc failed");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top++] = x;
}
void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst->top--;
}
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}
int STSize(ST* pst)
{assert(pst);return pst->top;
}
STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst->a[(pst->top) - 1];
}

队列的概念：和栈相反，队列是一种先进先出的的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中允许插入的一端叫做队尾，允许删除的一端则称为队头

栈的应用（括号匹配问题）

解题思路，我们可以使左括号进栈，遇到右括号时出左括号，如果不匹配返回false，如果括号序列结束了，栈中还有括号，那么说明括号不匹配，返回false，如果只有右括号，此时栈中为空，不能出栈，说明括号不匹配，直接返回false。
leetcode做题链接
具体代码如下：

bool isValid(char * s){//首先初始化一个栈ST st;//初始化栈STInit(&st);while(*s){//遇到左括号进栈if(*s=='('||*s=='{'||*s=='['){STPush(&st,*s);}else   //遇到右括号，退栈{//如果此时的栈为空，即没有左括号，括号不匹配，返回falseif(STEmpty(&st)){STDestory(&st);return false;}char top = STTop(&st);STPop(&st);if((top=='('&&*s!=')')||(top=='{'&&*s!='}')||(top=='['&&*s!=']')){STDestory(&st);return false;}} s++;}//销毁栈bool ret = STEmpty(&st);STDestory(&st);if(ret){STDestory(&st);return true;}return false;
}