目录
环形链表
按一条件删除节点
测试
结果
栈
用数组模拟栈
测试
【链表|数据结构与算法（环形链表，栈）】栈实现综合计算器
环形链表
按一条件删除节点 根据用户的输入，生成一个小孩出圈的顺序
n=5，有5个小孩
k=1，从第一个小孩开始报数
m=3，数3下（或m=3，3的倍数）
1.创建一个辅助指针temp，初始指向环形链表最后一个节点
2.让first和temp指针同时移动m-1次
3.让first指向小孩出圈
first=first.next
temp.next=first
/**
*
* @param startnum 开始的小孩的编号
* @param countnum 表示数几下或者几的倍数
* @param nums 起初有多少个小孩
*方法一
*/
public void delete(int startnum,int countnum,int nums){
if(first==null||startnum<1||startnum>nums){
System.out.println("输入参数有误");
return;
}
Nodeperson temp=first;
while (true){
if(temp.next==first){
break;
}
temp=temp.next;
}
while (true){
if(temp==first){
break;
}
for (int i=0;
inums||startnum<1||first==null){
System.out.println("输入参数有误");
return;
}
int k=1;
Nodeperson temp=first;
while (true){
if(temp.next==first){
break;
}
temp=temp.next;
}
while (true){
if (temp==first){
break;
}
if(k%3==0){
System.out.printf("小孩%d出圈%n",first.getId());
first=first.next;
temp.next=first;
k++;
}else {
k++;
first=first.next;
temp=temp.next;
}
}
} 测试
public static void main(String[] args) {
CircleList cl=new CircleList();
cl.addCircleList(5);
cl.show();
cl.delete(1,3,5);
System.out.println("-----------------");
cl.addCircleList(5);
cl.delete2(1,3,5);
}结果
文章图片
栈 栈的介绍：
1.栈是一个先入后出的有序列表
2.栈是线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端为变化的一端，称为栈顶。。另一端为固定的一端，称为栈底。
3.根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。
文章图片
文章图片
用数组模拟栈 1.定义一个top来表示栈顶，初始化为-1
2.入栈：top++；stack【top】=data
3.出栈：invalue=https://www.it610.com/article/stack【top】；top--
class ArrayStack{
private int maxSize;
private int[] stack;
private int top=-1;
public ArrayStack(int maxSize){
this.maxSize=maxSize;
stack=new int[maxSize];
}
//判断栈空
public boolean isEmploy(){
return top==-1;
}
//判断栈满
public boolean isFull(){
return top==maxSize-1;
}
//入栈
public void push(int num){
if (isFull()){
System.out.println("栈已经满了");
return;
}
top++;
stack[top]=num;
}
//出栈
public int pop(){
int num=0;
if(isEmploy()){
System.out.println("栈已经空了");
}else {
num=stack[top];
top--;
}
return num;
}
//显示栈
public void show(){
if (isEmploy()){
System.out.println("栈是空的");
return;
}
for (int i=top;
i>=0;
i--){
System.out.println("栈的数据为"+stack[i]);
}
}
}
测试
public static void main(String[] args) {
ArrayStack arrayStack=new ArrayStack(5);
boolean loop=true;
Scanner sc=new Scanner(System.in);
while (loop){
System.out.println("1.入栈");
System.out.println("2.出栈");
System.out.println("3.显示");
System.out.println("4.结束");
int scnum=sc.nextInt();
switch (scnum){
case 1:
System.out.println("请输入一个数");
int num=sc.nextInt();
arrayStack.push(num);
break;
case 2:
int popnum=arrayStack.pop();
System.out.println("出栈的数为"+popnum);
break;
case 3:
arrayStack.show();
break;
case 4:
sc.close();
loop=false;
break;
default:
break;
}
}栈实现综合计算器 1.通过一个temp指针来遍历表达式
2.如果遍历的字符为数字，直接入数栈
3.如果遍历的字符为符号
如果符号栈为空，直接入符号栈
如果符号栈有操作符
如果当前操作符的优先级小于或等于栈中操作符，要从数栈中取出两个数，在符号栈中取出一个符号，进行运算得到结果入数栈，把当前操作符入符号栈。
如果当前操作符的优先级大于符号栈里的，直接入符号栈
4.当前表达式扫描完毕，就顺序的从数栈和符号栈取出进行运算
5.当数栈中只剩下一个数或者符号栈为空时，该数栈的数就是表达式的结果。
public class StackDemo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String biaodashi = sc.next();
//创建数栈和符号栈
ArrayStack snum = new ArrayStack(10);
ArrayStack soper = new ArrayStack(10);
//定义需要的相关变量
int res = 0;
int num1 = 0;
int num2 = 0;
int temp = 0;
int oper = 0;
char ch = ' ';
String keepNum = "";
while (true) {
ch = biaodashi.substring(temp, temp + 1).charAt(0);
//ch如果是运算符
if (soper.isoper(ch)) {
//运算符栈里为空
if (soper.isEmploy()) {
soper.push(ch);
} else {//如果不为空
//ch优先级小于栈里的
if (soper.priority(ch) <= soper.priority(soper.peek())) {
num1 = snum.pop();
num2 = snum.pop();
oper = soper.pop();
res = snum.addnum(num1, num2, oper);
snum.push(res);
soper.push(ch);
} else {//优先级大于栈里的
soper.push(ch);
}
}
} else {//如果不是运算符
keepNum += ch;
//如果ch后一位是运算符则入栈
if (temp == biaodashi.length()-1) {
snum.push(Integer.parseInt(keepNum));
} else {
if (soper.isoper(biaodashi.substring(temp + 1, temp + 2).charAt(0))) {
snum.push(Integer.parseInt(keepNum));
//清空keepnum重复使用
keepNum = "";
}
}
}
temp++;
if(temp==biaodashi.length()){
break;
}
}
while (true){
if(soper.isEmploy()){
break;
}
num1= snum.pop();
num2=snum.pop();
oper=soper.pop();
res=snum.addnum(num1,num2,oper);
snum.push(res);
}
System.out.printf("表达式%s=%d",biaodashi,snum.pop());
}
}class ArrayStack {
private int maxSize;
private int[] stack;
private int top = -1;
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}//判断栈空
public boolean isEmploy() {
return top == -1;
}//判断栈满
public boolean isFull() {
return top == maxSize - 1;
}//入栈
public void push(int num) {
if (isFull()) {
System.out.println("栈已经满了");
return;
}
top++;
stack[top] = num;
}//出栈
public int pop() {
int num = 0;
if (isEmploy()) {
System.out.println("栈已经空了");
} else {
num = stack[top];
top--;
}
return num;
}//显示栈
public void show() {
if (isEmploy()) {
System.out.println("栈是空的");
return;
}
for (int i = top;
i >= 0;
i--) {
System.out.println("栈的数据为" + stack[i]);
}
}//返回运算符的优先级
public int priority(int oper) {
if (oper == '*' || oper == '/') {
return 1;
} else if (oper == '+' || oper == '-') {
return 0;
} else {
return -1;
}
}//计算方法
public int addnum(int num1, int num2, int oper) {
int res = 0;
switch (oper) {
case '+':
res = num1 + num2;
break;
case '-':
res = num2 - num1;
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}public boolean isoper(int oper) {
if (oper == '+' || oper == '-' || oper == '*' || oper == '/') {
return true;
}
return false;
}//返回栈的头
public int peek() {
return stack[top];
}
}推荐阅读
- dp|最近写过的dp题单（持续更新）
- 数据结构|递归算法简介
- 数据结构|面对对象编程细则（三）
- 数据结构|浅谈算法分析
- Windows核心编程|Windows提取环境变量
- c语言药店管理系统|药店管理系统(c语言链表实现)
- python全栈开发|进军Python全栈开发--14.Python中的数据结构与算法
- b树|MySQL索引原理，设计原则
- 算法|KMP算法、计算器(一）、(二)