0.PTA得分截图
1.本周学习总结（0-4分）
1.1 总结栈和队列内容
栈的存储结构及操作
栈是一种只能在一端进行插入或删除操作的线性表，只能在栈顶进行删除插入操作，是一种先进后出的线性表
typedef struct Stack
{
ElementType *Data; //存储元素的数组
int top; //栈顶指针
}LStsck,*Stack;
栈的操作
大致代码：
栈空条件： top=-1
栈满条件： top=MaxSize-1
进栈e操作：top++; st->data[top]=e
退栈操作： e=st->data[top]; top--;
栈的应用
网络浏览器的浏览记录：用户访问一个新页面，其前一个页面地址会被存放至栈顶，即执行入栈操作；而“后退”按钮，即可沿相反的次序访问此前刚访问过的页面，即执行出栈操作
还有我们学的递归算法，每一次递归都将结果入栈，而后又执行出栈操作，最后得到结果
还有在课堂派里的进制转换，如十进制转为八进制等等，都是先将取余的的数保存进栈中，直到为零时出栈
表达式转换，符号配对，迷宫问题等等
队列的存储结构及操作
队列的存储结构
typedef struct Queue
{
ElementType *Data;//存储元素的数组
int rear,front;//队头队尾指针
}SQueue,*Queue;
操作
大致代码如下
//进队列
int EnQueue(SqQueue& Q, Person e)//加入队列,变换尾指针
{
if (Q->rear == MAXQSIZE) return ERROR;//判断栈是否满
Q->data[Q->rear] = e;
Q->rear++;
return OK;
}
//出队列
int DeQueue(SqQueue& Q, Person& e)//出队列，变换头指针
{
if (Q->front == Q->rear) return ERROR;//判断栈是否空
e = Q->data[Q->front];
Q->front++;
return OK;
}
队列应用
银行排队，以及银行排队的一系列扩展
搭配舞伴问题
还有就是用栈只能找到一条路径的迷宫问题，用队列可以找到多条问题
stack和queue
stack模板类的定义在
stack是链栈，不是顺序栈
stack的基本操作有：
入栈，s1.push(x);
出栈，s1.pop();//出栈操作只是删除栈顶元素，并不返回该元素。
访问栈顶，如例：s1.top()//并不删除该元素
判断栈空，如例：s1.empty()//当栈空时，返回true。
访问栈中的元素个数，如例：s1.size()
queue模板类的定义在
queue是链队列，不是顺序队列
queue的基本操作有：
入队，如例：q1.push(x); 将x接到队列的末端。
出队，如例：q1.pop(); 弹出队列的第一个元素，并不会返回被弹出元素的值。
访问队首元素，如例：q1.front()，即最早被压入队列的元素。
访问队尾元素，如例：q1.back()，即最后被压入队列的元素。
判断队列空，如例：q1.empty()，当队列空时，返回true。
访问队列中的元素个数，q1.size()
循环队列
如图所示，不可以继续添加元素，否则会造成数组越界而遭致程序出错。然而此时又不应该扩充数组，因为还有大量实际空间未被占用。
我们将其实现为循环队列，则很好解决了这个问题
图解如下：
当添加一个元素时,(rear+1)%MAXQSIZE;
当删除一个元素时,(front+1)%MAXQSIZE；
队满时：(Q.rear+1)%MAXSIZE==Q.front
队空时：Q.rear==Q.front
1.2.谈谈你对栈和队列的认识及学习体会。
学习了栈和队列，相比之下还是要好理解一些，操作也更简单一些，主要是有一些库来更好操作，除了有一些难一点的题
这应该就完了线性结构，接下来的非线性结构应该就会更难一些了，得好好加油了！！！
2.PTA实验作业（0-2分）
2.1.题目1：题目名称
7-4 符号配对 (20分)
请编写程序检查C语言源程序中下列符号是否配对：/*与*/、(与)、[与]、{与}。
2.1.1代码截图
2.1.2本题PTA提交列表说明。
部分正确：开头有多余左符号，末尾没加判断栈为空的情况
部分正确：左右符号个数相同，达到最大值，但不匹配；这个我也不知道是啥，试了一下午，都不知道是啥子情况
2.2.题目1：题目名称
7-5 表达式转换 (25分)
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
2.2.1代码截图
2.1.2本题PTA提交列表说明
部分正确：输出时没有将各个符号分开，导致格式错误。以及没有考虑到小数负数的情况，将正负号分别考虑，小数分别考虑就解决了这些问题
部分正确：修改后，显示的负数以及嵌套括号的情况显示错误；而在编译器时，我尝试过多种情况，并没有错误，后面我也会花点时间去解决它，看看是哪里的问题
3.阅读代码（0--4分）
3.1 题目及解题代码
题目：
请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
解题代码：
3.1.1 该题的设计思路
算法时间复杂度O(1)
空间复杂度O(N)
3.1.2 该题的伪代码
void push(stack<int> Stack)
{
输入入栈元素x；
if(min>=x)
判断栈空
将最小值min入栈
将入栈元素x入栈
else 将入栈元素x入栈
}
bool pop(stack<int> Stack)
{
判断栈空
if 栈内元素只有一个
则将最小值= INT_MAX
else if判断最小值是否为栈顶
出栈顶，将最小值等于下一个栈顶
去掉下一个栈顶，即第二小的值
}
3.1.3 运行结果
3.1.4分析该题目解题优势及难点
第一次看到这个题目时，觉得挺简单，但仔细想了想，要在完成题目要求时间复杂度为o（1）的条件下，确实不简单
他解题的优点恰恰是它本题的难点，用栈将它的顺序间接连接起来。
即在最小值的下一个地方放入第二小的值，第二小的值的下一个位置放入第三小的值，以此类推。就解决了o（1）的问题
3.2 题目及解题代码
给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
注意:
nums1和nums2中所有元素是唯一的。
nums1和nums2 的数组大小都不超过1000。
解题代码：
3.2.1 该题的设计思路
算法时间复杂度O(N)
空间复杂度O(N)
3.2.2 该题的伪代码
void DealStack(int nums1[MaxSize], int nums2[MaxSize])//构建栈来处理
{
初始化哈希数组为0；
for遍历nums2
if 栈空或nums2[i]小于栈顶时，将nums2[i]入栈
if nums2[i]大于栈顶时
while（nums2[i]大于栈顶）
写入哈希数组中
将nums2[i]入栈
剩下栈中还有值，全部赋值-1
遍历nums1得出答案
}
3.2.3 运行结果
3.2.4分析该题目解题优势及难点
用以前的数组做的话，复杂度就是n2
而这题用了栈的写法，还结合了哈希数组，大大降低了时间
难点就是难想到用栈的做法，非常巧妙。我做的话肯定就是用暴力来做了