《数据结构》第3章-栈与队列的学习总结
我之前有接触过栈和队列，当时就觉得很好奇，那是以怎样的存储结构存储数据的呢？拨开重重迷雾，终于学到基础知识了。
学习《栈和队列》有两个星期了，有了前面两个章节的思维基础，我觉得栈和队列学习起来还是很好理解的，通过一些实际应用例子，让我有了更进一步的理解。现在我梳理一下知识，下面总结这一章我所学习到的东西。
一、栈（后进先出：LIFO）
1、顺序栈
这是顺序栈的存储结构：
typedef struct { int *base;//栈底指针 int *top; //栈顶指针 int size; //栈容量 }SqStack;
开始栈底、栈顶指针都为空，之后随着元素的插入，还有栈的特性（只能在栈顶插入删除），base始终指向栈底位置，而top则加1，指向栈顶元素的上一个。对于顺序栈的基本操作，我觉得跟前面顺序表差不多，只需要在栈顶操作，好像更简单些。
我无意中发现自己现在更喜欢链式存储结构，可能是以前觉得链式比顺序复杂，而学习之后觉得链式更有趣，它的抽象逻辑结构如果捋清楚，就使我豁然开朗，也是这也是一种乐趣吧。
2、链栈
这张图很好表示了链栈的存储结构，老师分析，链栈没必要设头结点，因为在这里对于链栈插入删除，只需要在栈顶操作最方便，初始化时直接将头指针置空就行。
//---------链栈存储结构--定义 typedef struct stacknode { int data; //数据域 struct stacknode *next; // 指针域 }stacknode，*linkstack; 1、初始化 void initstack(linkstack &S) { S=NULL;//构造空栈S.栈顶指针置空 } 2、入栈 void push(linkstack &S,int e) { stacknode p; //定义变量 p=new stacknode;//申请变量空间，生成新结点 p->data=e; //将数据给新结点 p->next=S; //新结点插入栈顶 S=p; //修改栈顶指针为p } 3、出栈 void pop(linkstack &S,int &e) //删除栈顶元素 { if(S==NULL) //判断是否栈空 e=S->data; //栈顶元素数据赋给e p=S; //用p保存栈顶空间，以备释放 S=S->next; // 修改栈顶指针 delete p; //释放原栈顶空间 } 4、取栈顶元素 int gettop(linkstack &S) { if(S!=NULL) return S->data; }
以上这些代码只是各自的算法，我在打的时候也在思考这一句代码的作用是什么，老师也强调注释的重要性，在这个过程中有时就是找出Bug的关键一步，我在自己做题目的时候或者跟同学讨论时确实感受到注释是检查程序的一个工具。
我认为我们老师说的很有道理，一个程序的编写，首先要考虑它的逻辑结构，这也是数据结构这门课的关键，其次是算法，最后是存储结构。
比如，我在做PTA上面括号匹配题目时，开始就明确要用线性结构栈，算法我是参考一下课本案例里面，然后用链式存储结构。
二、队列（先进先出：FIFO）
1、顺序队列（循环队列）
这种循环队列是为了解决“假溢出”，这是由队列特性：队尾入队，队头出队限制造成的，实现操作一个巧妙方法就是（Q.rear+1）%MAXSIZE==Q.front.
2、链队
《银行业务队列简单模拟》那道题，让我对链队有了更深的理解。