栈（Stack）day04

程序员文章站 2022-06-04 09:13:28

...

栈的应用

栈（Stack）day04

栈的介绍

栈的英文为(stack)
栈是一个先入后出(FILO-First In Last Out)的有序列表。
栈(tack)是限制线性表中元素的插入和删除只能在线性表的同-端进行的一种特殊线性表。 允许插入和删除的一端，为变化的一端，称为栈顶(Top), 另一端为固定的一端，称为栈底(Bottom).
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

图解方式说明出栈(pop)和入栈(push)的概念：
栈（Stack）day04

栈的应用场景

子程序的调用:在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
处理递归调用:和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
二叉树的遍历。
图形的深度优先(depth一firs)搜索法。

栈的入门

用数组模拟栈的使用，由于栈是一种有序列表，当然可以使用数组的结构来储存栈的数据内容，下面我们就用数组模拟栈的出栈，入栈等操作。
实现思路分析,并画出示意图

数组模拟

package com.xhl.ArrayStack;

public class ArrayStack {
	private int maxSize;
	private int[] stack;
	private int top=-1;
	
	public ArrayStack(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}
	
	public boolean isFull() {
		return top == maxSize-1;
	}
	
	public boolean isEmpty() {
		return top == -1;
	}
	
	public void push(int value) {
		if(isFull()) {
			System.out.println("栈满");
			return ;
		}
		stack[++top]=value;
	}
	
	public int pop() {
		if(isEmpty()) {
			throw new RuntimeException("栈空");
		}
		return stack[top--];
	}
	
	public void show() {
		if(isEmpty()) {
			System.out.println("栈空");
		}
		for(int i=top;i>-1;i--) {
			System.out.printf("%d\t",stack[i]);
		}
	}
}

package com.xhl.ArrayStack;

import java.util.Scanner;

public class ArrayStackDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//测试
		ArrayStack as = new ArrayStack(5);
		char key=' ';
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		
		//菜单
		System.out.println("s(show)：显示栈");
		System.out.println("o(pop)：出栈");
		System.out.println("i(push)：入栈");
		System.out.println("e(exit)：退出程序");
		while(loop) {
			
			key = scanner.next().charAt(0);
			switch(key) {
			case's':
				as.show();
				break;
			case'i':
				System.out.println("请输入需要插入的数据?");
				int value = scanner.nextInt();
				as.push(value);
				break;
			case'o':
				int top = as.pop();
				System.out.println("出栈的数据是?"+top);
				break;
			case'e':
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
			
		}
		
		System.out.println("程序退出！！！");
	}

}

链表模拟

package com.xhl.LinkedStack;

public class Node {
	public int data;
	public Node next;
	
	//构造器
	public Node(int data) {
		super();
		this.data = data;
		next = null;
	}

	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return "Node[data="+data+"]";
	}
}

package com.xhl.LinkedStack;

import com.xhl.SingleLinkedList.Node;

public class LindedStack {
	//初始化头结点
	Node head = new Node(0);
	
	//入栈，用尾插法
	public void push(Node node) {
		if(head.next!=null) {
			node.next=head.next;
		}
		head.next=node;
	}
	
//	出栈
	public int pop() {
		if(head.next==null) {
			throw new RuntimeException("栈空");
		}
		Node node = head.next;
		head.next=node.next;
		return node.data;
	}
	
	//显示链表
	public void show() {
		Node temp = head;
		//遍历链表，找到最后的节点
		while(temp.next!=null) {
			temp = temp.next;
			System.out.println(temp.toString());
		}
		System.out.println();
	}
	
}

package com.xhl.LinkedStack;

import java.util.Scanner;

import com.xhl.SingleLinkedList.Node;

public class LinkedStackDemo {

	public static void main(String[] args) {
		//测试
		LindedStack ls = new LindedStack();
		char key=' ';
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		
		//菜单
		System.out.println("s(show)：显示栈");
		System.out.println("o(pop)：出栈");
		System.out.println("i(push)：入栈");
		System.out.println("e(exit)：退出程序");
		while(loop) {
			
			key = scanner.next().charAt(0);
			switch(key) {
			case's':
				ls.show();
				break;
			case'i':
				System.out.println("请输入需要插入的数据?");
				int value = scanner.nextInt();
				ls.push(new Node(value));
				break;
			case'o':
				int top = ls.pop();
				System.out.println("出栈的数据是:"+top);
				break;
			case'e':
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
			
		}
		
		System.out.println("程序退出！！！");
	}

}

栈实现综合计算器（中缀表达式）

使用栈来实现综合计算器
思路分析

package com.xhl.ArrayStack;

public class ArrayStack2 {
	private int maxSize;
	private int[] stack;
	private int top=-1;
	
	public ArrayStack2(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}
	
	
	public boolean isFull() {
		return top == maxSize-1;
	}
	
	public boolean isEmpty() {
		return top == -1;
	}
	
