掌握栈、队列的顺序存储结构和链式存储结构
掌握栈、队列的基本操作在顺序存储结构和链式存储结构上的实现
掌握矩阵的压缩存储
今天核心咱们先把栈搞清楚
栈和队列可以看做是特殊的线性表。它们的特殊性表现在它们的基本运算是线性表运算的子集，它们是运算受限的线性表
栈（Stack）是运算受限的线性表，这种线性表上的插入和删除操作限定在表的一端进行
栈顶：允许插入和删除的一端栈尾：另一端空栈：不含任何数据元素的栈栈顶元素：处于栈顶位置的数据元素
书中的例子比较形象
洗盘子，放盘子，每次只能从这一摞盘子的最上面拿走，这就是栈的基本操作
看重点：栈—>==后进先出（LastInFirstOut）LIFO原则==
所以栈被称作后进先出线性表（后进先出表）
栈的插入和删除运算分为成为进栈和出栈
这里面有两个小知识点在写代码之前需要掌握
空栈做出栈操作，会出现问题，叫做“下溢”满栈做进栈操作，会出现问题，叫做“上溢”
接下来我们就用C语言实现一下
初始化一个空栈
初始化需要动态分配空间，并且需要让top值等于0
判断栈空
//判断栈空intempty(Seqs){printf("判断栈空n");if(s.top==0){return1;}return0;}这个比较简单了，只需要判断s.top值就可以了
进栈操作
//进栈操作Seqpush(Seqs,intx){printf("进栈操作n");//判断栈是否满了if(s.top==maxsize-1){printf("栈满");returns;}else{printf("正在插入数据%dn",x);s.data[s.top]=x;s.top++;returns;}}出栈操作
//出栈操作Seqpop(Seqs,int*e){if(empty(s)){printf("栈空n");exit(0);}else{*e=s.data[s.top-1];s.top--;returns;}}进栈和出栈，这部分内容一定要好好的理解，其实也是比较简单的，就是添加元素和删除元素
打印栈中元素与获取栈顶元素
//打印栈中元素voiddisplay(Seqs){if(empty(s)){printf("栈空n");exit(0);}else{printf("开始打印n");intnum=0;while(num intmain(){printf("代码运行中n");Seqs;s=init(s);//插入两个元素s=push(s,1);s=push(s,2);display(s);inte;s=pop(s,&e);printf("删除的元素是:%dn",e);display(s);return0;}双栈书中还提到了双栈，不过这个不是重点了，你要知道的是，双栈的两个栈底分别设置在数组的两端，栈顶分为是top1,top2 两个栈顶在中间相遇，条件为（top1+1=top2）发生上溢 判断栈空条件呢？一个是top=0另一个是top=maxsize-1这个要注意一下即可 栈的链接实现称为链栈。链栈可以用带头结点的单链表来实现，链栈不用预先考虑容量的大小 链栈将链表头部作为栈顶的一端，可以避免在实现数据“入栈”和“出栈”操作时做大量遍历链表的耗时操作 链表的头部作为栈顶，有如下的好处 结论：链表实际上就是一个只能采用头插法插入或删除的链表 例子：将元素1，2，3，4依次入栈，等价于将各元素采用头插法依次添加到链表中 完整代码如下 由于比较简单，直接贴上了 #include#includetypedefstructnode{intdata;//数据域structnode*next;//链域}LkStk;//初始化voidinit(LkStk*ls){printf("初始化操作n");ls=(LkStk*)malloc(sizeof(LkStk));ls->next=NULL;}//进栈voidpush(LkStk*ls,intx){printf("进栈操作n");LkStk*temp;temp=(LkStk*)malloc(sizeof(LkStk));//给temp新申请一块空间temp->data=x;temp->next=ls->next;ls->next=temp;printf("%d进栈成功n",x);}intempty(LkStk*ls){if(ls->next==NULL){return1;}elsereturn0;}//出栈intpop(LkStk*ls){LkStk*temp;//判断栈是否为空if(!empty(ls)){temp=ls->next;//准备出栈的元素指向ls的下一结点ls->next=temp->next;//原栈顶的下一个结点称为新的栈顶printf("栈顶元素：%dn",temp->data);free(temp);//释放原栈顶的结点空间return1;}return0;}intmain(){LkStkls;init(&ls);push(&ls,1);push(&ls,2);pop(&ls);pop(&ls);return0;}这就是链栈的基本进栈和出栈了，当然，我们还可以获取一下栈顶元素 在自考或者期末考试中，容易出现的一种题是手写入栈和出栈例如 设一个链栈的输入序列为A、B、C，试写出所得到的所有可能的输出序列，即输出出栈操作的数据元素序列 写答案的时候，记住先进后出原则 从A开始写A进，A出，B进，B出，C进，C出A进，B进，B出，C进，C出，A出……继续写下去就可以了，一定不要出现A进，B进，B出，C进，A出注意，A出不去，A前面有C呢 在来一个例题 这个就是把A开头和B开头的都写出来 主要仔细，就能写对，套路就是，先进后出 栈是只能在一端（栈顶）进行插入和删除运算的线性表，具有后进先出特征。 以顺序存储结构实现的栈称为顺序栈，以链式存储结构实现的栈称为链栈。 顺序栈需要预先定义栈的大小，在难以估计栈的大小时，可以采用链栈，链栈是用单链表实现。一般地，将栈顶设在链表的表头一端，栈底设置在链表的表尾。栈适合与具有后进先出特征的问题。