DS博客作业02--栈和队列

0.PTA得分截图

1.本周学习总结

1.1 栈和队列学习内容

1.1.1栈的存储结构及操作

1.1.1.1栈的存储结构

顺序栈

  • 抽象图示
typedef struct SNode
{
   int data[MaxSize];
   int top;      //栈顶指针（并非指针类型变量，因为该int变量指向栈顶，抽象描述为指针）
}*stack;
stack *st;  //定义了顺序栈st

说明：顺序栈的数据都由事先申请好的数组空间来存储。

  • 链栈
    抽象图示
typedef struct SNode
{
   ElemType data;
   struct SNode *next;
}SNode,*LinKStack;
**说明**：链式栈的定义和单链表的定义相同，不过操作只能在栈顶（头节点的下一个节点）进行，数据节点（栈的内容）可即用即生成。

1.1.1.2栈的基本操作

出栈

  • 顺序栈
e=st->data[st->top];    //存储出栈数据
st->top--;         //栈顶下降
  • 链式栈
e=st->next->data;    //存储出栈数据
temp=st->next;
st->next=st->next->next;
delste temp;      //释放出栈数据的地址占用

进栈

  • 顺序栈
st->top++;
st->data[st->top]=x;  //x为进栈数据
  • 链式栈
node=new SNode;
node->data=x;     //x为进栈数据
node->next=st->next;
st->next=node;

判断栈满

  • 顺序栈
st->top=MaxSize-1
  • 链式栈
    链式栈一般没有栈满情况（由于链表节点地址可以一直申请）
    栈空判断
  • 顺序栈
st->top=0
  • 链式栈
st->next=NULL

1.1.1.3另类栈（共享栈）

抽象图示

1.1.2栈的应用

1.1.2.1查找迷宫

1.1.2.2网页浏览

我们使用两个栈，X和Y，首次浏览的页面，依次压入栈X。当点击回退时，依次从X栈中取出数据，并依次放入Y栈。点击前进时，从Y栈中取出数据，并依次放入X栈。当X栈中没有数据时，就说明不能再回退了；当Y中没有数据时，就说明不能再前进了。
比如你依次浏览了a b c 三个页面，我们依次把 a b c 压入栈，这时两个栈是这个样子

浏览器通过后退按钮，回退到页面 a 时，我们把 c b 依次压入Y栈，这时两个栈是这个样子

这时候，你又通过前进按钮，又回到 b 页面，这时两个栈的数据是这个样子

这时，你由 b 页面打开新的页面 d，那么你就不能再通过后退回到 c 页面，Y栈数据要清空。这时两个栈是这个样子

1.1.3队列的存储结构及操作

1.1.3.1队列的存储结构

顺序队列

  • 抽象图示
typedef struct
{
   int data[MaxSize];
   int front;    //队头指针
   int rear;    //队尾指针
}queue,SqQueue;

说明：顺序队列的数据都由事先申请好的数组空间来存储。
链队列

  • 抽象图示
typedef struct QNode   //定义数据节点结构体
{
   int data;
   struct QNode *next;
}Queue,*QueuePtr;

typedef struct    //定义存储队头队尾指针的结构体
{
   QueuePtr front;
   QueuePtr rear;
}*LinkQueue;

说明：链队列的定义和单链表的定义相同，不过需要再定义一个辅助结构体变量来存放队头和队尾指针，存储空间可以凭需要申请。

1.1.3.2队列的基本操作

出队列

  • 顺序队列
Q->front++;
e=Q->data[Q->front];
  • 链队列
e=Q.front->data;  //存出队数据
temp=Q.front->next;
Q.front->next=temp->next;;
delete temp;

进队列

  • 顺序队列
Q->rear++;
Q->data[Q->rear]==x;
  • 链队列
SqQueue Node=new Queue;
Node->data=x;   //x为入队数据
Q.rear->next=Node;
Q.rear=Q.rear->next;
Q.rear->next=NULL;

对空判断

  • 顺序队列
Q->rear=Q->front;
  • 链队列
Q.front=Q.rear;

队满判断

  • 顺序队列
Q->rear=MaxSize-1;
  • 链队列
    一般没有队满情况，因为其可以随需要申请节点存放队列数据

