当你用浏览器上网时，不管什么浏览器都有一个“后退”键，你点击后可以按访问顺序的逆序加载浏览过的网页。即使你从一个网页开始，连续点了几十个链接跳转，你点“后退”时，还是可以像历史倒退一样，回到之前浏览过的某个页面。又或者你在word里面快乐地写论文的时候，一不小心将一整段内容删除了，这个时候不要慌，我们可以点Ctrl+z,撤销之前的删除操作。这就是栈在现实生活之中的应用栈是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的找称为空栈。栈是一种后进先出的线性表。
既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们将其简称为顺序栈。
/*插入元素e为新的栈顶元素*/StatusPush(SqStack*S,SElemTypee){if(S->top==MAXSIZE-1)/*栈满*/{returnERROR;}S->top++; /*栈顶指针增加一*/S->data[S->top]=e;/*将新插入元素赋值给栈顶空间*/returnOK;}（2）顺序栈的出栈操作：进栈是先自增再赋值，出栈则反过来。先把要出栈的元素获取到，然后再指针自减，把空间释放出来。
/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/StatusPop(SqStack*S,SElemType*e){if(S->top==-1)returnERROR;*e=S->data[S->top]; /*将要删除的栈顶元素赋值给e*/S->top--; /*栈顶指针减一*/returnOK;}（2）顺序栈的其他操作：
/*构造一个空栈S*/StatusInitStack(SqStack*S){/*S.data=(SElemType*)malloc(MAXSIZE*sizeof(SElemType));*/S->top=-1;returnOK;}/*顺序栈的遍历：从栈底到栈顶依次对栈中每个元素显示*/StatusStackTraverse(SqStackS){inti;i=0;while(i<=S.top){visit(S.data[i++]);}printf("\n");returnOK;}Statusvisit(SElemTypec){printf("%d",c);returnOK;}/*在栈不空的情况下返回栈顶元素并出栈*/StatusPop(SqStack*S,SElemType*e){if(S->top==-1)returnERROR;*e=S->data[S->top]; /*将要删除的栈顶元素赋值给e*/S->top--; /*栈顶指针减一*/returnOK;}（2）链栈:链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。对于链栈来说，一般情况下基本不存在栈满的情况。链栈为空的判断的条件是top=NULL；链栈的结构体定义如下：
typedefintStatus;/*SElemType类型根据实际情况而定，这里假设为int*/typedefintSElemType;/*链栈结构*/typedefstructStackNode{SElemTypedata;structStackNode*next;}StackNode,*LinkStackPtr;typedefstruct{LinkStackPtrtop;intcount;}LinkStack;链栈的操作与对链表的操作基本相同。
/*链栈的进栈操作*/StatusPush(LinkStack*S,SElemTypee){LinkStackPtrs=(LinkStackPtr)malloc(sizeof(StackNode));s->data=e;s->next=S->top; /*把当前的栈顶元素赋值给新结点的直接后继，见图中①*/S->top=s;/*将新的结点s赋值给栈顶指针，见图中②*/S->count++;returnOK;}/*出栈操作*/StatusPop(LinkStack*S,SElemType*e){LinkStackPtrp;if(StackEmpty(*S))returnERROR;*e=S->top->data;p=S->top; /*将栈顶结点赋值给p，见图中①*/S->top=S->top->next;/*使得栈顶指针下移一位，指向后一结点，见图中②*/free(p);/*释放结点p*/S->count--;returnOK;}1.1.2队列：在日常生活中，我们使用电脑的时候。机器有时会处于疑似死机的状态，鼠标怎么点都没用，双击任何快捷方式都不动弹。就当你失去耐心，打算重启时，突然它能动了，把你刚才点击的所有操作全部都按顺序执行了一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出，而按先后次序排队等待造成的。这就是队列。队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
线性表分为顺序存储和链式存储，栈是线性表，所以也有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。我们一直都是用数组来实现顺序存储的，顺序队列也不例外。所以我们可以定义一个数组intdata[MAXSIZE]来存储队列的元素。另外，我们还需要两个指针，来标记队头和队尾，所以定义如下：
*QElemType类型根据实际情况而定，这里假设为int*/typedefintQElemType;/*循环队列的顺序存储结构*/typedefstruct{ QElemTypedata[MAXSIZE]; intfront; /*头指针*/ intrear; /*尾指针，若队列不空，指向队列尾元素的下一个位置*/}SqQueue;如果队不满，我们就可以入队了。入队的思路就是，先给队尾元素赋值，然后再将队尾指针向后移动一位。比如从空队列开始，此时Q->front==Q->rear，这个时候插入元素的话，其实就是给data[Q->rear]赋值e，然后队尾指针Q->rear向后移动一位重新赋值。虽然我们在定义队列的时候没这个长度变量，但是我们可以通过模计算来取得我们需要的。将队尾指针向后移动一位？很简单，Q->rear=(Q->rear+1)%MAXSIZE;即可。
/*QElemType类型根据实际情况而定，这里假设为int*/typedefintQElemType;typedefstructQNode /*结点结构*/{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct /*队列的链表结构*/{QueuePtrfront,rear;/*队头、队尾指针*/}LinkQueue;链队的操作，入队出队，大致思路：（1）我们先创建一个结点s，QueuePtrs=(QueuePtr)malloc(sizeof(QNode));（2）然后给s的data域赋值e，指针域next赋值null。s->data=e;s->next=NULL;目的就是让它成为新任队尾元素。（3）前任队尾元素直接让它的指针域指向s就行了。Q->rear->next=s;（4）别忘了把队尾指针重新指向新任队尾s。Q->rear=s;代码如下：
（1）如图中，要删除掉a1结点，思路很简单，就是让头结点Q->front的后继next直接指向a2。但是a2如何标识呢？（2）假设a1结点为p结点，那么a2就是p->next了。如何让a1结点存到p呢？（3）直接让头结点的后继指向p就行，p=Q->front->next;（4）假如队尾已经是p结点的话（Q->rear==p），队尾指针需要指向头结点Q->rear=Q->front;（5）最后别忘了把pfree掉。
/*若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/StatusDeQueue(LinkQueue*Q,QElemType*e){ QueuePtrp; if(Q->front==Q->rear) returnERROR; p=Q->front->next; /*将欲删除的队头结点暂存给p*/ *e=p->data; /*将欲删除的队头结点的值赋值给e*/ Q->front->next=p->next;/*将原队头结点的后继p->next赋值给头结点后继*/ if(Q->rear==p) /*若队头就是队尾，则删除后将rear指向头结点*/ Q->rear=Q->front; free(p); returnOK;}1.2.谈谈你对栈和队列的认识及学习体会。学习栈与链表的时候感觉这两个概念好懂，但是真正做题的时候又十分地抽象，题目通常很长，需要利用栈和容器地性质才能很好的解决问题。所以，这一部分的习题做的不是太好。开学已经近6周了，总是觉得自己的状态不怎么良好。线上教学确实能比现实中上课听得清楚，但是自己需要抵制各种诱惑。还有，最近代码量有点少，所以看见题目会有一种无从下手的感觉。在家确实没有学校氛围好，自己会懈怠的。总而言之，还是看自己，不能步步都跟不上不是吗？努力吧！
选2道PTA题目，不写伪代码，只贴代码截图，并记录代码提交碰到问题及解决方法。不得选栈或队列操作（选，则为0分）选择难度越高题目得分越高。
Q:多种错误；A:开始按着自己的思路写了下来，输出时的格式不正确，导致错误；Q部分正确:A:这次提交过了两个测试点。由于我没有调用函数，直接在main()里面实现，所以代码重复的地方多；当输入的字符串是匹配的时候，可以输出”yes”;但是当栈内仍然存在元素（如测试点”[{“）,也会输出”yes”;所以另外加了一个判断条件，判断循环结束时栈是否为空；Q:部分正确；A:起初先判断flag值是否进行了变通，再判断栈是否为空。这样子做，如果flag值被改变，栈为空，那么即会输出yes,也会输出no。所以，将栈空判断放在前面就会解决这个问题。
Q:答案错误；A:开始的时候没看懂题目的意思，以为m%3==1的情况下才进行输出，所以第一次答案错误。在调试中发现了这个问题，所以没有提交；Q:部分正确；A:格式不符合导致的错误。题目要求每一个数字之间要有空格隔开，结尾不能留空格。所以要控制一下输出格式。因为我用的是链队，所以不方便对队尾数字进行操作，所以对第一个数字进行格式控制。刚开始改的时候没有注意第一个数字也要出队，导致输出的数据多了一个。不要忘记判断m与n的大小，m>n时要直接报错。
/*官方解题代码*/voidhanota(vector
函数中涉及到的c++知识（1）pair