蓝桥杯刷题 Day 4 栈与链表

蓝桥杯刷题 Day 4 栈与链表

---

---

前言

今天写牛客网模板题中的数据结构模块：栈与列表

---

一、栈

原题地址: 栈

import java.util.*;public class Stack1 {public static void main(String[] args) {Scanner input = new Scanner(System.in);// 输入操作次数n以及字符串int n = input.nextInt();// 创建数组模拟栈操作int[] stack = new int[n];int size = 0;for (int i = 0; i < n; i++) {String pattern = input.next();switch (pattern){case "push":int x = input.nextInt();stack[size++] = x;break;case "pop":System.out.println(size == 0 ? "error" : stack[--size]); // --size，先将索引-1，再查找（改变栈，使出栈）break;case "top":System.out.println(size == 0? "error" : stack[size - 1]);}}}
}

1. 解题思路

栈是后入先出，将洗完的盘子叠好，再一个个地取出来用。

1. 用数组模拟出入栈

2. 拆解代码（不复杂，不拆了）

二、链表

import java.util.*;public class Linked {public static void main(String[] args) {Scanner input = new Scanner(System.in);MyList myList = new MyList();// 输入n个操作数int n = input.nextInt();// 处理指令for (int i = 0; i < n; i++) {String command = input.next();switch(command){case "insert":int x = input.nextInt();int y = input.nextInt();myList.insert(x,y);break;case "delete":int num = input.nextInt();myList.delete(num);break;}}System.out.println(myList.print());}// 自定义列表类static class MyList{// 定义结构存储LinkedList<Integer> list = new LinkedList<>();// 插入public void insert(int x, int y){int position = list.indexOf(x); // indexOf()返回列表第一次出现的位置，lastindexOf()最后一次出现的位置if(position != -1){list.add(position, y); // 在position处插入，其余往后移}else {list.addLast(y); // 末尾插入}}// 删除public void delete(int x){list.remove(Integer.valueOf(x)); // 这样才能按值删除，若为int，则按索引删除}// 输出public String print(){if(list.isEmpty()) return "NULL";// 将列表转换成字符串输出StringBuilder sb = new StringBuilder();for(Integer num:list){sb.append(num).append(" ");}// trim()处理末尾空格return sb.toString().trim();}}
}

1. 解题思路

也没啥好说的，看题，写delete()和insert()方法

1.1 主函数

public static void main(String[] args) {Scanner input = new Scanner(System.in);MyList myList = new MyList();// 输入n个操作数int n = input.nextInt();// 处理指令for (int i = 0; i < n; i++) {String command = input.next();switch(command){case "insert":int x = input.nextInt();int y = input.nextInt();myList.insert(x,y);break;case "delete":int num = input.nextInt();myList.delete(num);break;}}System.out.println(myList.print());}

1.2 自定义列表类

 static class MyList{// 定义结构存储LinkedList<Integer> list = new LinkedList<>();
}

1.2.1 插入操作

public void insert(int x, int y){int position = list.indexOf(x); // indexOf()返回列表第一次出现的位置，lastindexOf()最后一次出现的位置if(position != -1){list.add(position, y); // 在position处插入，其余往后移}else {list.addLast(y); // 末尾插入}}

1.2.2 删除操作

public void delete(int x){list.remove(Integer.valueOf(x)); // 这样才能按值删除，若为int，则按索引删除}

1.2.3 按要求输出

 // 输出public String print(){if(list.isEmpty()) return "NULL";// 将列表转换成字符串输出StringBuilder sb = new StringBuilder();for(Integer num:list){sb.append(num).append(" ");}// trim()处理末尾空格return sb.toString().trim();}

三、 题后收获

3.1 知识点

1. list.indexOf()：返回列表第一次出现的位置
2. list.add(position, y); // 在position处插入，其余往后移
3. list.addLast(y); // 末尾插入
4. remove(object)与remove(int)：list.remove(Integer.valueOf(x));
5. 将列表转换成字符串输出
   StringBuilder sb = new StringBuilder();
   for(Integer num:list){
   sb.append(num).append(" ");
   }
   // trim()处理末尾空格
   return sb.toString().trim();