	public void push(int value) {
		if(isFull()) {
			System.out.println("栈满");
			return ;
		}
		stack[++top]=value;
	}
	
	public int pop() {
		if(isEmpty()) {
			throw new RuntimeException("栈空");
		}
		return stack[top--];
	}
	
	public void show() {
		if(isEmpty()) {
			System.out.println("栈空");
		}
		for(int i=top;i>-1;i--) {
			System.out.printf("%d\t",stack[i]);
		}
	}
	
	//返回栈顶值
	public int peek() {
		return stack[top];
	}
	
	//返回运算符优先级
//	数字越大优先级越高
	public int priority(int oper) {
		if(oper == '*'||oper == '/') {
			return 1;
		}else if(oper == '+'||oper == '-') {
			return 0;
		}else {
			return -1;//假定运算符只有+-*/;
		}
	}
	
	//计算
	public int cal(int numA,int numB,int oper) {
		int res = 0;
		switch(oper) {
		case '+':
			res = numA+numB;
			break;
		case '-':
			res = numB-numA;
			break;
		case '*':
			res = numA*numB;
			break;
		case '/':
			res = numB+numA;
			break;
		default:
			break;
		}
		
		return res;
	}
	//判断是否为运算符
	public boolean isOper(char val) {
		return val=='+'||val=='-'||val=='*'||val=='/';
	}
}

package com.xhl.ArrayStack;

public class Calculator {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String expression = "7*2*2-5+1-5+3-4*5";
		ArrayStack2 numStack = new ArrayStack2(10);
		ArrayStack2 operStack = new ArrayStack2(10);
		int numA,numB;
		int index=0;//用于扫描
		int res;
		int oper;
		char ch=' ';
		String keepNum = "";
		while(index<expression.length()) {
			ch=expression.substring(index, index+1).charAt(0);//截取字符串取第一个
			if(operStack.isOper(ch)) {
				numStack.push(Integer.parseInt(keepNum));
				keepNum="";
				if(!operStack.isEmpty()) {
					if(operStack.priority(ch)<=operStack.priority(operStack.peek())) {
						numA = numStack.pop();
						numB = numStack.pop();
						oper = operStack.pop();
						res = numStack.cal(numA, numB, oper);
						numStack.push(res);
						operStack.push(ch);
					}else {
						operStack.push(ch);
					}
				}else {
					operStack.push(ch);
				}
			}else {
				keepNum+=ch;
				if(index == expression.length()-1) {
					numStack.push(Integer.parseInt(keepNum));
				}
			}
			index++;
		}
		
		while(!operStack.isEmpty()) {
			numA = numStack.pop();
			numB = numStack.pop();
			oper = operStack.pop();
			res = numStack.cal(numA, numB, oper);
			numStack.push(res);
		}
		
		int result = numStack.pop();
		System.out.printf("表达式%s=%d",expression,result);
	}

}

栈（Stack）day04

逆波兰计算器

我们完成-一个逆波兰计算器，要求完成如下任务:

输入一个逆波兰表达式(后缀表达式)，使用栈(Stack), 计算其结果
2)支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。
3)思路分析

中缀表达式转换为后缀表达式

栈（Stack）day04

相关标签：数据结构复习数据结构

上一篇：越发凉凉：HTC关闭高级粉丝社区Elevate

下一篇：俗话说乱世不见佛,盛世不见道这里面到底有什么原因

栈（Stack）day04

栈的应用

栈的介绍

栈的应用场景

栈的入门

数组模拟

链表模拟

栈实现综合计算器（中缀表达式）

逆波兰计算器

中缀表达式转换为后缀表达式

Python全栈Day 9部分知识点

Docker搭建简单的应用栈与容器Hello World访问详解

Python实现包含min函数的栈

云知声 OpenDay 深圳站：全栈 AI 硬核技术助力产业落地

C#数据结构与算法揭秘五栈和队列

JS栈stack类的实现与使用方法示例

Python编程实现双链表，栈，队列及二叉树的方法示例

Python栈算法的实现与简单应用示例

用PHP解决的一个栈的面试题

服务器（CentOS)安装配置mongodb-do前端while全栈-SegmentFault思否

栈（Stack）day04

栈的应用

栈的介绍

栈的应用场景

栈的入门

数组模拟

链表模拟

栈实现综合计算器（中缀表达式）

逆波兰计算器

中缀表达式转换为后缀表达式

Python全栈Day 9部分知识点

Docker搭建简单的应用栈与容器Hello World访问详解

Python实现包含min函数的栈

云知声 OpenDay 深圳站：全栈 AI 硬核技术助力产业落地

C#数据结构与算法揭秘五 栈和队列

JS栈stack类的实现与使用方法示例

Python编程实现双链表，栈，队列及二叉树的方法示例

Python栈算法的实现与简单应用示例

用PHP解决的一个栈的面试题

服务器（CentOS)安装配置mongodb-do前端while全栈-SegmentFault思否

C#数据结构与算法揭秘五栈和队列