jmu-Java-PTA（6.1-jmu-Java-05集合-01-ListIntegerStack，6.2- 银行业务队列简单模拟）
6.1-jmu-Java-05集合-01-ListIntegerStack
问题要求
定义IntegerStack接口，该接口描述了一个存放Integer的栈的常见方法：
public Integer push(Integer item); // 如item为null，则不入栈直接返回null。否则直接入栈，然后返回item。
public Integer pop(); // 出栈，如栈为空，则返回null。
public Integer peek(); // 获得栈顶元素，如栈顶为空，则返回null。注意：不要出栈
public boolean empty(); // 如果栈为空返回true
public int size(); // 返回栈中元素数量
定义IntegerStack的实现类ArrayListIntegerStack，内部使用ArrayList存储。该类中包含：
构造方法：
在无参构造方法中新建ArrayList或者LinkedList，作为栈的内部存储。
思考：查询JDK文档，尝试说明本题到底使用哪个List实现类最好。
方法:
public String toString() //用于输出List中的内容,可直接调用List的toString()方法。可用System.out.println(list)进行输出。
提示：
不建议使用top指针。最好直接复用List实现类中已有的方法。
pop时应将相应的元素从列表中移除。
main方法说明
建立ArrayListIntegerStack对象
输入m个值，均入栈。每次入栈均打印入栈返回结果。
输出： 栈顶元素，输出是否为空，然后输出size.
输出栈中所有元素（调用其toString()方法）
输入x，然后出栈x次，每次均打印出栈的对象。
输出:栈顶元素，输出是否为空，输出size。注意：这里的输出栈顶元素，仅输出、不出栈。
输出栈中所有元素（调用其toString()方法）。注意：返回null，也要输出。
思考：
如果使用LinkedList来实现IntegerStack，怎么实现？测试代码需要进行什么修改？
输入样例:
5
1 3 5 7 -1
2
输出样例:
1
3
5
7
-1
-1,false,5
[1, 3, 5, 7, -1]
-1
7
5,false,3
[1, 3, 5]
解题步骤
第一步：接口定义
首先，定义了一个IntegerStack接口，其中包含了栈的基本操作方法，如入栈、出栈、查看栈顶元素、判断栈是否为空以及获取栈的大小。
interface IntegerStack {
public Integer push(Integer item);
public Integer pop();
public Integer peek();
public boolean empty();
public int size();
}
第二步：实现类
接下来，实现了一个名为ArrayListIntegerStack的类，该类实现了IntegerStack接口。
第三步：构造方法
在无参构造方法中，初始化了一个ArrayList作为栈的内部存储。
class ArrayListIntegerStack implements IntegerStack {
private ArrayList<Integer> arr = new ArrayList<>();
}
第四步：方法实现
对于每个接口方法，我们都提供了具体的实现：
push方法将元素添加到栈顶，如果元素为null，则不添加并返回null。pop方法移除并返回栈顶元素，如果栈为空，则返回null。peek方法返回栈顶元素，但不移除它。empty方法检查栈是否为空。size方法返回栈中元素的数量。toString方法用于输出栈的内容。
// ...其他方法...
@Override
public String toString() {
return arr.toString();
}
第五步：主方法
在Main类中，我们创建了一个ArrayListIntegerStack对象，并执行了一系列操作，如入栈、出栈，并打印相关信息。
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
ArrayListIntegerStack stack = new ArrayListIntegerStack();
int m = in.nextInt();
for (int i = 0; i < m; i++) {
Integer n = in.nextInt();
Integer e = stack.push(n);
System.out.println(e);
}
System.out.println(stack.peek() + "," + stack.empty() + "," + stack.size());
System.out.println(stack.toString());
int x = in.nextInt();
for (int i = 0; i < x; i++) {
Integer e = stack.pop();
System.out.println(e);
}
System.out.println(stack.peek() + "," + stack.empty() + "," + stack.size());
System.out.println(stack.toString());
}
}
整体代码：
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
interface IntegerStack{
public Integer push(Integer item);
public Integer pop();
public Integer peek();
public boolean empty();
public int size();
}
class ArrayListIntegerStack implements IntegerStack{
private static ArrayList<Integer> arr = new ArrayList<>();
public Integer push(Integer item){
if(item == null){
return null;
}else{
arr.add(item);
}
return item;
}
public Integer pop(){
if(arr.size() == 0){
return null;
}else{
Integer e = arr.get(arr.size()-1);
arr.remove(arr.size()-1);
return e;
}
}
public Integer peek(){
if(arr.isEmpty()){
return null;
}else{
Integer e = arr.get(arr.size()-1);
return e;
}
}
public boolean empty(){
if(!arr.isEmpty()){
return false;
}else{
return true;
}
}
public int size(){
return arr.size();
}
public String toString(){
if(arr.isEmpty()){
return "[]";
}
return arr.toString();
}
}
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
ArrayListIntegerStack arr = new ArrayListIntegerStack();
int m = in.nextInt();
for(int i=0;i<m;i++){
Integer n = in.nextInt();
Integer e = arr.push(n);
System.out.println(e);
}
System.out.println(arr.peek()+","+arr.empty()+","+arr.size());
System.out.println(arr.toString());
int x = in.nextInt();
for(int i=0;i<x;i++){
Integer e = arr.pop();
System.out.println(e);
}
System.out.println(arr.peek()+","+arr.empty()+","+arr.size());
System.out.println(arr.toString());
}
}
思考
如果使用LinkedList来实现IntegerStack，实现方式将非常相似，因为LinkedList也实现了List接口。主要的不同在于内部数据结构，LinkedList在频繁的插入和删除操作中可能更高效。
对于测试代码，如果切换到LinkedList则不需要做任何修改，因为ArrayListIntegerStack类完全依赖于List接口的方法，而不是ArrayList特有的方法。
6.2- 银行业务队列简单模拟
问题要求
设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。
输入格式:
输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。
输出格式:
按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。
输入样例:
8 2 1 3 9 4 11 13 15
输出样例:
1 3 2 9 11 4 13 15
关键点
- 窗口处理速度差异：A窗口每处理两个顾客，B窗口才能处理一个顾客。
- 顾客编号规则：奇数编号的顾客去A窗口，偶数编号的顾客去B窗口。
- 输出顺序：A窗口的顾客优先输出，当两个窗口同时处理完顾客时。
解题步骤
第一步：初始化数据结构
为了模拟两个窗口，可以使用两个LinkedList来分别存储A窗口和B窗口的顾客。
LinkedList<Integer> lista = new LinkedList<>();
LinkedList<Integer> listb = new LinkedList<>();
第二步：分配顾客到窗口
遍历输入的顾客编号，根据编号的奇偶性将顾客分配到对应的窗口队列中。
for (int i = 0; i < n; i++) {
int e = in.nextInt();
if (e % 2 != 0) {
lista.add(e);
} else {
listb.add(e);
}
}
第三步：处理顾客并输出
通过一个循环来模拟窗口处理顾客的过程。在这个循环中，根据题目要求我们需要处理以下几点：
- A窗口的处理速度是B窗口的两倍，因此我们需要一个计数器
count来记录A窗口处理的顾客数量。 - 当
count达到2时，表示A窗口处理了两个顾客，这时我们也需要处理B窗口的一个顾客。 - 输出顾客编号时，需要注意格式，尤其是最后一个编号后不能有多余的空格。
int count = 1;
int flag = 1; // 用于控制输出格式
while (lista.size() != 0 && listb.size() != 0) {
if (count != 2) {
// 输出A窗口的顾客
System.out.print((flag == 1 ? "" : " ") + lista.get(0));
lista.remove(0);
count++;
} else {
// 输出A窗口和B窗口的顾客
System.out.print(" " + lista.get(0));
lista.remove(0);
System.out.print(" " + listb.get(0));
listb.remove(0);
count = 1;
}
flag = 2;
}
第四步：处理剩余顾客
在主循环结束后，可能还有顾客在某个窗口的队列中等待处理。我们需要分别处理这两个队列中的剩余顾客。
while (lista.size() != 0) {
System.out.print((flag == 1 ? "" : " ") + lista.get(0));
lista.remove(0);
flag = 2;
}
while (listb.size() != 0) {
System.out.print((flag == 1 ? "" : " ") + listb.get(0));
listb.remove(0);
}
整体代码：
import java.util.Scanner;
import java.util.LinkedList;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
LinkedList<Integer> lista = new LinkedList<>();
LinkedList<Integer> listb = new LinkedList<>();
for(int i=0;i<n;i++){
int e = in.nextInt();
if(e%2!=0){
lista.add(e);
}else{
listb.add(e);
}
}
int count=1;
int flag = 1;
while(lista.size()!=0&&listb.size()!=0){
if(count!=2){
if(flag==1){
flag=2;
System.out.print(lista.get(0));
}else{
System.out.print(" "+lista.get(0));
}
lista.remove(0);
count += 1;
}else{
count = 1;
System.out.print(" "+lista.get(0));
lista.remove(0);
System.out.print(" "+listb.get(0));
listb.remove(0);
}
}
while(lista.size()!=0){
if(flag==1){
flag=2;
System.out.print(lista.get(0));
}else{
System.out.print(" "+lista.get(0));
}
lista.remove(0);
}
while(listb.size()!=0){
if(flag==1){
flag=2;
System.out.print(listb.get(0));
}else{
System.out.print(" "+listb.get(0));
}
listb.remove(0);
}
}
}