| 这个作业属于哪个班级 | 数据结构--网络2011/2012 |
|---|---|
| 这个作业的地址 | DS博客作业02--栈和队列 |
| 这个作业的目标 | 学习栈和队列的结构设计及运算操作 |
| 姓名 | 曹卉潼 |
0.PTA得分截图
1.本周学习总结（0-5分）
1.1 栈
1.1.1顺序栈
顺序栈的结构体定义：
/* 存储空间初始分配量 */
#define MAXSIZE 20
/* SElemType类型根据实际情况而定，这里假设为int */
typedef int SElemType;
/* 顺序栈结构 */
typedef struct
{
SElemType data[MAXSIZE];
int top; /* 用于栈顶指针 */
}SqStack;
顺序栈的基本操作：
- 初始化栈
/*顺序栈*/
void InitStack(SNode &s)
{
s.top=-1;//一般的顺序表栈顶指针的初始化为-1,
}
- 判断是否为空栈
/*顺序栈*/
bool IsEmpty(SNode s)//如果为空返回true，不为空则返回false；
{
if(s.top==-1)
return true;
else
return false;
}
- 判断是否栈满
对于顺序栈来说，是用数组来保存数据，因为数组在被定义时就需要预先申请一段连续的空间，所以如果我们要往里面进行插入的操作，必须要先判断该栈是否已经满了，否则就会出现数组溢出，访问错误的情况。
/*顺序栈*/
bool IsFull(sNode s)
{
if(s.top==MaxSize-1)
return true;
else
return false;
}
- 进栈
对栈的一端进行插入。
bool Push(SNode &s,Elemtype e)
{
if(IsFull(s))//在进栈之前一定要先判断是否栈满
return false;
else
s.data[++s.top] = e;
return true;//说明进栈成功；
}
- 取栈顶
取得栈顶元素
/*顺序栈*/
bool Gettop(SNode &s, Elemtype &e)
{
if(IsEmpty(s))//取栈顶时要判断是否为空栈！
return false;
else
e = s.data[s.top];
return true ;
}
- 出栈
/*顺序栈*/
bool Pop(SNode &s，Elemtype &e)//出栈并返回该栈顶元素；
{
if(IsEmpty(s))//在出栈之前一定要判断是否为空栈
return false ;
else
e = s.data[s.top--];//这里只是移动了栈顶指针，并没有真正的删除数据；
return true;//出栈成功；
}
- 销毁栈
将栈顶元素删除，并移动栈顶指针。
void DestroyStack(SNode &s)
{
delete s;
}
1.1.2链栈
链栈的结构体定义：
typedef struct stack
{
Elemtype data;
struct stack* next;
}SNode,*Stack;
链栈的基本操作：
- 初始化栈
/*链栈*/
void InitStack(Stack &s)
{
s = new SNode;//申请空间；
s->next=NULL;
}
- 判断是否为空栈
/*链栈*/
bool IsEmpty(Stack s)//如果为空返回true，不为空则返回false；
{
if(s->next==NULL)
return true;
else
return false;
- 判断是否栈满
因为是链式存储结构，不用预先设定需要多少的存储空间来保存数据，都是现用现配，空间利用效率比较高。所以只要一个数据我们就可以直接进栈，不必考虑是否会栈满。
- 进栈
void Push(Stack &s,Elemtype e)//使用头插法；
{
Stack str;
str=new Stack;
str->data = e;
str->next= s->next;//先将原来的链栈连接到str后面；
s->next = str;//再将str连接到头结点后面成为新的栈顶；
}
- 出栈
/*链栈*/
void Pop(Stack & s,Elemtype &e)
{
Stack str;
if(IsEmpty(s))//出栈之前要判断是否为空栈；
return false;
else
{
e = s->next->data;
str = s->next;
s->next = str->next;//让头结点连接栈顶的下一个结点，使s->next->next成为新的栈顶；
delete str;//释放空间，这里数据是真的被删除
}
}
- 取栈顶
bool Gettop(Stack &s,Elemtype &e)
{
if(IsEmpty(s))//取栈顶时要判断是否为空栈！
return false;
else
e = s->next->data;
return true;
}
- 销毁栈
/*链栈*/
void DestroyStack(Stack &s)
{
ListStack str;
while(s!=NULL)
{
str = s;//str保存当前删除的结点
s = s->next;//s指向下一个需要删除的结点；
delete str;
}
}
1.1.3 C++类模板：stack
头文件 #include <stack>
stack <Elemtype> s;初始化栈，保存Elemtype类型的数据；
s.push(x);入栈元素t；
s.top();返回栈顶指针；
s.pop();出栈操作，只做删除栈顶元素的操作，不返回该删除元素；
s.empty();判断是否栈空，如果为空返回true;
s.size();返回栈中元素个数；
1.2 栈的应用
表达式转换
运算符在操作数中间，这种表达式叫做中缀表达式，如果计算机要跳过数据去判断所有运算符的优先级，再按顺序取运算符两边的数据进行运算的话，对计算机来说工作量是很大的。于是如果我们能把运算符的优先级先排好，然后直接取该运算符的前两个数据运算，这样就使得运算变的简便起来。像这样 运算符位于两个运算数之后的表达式式叫做后缀表达式。
我们可以设置一个栈来保存运算符，利用运算符的优先级来进行运算符进栈入栈的操作。这里我们可以用到map容器，对运算符进行赋值，以此来判断栈内栈外运算符优先级的高低。
- 伪代码
结合运算符优先级用map容器给运算符赋值；
mp<char,int>in;//已入栈运算符的优先级；
mp<char,int>un;//未入栈时运算符优先级；
while(str[i])
{
if(str[i]为数字或者小数点'.')
while(str[i]为数字或者小数点'.')
str[i]写入后缀表达式中，继续读取下一字符；
else if(str[i]为正负号)
将负号写入后缀表达式中，读取下一字符；
else//都是运算符
{
if(栈空 || 栈顶运算符的优先级比str[i]低)
str[i]进栈，再读取下一字符；
else if(栈顶运算符的优先级比str[i]高)
while(栈顶运算符的优先级比str[i]高)
将栈顶元素写入后缀表达式，读取下一字符；
else //栈顶运算符的优先级等于str[i]的优先级，说明是左右括号配对的情况；
将栈顶元素'('出栈；读取下一字符；
}
如果栈不空，则出栈所有元素，写入后缀表达式中；
}
- 代码
1.3 队列
队列也是一个运算受限的线性表，它只能选取一端进行插入操作，另一端做删除操作，是先进先出的一种结构。我们把进行删除的一段叫做队头，进行插入的一端叫做队尾。
1.3.1顺序队列
顺序队结构体定义
typedf struct
{
Elemtype data[MaxSize];
int front;//队头指针；
int rear;//队尾指针；
}QNode;
顺序队初始化
void InitQueue(Queue &q)
{
q.front=q.rear=-1;
}
判断是否为空队
bool IsEmpty(Queue &q)
{
if(q.rear==q.front)//队空
return true;
else//队不空
return false;
}
判断是否队满
/*顺序队*/
bool IsFull(Queue &q)
{
if(q.rear==MaxSize-1)//队满
return true;
else
return false;
}
进队
bool Push(Queue &q,Elemtype e)
{
if(IsFull(q))//在进队之前一定要先判断是否队满；
return false;//表示入队失败；
else
q.data[++q.rear] = e;
return true;//表示入队成功；
}
出队
bool Pop(Queue &q,Elemtype &e)
{
if(IsEmpty())//出栈是要先判断是否为空栈；
return false;
else
e = q.data[++q.front];
return true;//表示出队成功；
}
取队头元素
bool GetFront(Queue q,Elemtype &e)
{
if(IsEmpty(q))//取队头是要判断是否为空队；
return false;
else
e = q.data[q.front + 1];
return true;
}
销毁顺序队
void DestroyQueue(Queue &q)
{
delete q;
}
1.3.2链队列
顺序队结构体定义
typedef struct qnode//用于保存每个结点；
{
Elemtype data;
struct qnode *next;
}Node,*LinkNode;
typedef struct
{
LinkNode front;//队头指针；
LinkNode rear;//队尾指针；
}Queue;
顺序队初始化
void InitQueue(Queue &q)
{
q.front->next = NULL;
q.rear->next = NULL;
}
判断是否为空队
bool IsEmpty(Queue &q)
{
if(q.front->next==NULL)//队空
return true;
else
return false;
}
判断是否队满
因为是链式存储结构，不用预先设定需要多少的存储空间来保存数据，都是现用现配，空间利用效率比较高。所以只要一个数据我们就可以直接进队，不必考虑是否会队满。
进队
void Push(Queue &q,Elemtype e)
{
LinkNode qtr;
qtr->data=e;
qtr->next=NULL;
if(IsEmpty(q))//先判断是否为空栈，如果为空栈要对队头指针一起修改；
q.front->next = qtr;
q.rear->next = qtr;
q.rear = qtr;
}
出队
bool Pop(Queue &q,Elentype &e)
{
LinkNode qtr;
if(IsEmpty())
return false;
else
{
qtr=q.front->next;//先用qtr保存要出队的结点；
q.front->next=qtr->next;//修改队头指针；
e = qtr->data;
delete qtr;//删除结点；
}
}
取队头元素
bool GetFront(Queue q.Elemtype &e)
{
if(IsEmpty(q))//取队头要先判断是否为空栈；
return false;
else
e= q.front->next->data;
return true;
}
销毁顺序队
void DestroyQueue(Queue &q)
{
LinkNode qtr;
while(q.front!=NULL)
{
qtr = q.front;//str保存当前删除的结点
q.front = q.front->next;//s指向下一个需要删除的结点；
delete qtr;
}
}
1.3.3环形队列
由于队列进行插入和删除的操作不在同一端口进行，所以在顺序链中，当队尾指针rear指向数组的最后一个位置作时，存在队头指针front不在数组的第一个位置上，也就是front!=0，队中还存在若干空位置，这种情况我们称为假溢出。所以，为了提高空间的利用率，我们引入一个特殊的队列————循环队列。
顺序队结构体定义
typedef struct
{
Elemtype data[MaxSize];
int front;
int rear;
}Queue;
初始化
void InitQueue(Queue &q)
{
front = rear = 0;//指向0位置；
}
判断是否为空队
bool IsEmpty(Queue &q)
{
if(front == rear)
return true;
else
return false;
}
判断是否队满
bool IsFull(Queue &q)
{
if((q.rear+1)%MaxSize == q.front)
return true;
else
return false;
}
进队
bool Push(Queue &q, Elemtype e)
{
if(IsFull(q))//先判断是否队满；
return false;
else
{
q.data[q.rear] = e;//先保存e，再移动rear指针，所以操作完的rear指针指向的是下一个需要插入的位置，也就是队尾元素的下一个位置。
q.rear = (q.rear+1)%MaxSize;
}
return true;
}
出队
bool Pop(Queueu &q, Elemtype &e)
{
if(IsEmpty(q))
return false;
else
e = q.data[q.front];
q.front = (q.front+1)%MaxSize;//操作完的front指向的是队头元素。
}
1.3.4 C++容器：queue
头文件：#include <queue>
q.push(x);将x插入到队列末端，成为新的队尾元素；
q.pop();弹出队列的第一个元素，注意！！这里不返回被弹出元素；
q.front();返回队头元素；
q.back();返回队尾元素；
q.empty();当队空是，返回true；
q.size();返回队列的元素个数；
1.3.5队列应用
- 思路：
定义队列，将游戏人数按编号依次进队，定义变量i循环自增，
用i求余m来判断要出队的是几号，i求余m=0时，输出号数，再将此数出队，求余m不等于0时，
定义临时变量k来存放这个数，再将其出队，之后再让k进队构成循环，直至队列为空。
2.PTA实验作业（4分）
2.1 符号配对
2.1.1 解题思路及伪代码
- 伪代码
使用map容器将符号进行配对；
while(str[i])
{
if(str[i]==左括号)
s.push(str[i])//左括号进栈；
else if(str[i]==右括号)
{
if(s.empty())//栈空；
缺少左括号，不匹配，退出循环；
else
{
if(左右括号匹配）
s.pop();//弹出栈顶元素
else//不匹配
退出循环；
}
}
读取下一字符；
}
2.1.2 总结解题所用的知识点
1.使用C++容器map
2.左右符号配对的判断条件
2.2 银行业务队列简单模拟
2.2.1 解题思路及伪代码
- 伪代码
输入n的数值
for i=1 to n
输入一个数num;
if(n为奇数)进入q1队列
else 进入q2队列
while(q1,q2均不为空时)
输出q1中的第一个数， 输出后让该数出队列
if(q1出队列的次数为偶数倍)
q2出队一个元素
end while
while(q1不为空)
将q1中剩余元素输出
while(q2不为空)
将q2中剩余元素输出
return 0;
- 代码
2.2.2 总结解题所用的知识点
1.queue 模板运用
2.考虑队列空满情况
3.注意数据输出的格式
3.阅读代码（0--1分）
3.1 题目及解题代码
题目
解题代码
3.2 该题的设计思路及伪代码
3.2.1 该题的设计思路
先排身高更高的，这是要防止后排入人员影响先排入人员位置
每次排入新人员[h,k]时，已处于队列的人身高都>=h，所以新排入位置就是people[k]
时间复杂度：O(N)。 理由：循环地从头读取people，根据people[i][1]也就是k,插入list
空间复杂度：O(N)。 理由：这里将完成所有插入操作的list重建为vector返回
3.2.2 该题的伪代码
class Solution {
public:
先将people按照身高降序排序，
又由于每次插入的位置是k，所以相同身高需要按k升序排序，否则插入位置会越界
确定循环次数
新建容器tmp用来存放数据
// 循环插入
for i = 0 to len
使用advance()找到应插入位置
插入数据
end for
// 重建vector返回
将完成所有插入操作的list重建为vector返回
}
};
3.3 分析该题目解题优势及难点。
3.3.1优势：
并没有直接使用vector，而是将完成所有插入操作的list重建为vector，这样的操作使得整个代码的运行效率大大提高
先利用了sort函数进行排序，大大减少了后续代码的执行的难度.
3.3.2难点：
每次排入新人员[h,k]时，如何确定新排入的位置
相同身高需要按k升序排序，否则插入的位置会越界