一.学习总结

1 关键词:

  • 逻辑结构,存储结构,抽象数据类型,顺序存储类型,链式存储类型,线性表应用
  • 栈和队列

2 使用思维导图将这些关键词组织起来。

DS03--栈和队列-LMLPHP

DS03--栈和队列-LMLPHP

二.PTA实验作业

2.1题目1:符号配对

请编写程序检查C语言源程序中下列符号是否配对://、(与)、[与]、{与}。

1.设计思路

定义i,flag记录变量和判断变量
定义字符型e,str[MAXSIZE]
初始化栈s
while(1)
{
读取一整行字符串
定义len为字符串长度
if(开头为.且长度为1)
跳出循环end
for(遍历字符串)
{
if(为左大中小括号)
进栈
else if(为左注释符号)
用<代替进栈 else if(右括号) {[(/*四种情况类似
{
if(栈不空)
{
取栈顶元素
if(栈顶为左括号)
出栈
else
{
右括号缺失输出
flag=1标记
break跳出循环
}
}
else栈已经空
{
左括号缺失输出
flag=1标记
break跳出循环
}
}
}
}
if(!flag且栈空)
输出YES
else if(!flag)
取栈顶元素
右括号缺失输出

2.代码截图

DS03--栈和队列-LMLPHP

DS03--栈和队列-LMLPHP

DS03--栈和队列-LMLPHP

DS03--栈和队列-LMLPHP

DS03--栈和队列-LMLPHP

DS03--栈和队列-LMLPHP

3.PTA提交列表说明

DS03--栈和队列-LMLPHP

调试问题

  • 答案错误:出栈函数e前没加&号,导致没将元素返回到主函数内,找了很久才发现原来错在这里

DS03--栈和队列-LMLPHP

  • 部分正确:开头多余左符号,比起上一个错误好改很多

DS03--栈和队列-LMLPHP

DS03--栈和队列-LMLPHP

多输出了一个NO

2.2题目2:银行业务队列简单模拟

设某银行有A、B两个业务窗口,且处理业务的速度不一样,其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时,B窗口处理完1个顾客。给定到达银行的顾客序列,请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔,并且当不同窗口同时处理完2个顾客时,A窗口顾客优先输出。

1.设计思路

初始化A,B窗口
for(i=0 to n)
输入num
奇偶数分别进入A,B队
end while(A,B都不为空)
{
if(A不为空)
控制输出格式
if(A不为空)
继续输出格式
if(B不为空)
控制输出格式
}
end

2.代码截图

DS03--栈和队列-LMLPHP

DS03--栈和队列-LMLPHP

3.PTA提交列表说明

DS03--栈和队列-LMLPHP

调试问题

  • 部分正确:忘记加上A两倍输出

DS03--栈和队列-LMLPHP

2.3题目3:jmu-报数游戏

1.设计思路

定义循环变量i,队列q
for(i=1 to n)
元素入队列
更改长度
end
if(m>=n)
输出错误
else
定义观察变量flag=1
while(队列不为空)
for(i=0 to m-1)
前m-1个元素先出队再入队
出队第m个元素
控制输出格式
end

2.代码截图

DS03--栈和队列-LMLPHP

DS03--栈和队列-LMLPHP

3.PTA提交列表说明

  • 编译错误:没有改c++

3.截图本周题目集的PTA最后排名

3.1 栈PTA排名

DS03--栈和队列-LMLPHP

3.2 队列PTA排名

DS03--栈和队列-LMLPHP

3.3 我的总分:2.5分(205分)

四. 阅读代码

利用两个队列实现一个栈

public class StackByTwoQueue
{
/*
* 两个队列实现一个栈
* pop完成出栈操作,push完成入栈操作
*/
public void push(String obj) {
if(queue1.isEmpty()){
queue2.add(obj);
}
if(queue2.isEmpty()){
queue1.add(obj);
}
}
public String pop() {
//两个栈都为空时,没有元素可以弹出
if (queue1.isEmpty()&&queue2.isEmpty()) {
try {
throw new Exception("stack is empty");
} catch (Exception e) {
}
}
if(queue1.isEmpty()){
while(queue2.size()>1){
queue1.add(queue2.poll());
}
return queue2.poll();
}
if(queue2.isEmpty()){
while(queue1.size()>1){
queue2.add(queue1.poll());
}
return queue1.poll();
}
return null;
} public static void main(String[] args) {
StackByTwoQueue stack = new StackByTwoQueue();
for(int i=0;i<10;i++){
stack.push(i+"");
}
for(int i=0;i<20;i++){
System.out.println(stack.pop());
}
} }

此代码实现的时用两个队列来实现栈,网上关于这个题目的代码基本上都是c++,代码虽然不能完全理解,但思路还是可以明白的。将queue1 作为入队存储数据的功能,queue2 作为中转件,出队时先把 queue1 中数据取出然后加入到 queue2 中,出队之后再返回到 queue2 中。

五.代码Git提交记录截图

DS03--栈和队列-LMLPHP

05-22 15:15