0.PTA得分
1.本周学习总结
1.1栈
顺序栈的结构、操作函数
0.顺序栈的结构体定义
typedef struct{
ElemType data[MAXSIZE];
int top;
}Stack,*SqStack;
1.进栈操作
bool Push (SqStack &s,ElemType e)
{
if(S-top==MAXSIZE-1)
{
return false;//栈满返回false
}
s->top++;
s->data[s->top]=e;
retrun true;
}
2.取栈顶元素操作
bool Get top(SqStack &s,ElemType &e)
{
if(s->top==-1)
return false;//栈空返回false
e=s->data[s->top];
return true;
}
3.出栈操作
bool Pop(SqStack &s,ElemType &e)
{
if(s->top==-1)
return false;//栈空返回false
e=s->data[s->top];
s->top--;
return true;
}
链栈的结构、操作函数
0.链栈结构体定义
typedef struct linkstack
{
ElemType data;
struct linkstack *next;
}StStack,*LinkStack;
1.进栈操作
bool Push(LinkStack &S, int e) //在栈顶插入元素e
{
LinkStack p;
p = new Snode; //生成新结点
p->data = e; //将e放在新结点数据域
p->next = S; //将新结点的指针域指向S
S = p; //修改栈顶指针为p
return true;
}
2.取栈顶元素
int GetTop(LinkStack S) //返回S的栈顶元素
{
if (S != NULL)
return S->data; //返回栈顶元素的值
else
return -1;
}
3.出栈
bool Pop(LinkStack &S, int &e)
{
LinkStack p;
if (S == NULL)
return false;
e = S->data;
p = S;
S = S->next;
delete p; //释放原栈顶元素的空间
return true;
}
1.2栈的应用
1.输入之后逆序输出
2.语法检查：括号匹配
每当扫描到大中小的括号后，令其进栈，当扫描到右括号时，则检查栈顶是否为相应的左括号，若是，则出栈处理，若不是，则出现了语法错误。当扫描到文件结尾，若栈为空则表明没有发现括号配对错误。
1.3队列
顺序队列的结构、操作函数
0.队列的定义
typedef struct Squeue
{
DataType queue[QueueSize];
int front, rear;
}SeqQueue;
1.入列
bool EnQueue(SeqQueue *S, DataType e)
{
if (S->front==(S->rear+1)%QueueSize)
{
return false;
}
S->rear ++;
S->queue[S->rear] = e;
return true;
}
2.出列
bool DeQueue(SeqQueue *S, DataType &e)
{
if (S->front==S->rear)
{
return false;
}
else
{
S->front++;
e = S->queue[S->front];
return true;
}
}
3.判断队列是否为空
bool QueueEmpty(SeqQueue *S)
{
if (S->front==S->rear)
{
return false;
}
else
{
return true;
}
}
链队列的结构、操作函数
0.定义
typedef int QElemType;
typedef struct QNode
{
QElemType data;
struct QNode *_pNext;
}QNode;
typedef struct LQueue
{
QNode *pFront;
QNode *pRear;
}LQueue;
1.入列
void enQueue(LQueue*&q,QElemType data)
{
Qnode*p;
p=(Qnode*)malloc(sizeof(Qnode));
p->data=data;
p->_pNext=NULL;
if(q->pRear==NULL)
q->ppFront=q->pRear=p;//若队列为空，新节点是头又是尾
else
{
q->pRear->_pNext=p;
q->pRear=p;
}
}
3.出列
bool deQueue(LQueue*&q,QElemType &data)
{
Qnode *t;
if(q->pRear==NULL)
{
return false;
}
t=q->pFront;
if(q->pFront==q->pRear)
{
q->pFront=q->pRear=NULL;
}
else
q->pFront=q->pFront->next;
data=t->data;
free(t);
return true;
}
3.判断队列是否为空
bool Emptyqueue(LQueue *q)
{
return(q->pRear==NULL);
}
1.3队列的应用
队列是一种常见的数据结构，主要的特性先进来的元素会先出去，所以适合具有这个特性的算法来使用，比如图的广度优先搜索、二叉树的层次遍历等。
所以队列和生活中的排队非常相似，先来的先服务，后来的后服务。
2.PTA实验作业
2.1符号配对
2.1.1 解题思路：
将字符一个一个处理，发现一个要处理的左符号“[,(,{”就入栈，发现一个需要处理的右符号“],),}”就与栈顶对比。
如果是对应的左符号，那么把栈顶弹出，否则说明这个右符号不能配对，输出NO等信息并退出。如果一直处理到程序结尾都没有退出就是YES。
2.1.2 总结解题所用的知识点
stack库的操作
2.2 银行业务队列简单模拟
2.2.1解题思路：
模拟队列，将偶数的数字存到b窗口，将奇数的数字存到a窗口，而且是先进先出，所以可以采用队列，将偶数的放在b队列，将奇数的放在a队列；然后每输出两个a队列中的元素，再输出一个b队列中的元素；
2.2.2总结解题所用的知识点
queue库的操作
3.阅读代码
3.1题目及解题代码
int *dailyTemperatures(int *T, int TSize, int *returnSize)
{
int *monoStack = (int *)malloc(sizeof(int) * TSize);
memset(monoStack, 0, sizeof(int) * TSize);
int stackTop = -1;
int tIter = 0;
int *res = (int *)malloc(sizeof(int) * TSize);
memset(res, 0, sizeof(int) * TSize);
while (tIter < TSize) {
/* monoStack[stackTop]是栈顶元素在T中的下标，T[monoStack[stackTop]] 才是真正的栈顶温度 */
while (stackTop != -1 && T[monoStack[stackTop]] < T[tIter]) {
int r = monoStack[stackTop];
stackTop--;
res[r] = tIter - r;
}
monoStack[++stackTop] = tIter++;
}
*returnSize = TSize;
return res;
}
3.2 该题的设计思路
1.构造一个单调递减栈，当遇到比栈顶元素大的温度，就要考虑出栈
2.单调栈中，存入的是每日温度的下标，当发现更高的温度时，栈顶元素monoStack[stackTop]和当前元素下标tIter相减，即为天数差
3.3该题目解题优势及难点
运用了单调栈的套路