1.1.3.3循环队列

抽象图示

相关操作和判断

  • 进队
Q->rear=(Q->rear+1)%MaxSize;
Q->data[Q->rear]=x;
  • 出队
Q->front=(Q->front+1)%MaxSize;
  • 优点（相较于普通的顺序队列）：由于普通队列front=rear=MaxSize-1时明明还要位置可排，但因为我们队满的判断条件rear=MsxSize-1达到确无法再排，运用循环队列来储存便没有这个问题出现，不会让空间得到浪费。

1.2学习体会

在学习栈和队列这章内容时，明显感觉到比前段时间学习链表时容易接受，容易理解，也没有那么抽象了。不过相较于链表，栈和队列的学习过程中，也要熟记许多内容，如出入栈，出入队列的操作语句，初始化栈和队列的操作语句，指针的移动和满空的判断语句，需要通过代码量来巩固这些知识。在学习过程中和代码练习的过程中要多加注意某些特殊情况。还有一点我让我很受用的便是stl容器的学习，map，queue，stack，它们可以简便我们的代码和操作，需要去多使用它们才能印象深刻。

2.PTA实验作业

2.1.题目1：7-8 电路布线

2.1.1代码截图

2.1.2PTA提交列表说明


Q1:代码在VS上面运行超时了
A1:仔细检查发现，题给信息是将值为0的点当作未铺线的点，而我却在代码里弄反了，便逐一修改。
Q2:代码在VS上面运行还是无结果，中途会跳出运行，我便将代码提交PTA一试，出现段错误。
A2:算法中从一个点出发，上下左右寻找可走路径，我发现往一个方向走后忘记复原，例如我走左后本应该回到原来的位置再走右边，而我却在走左的基础上走右边。
未修改前

修改后

2.2 题目2：6-5 舞伴问题

2.2.1代码截图

2.2.2PTA提交列表及说明




Q1:写完代码提交显示运行超时。
A1:首先我的配对函数里面建了一个单链表，每个节点存放一对配对男女。后来发现输出配对结果的时候（遍历链表输出数据），代码中前驱指针忘了pre=pre->next，导致前驱指针无法指向下一个节点，造成死循环，补上后问题得到解决。
Q2:解决问题一后提交代码，发现只过了一个测试点：全部正好配对。题目要求在男或者女有剩余的情况下输出剩余个数（主函数中输出），而我的代码运行无法输出。
A2:
在这里先介绍一下我的代码：
我观察了题给主函数的代码，里面有男女队列的初始化

配对函数的运行

我发现配对函数的参数中并没有男女队列的存在，我就想到便无法利用男女队列进行配对。
于是我自作聪明，在配对函数里面又建了男女队列

所以问题就来，由于是函数内队列，那么队列本身和所作的队列头尾指针的移动在函数运行后都会销毁，所以无法根据队列头尾指针的位置判断配对后剩余人数。
认真重审题目发现，题目已经给出的男女队列是全局变量，也就是无需作为参数传递便可以使用。修改后正确。

3.阅读代码（0--4分）

找2份优秀代码，理解代码功能，并讲出你所选代码优点及可以学习地方。主要找以下类型代码：
考研题
PTA赛题目，可以自己做法，实现 不了也可以找题解研究。题目放2019-ds-难题集中.
ACM题解
leecode--栈
leecode--队列
注意：不能选教师布置在PTA的题目。完成内容如下。
3.1 题目及解题代码
可截图，或复制代码，需要用代码符号渲染。题目截图后一定要清晰。
3.1.1 该题的设计思路
链表题目，请用图形方式展示解决方法。同时分析该题的算法时间复杂度和空间复杂度。
3.1.2 该题的伪代码
文字+代码简要介绍本题思路
3.1.3 运行结果
网上题解给的答案不一定能跑，请把代码复制自己运行完成，并截图。
3.1.4分析该题目解题优势及难点。
评分注意
本学期，博客作业重点会在知识总结及代码阅读内容。代码阅读部分务必按照要求详细介绍解题思路。回答简单应付，博客书写没有看出作者对代码理解，则得0分。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/243050cz/p/12548064.html