java数据结构关于栈的实例应用
此文章介绍关于顺序栈，链式栈的实例操作，括号匹配，表达式求值（后缀表达式）
1.声明一个栈接口SStack
package ch05;
public interface SStack <T>{
boolean isEmpty(); // 判断栈是否为空
void push(T x); // 元素x入栈
T pop(); // 出栈，返回栈顶元素
T peek(); // 返回栈顶元素，但不出栈
}
2. 定义顺序栈类SeqStack<T>，包括数据元素的对象数组和栈顶元素下标两个私有成员变量，构造方法可实例化容量为size大小的空顺序栈，调用类中成员方法实现顺序栈的入栈、出栈、获取栈顶元素等操作，重写toString()方法获取顺序栈的字符串描述。
package ch05;
public class SeqStack <T> implements SStack<T>{
Object[] element;
int top;
// 构造方法，创建一个空栈，存储容量大小size
public SeqStack(int size){
element=new Object[size];
top=-1;
}
// 判断栈是否为空
@Override
public boolean isEmpty() {
return top==-1;
}
// 元素x入栈
@Override
public void push(T x) {
if (x==null){
return;
}
// 若栈满，则扩充栈容量
if (this.top==element.length-1){
Object[] temp=this.element;
element=new Object[temp.length*2];
for (int i=0;i<temp.length;i++){
element[i]=temp[i];
}
}
//入栈
this.element[++top]=x;
}
// 出栈，返回栈顶元素
@Override
public T pop() {
if (top!=-1){
return (T) this.element[this.top--];
}
return null;
}
// 返回栈顶元素，但不出栈
@Override
public T peek() {
if (top!=-1){
return (T) this.element[this.top];
}
return null;
}
// 返回顺序栈中所有元素的描述字符串，形式为"（,）"，覆盖Object类的toString()方法
public String toString(){// 自栈顶输出到栈底
String str="";
if (top>=0){
str="(";
for (int i=top;i>=0;i--){
str+=element[i]+",";
}
str=str.substring(0,str.length()-1);
str+=")";
}else {//空栈
str="()";
}
return str;
}
}
3.定义结点类Node<T>，包括数据域和地址域两个成员变量，构造方法实例化结点，重写toString()方法获取结点的字符串描述。
package ch05;
public class Node <T>{
public T data;
public Node<T> next;
public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
public Node(){
this(null,null);
}
}
4. 定义链式栈类LinkedStack<T>：
package ch05;
public class LinkedStack<T> implements SStack<T>{
private Node<T> top;
public LinkedStack() {
top=new Node<>();
}
@Override
public boolean isEmpty() {
return top.next==null ? true:false;
}
@Override
public void push(T x) {
if (x==null){
return;
}
//生成新结点
Node<T> q=new Node<>(x,null);
q.next=top.next;
top.next=q;
}
@Override
public T pop() {
T elem=null;
if (top.next!=null){
elem=top.next.data;
top.next=top.next.next;
}
return elem;
}
@Override
public T peek() {
T elem=null;
if (top.next!=null){
elem=top.next.data;
}
return elem;
}
// 返回顺序栈中所有元素的描述字符串，形式为"（,）"，覆盖Object类的toString()方法
public String toString(){
String str="";
Node<T> p=top.next;
if (p!=null){
str="(";
while (p!=null){
str+=p.data+",";
p=p.next;
}
str=str.substring(0,str.length()-1);
str+=")";
}else {
str="()";
}
return str;
}
}
5.括号匹配
package ch07;
import java.util.Scanner;
public class Bracket {
// 括号匹配
public static String isMatched(String infix) {
SeqStack<Character> stack = new SeqStack<Character>(infix.length());
for (int i = 0; i < infix.length(); i++) {
char ch = infix.charAt(i);
switch (ch) {
case '(':
stack.push(ch);
break;
case ')':
if (stack.isEmpty() || !stack.pop().equals('(')) {
return "expect (";
}
}
}
return stack.isEmpty() ? "" : "expect )";
}
// 测试括号匹配算法
public static void main(String[] args) {
// 括号匹配
Scanner r = new Scanner(System.in);
System.out.print("输入括号表达式：");
String infix = r.nextLine();
System.out.println(isMatched(infix));
}
}
6.表达式求值（后缀表达式）：
package ch05;
import java.util.Scanner;
public class ExpressionPoland {
// 括号匹配
public static String isMatched(String infix) {
SeqStack<Character> stack = new SeqStack<Character>(infix.length());
for (int i = 0; i < infix.length(); i++) {
char ch = infix.charAt(i);
switch (ch) {
case '(':
stack.push(ch);
break;
case ')':
if (stack.isEmpty() || !stack.pop().equals('(')) {
return "expect (";
}
}
}
return stack.isEmpty() ? "" : "expect )";
}
// 将中缀表达式转换为后缀表达式
public static StringBuffer toPostfix(String infix){
SeqStack<Character> stack=new SeqStack<Character>(infix.length());
StringBuffer postfix=new StringBuffer(infix.length()*2);
int i=0;
System.out.println("\n求后缀表达式过程：");
System.out.println("字符"+"\tstack\t\tpostfix");
while(i<infix.length()){ // 对表达式中的每个字符进行处理
char ch=infix.charAt(i); // 第i个字符
System.out.print(ch+"\t"); // 输出第i个字符
switch(ch){ // 判断字符类别
// +、-运算符
case '+':
case '-':
// 当栈不空且栈顶运算符优先级高时，包括+、-、*、/
while(!stack.isEmpty() && !stack.peek().equals('(')){ // 栈中的'('优先级最低
postfix.append(stack.pop()+" "); // 将出栈的运算符追加到后缀表达式中（空格间隔）
}
stack.push(ch); // 第i个字符入栈
i++;
break;
case '*':
case '/':
// 当栈不空且栈顶运算符优先级高时，包括*、/
while(!stack.isEmpty() && (stack.peek().equals('*') || stack.peek().equals('/'))){
postfix.append(stack.pop()+" "); // 将出栈的运算符追加到后缀表达式中（空格间隔）
}
stack.push(ch); // 第i个字符入栈
i++;
break;
case '(':
stack.push(ch); // '('入栈
i++;
break;
case ')':
Character out=stack.pop();
while(out!=null && !out.equals('(')){ // 若干运算符出栈，直到'('出栈
postfix.append(out+" "); // 将出栈的运算符追加到后缀表达式中（空格间隔）
out=stack.pop();
}
i++;
break;
default:
while(i<infix.length() && ch>='0' && ch<='9'){ // 获取运算的整数
postfix.append(ch); // 将数字追加到后缀表达式中
i++;
if(i<infix.length()){
ch=infix.charAt(i); // 下一位字符
}
}
postfix.append(" "); // 运算数以空格间隔
}
System.out.printf("%-18s",stack.toString()); // 输出每个运算符或运算数处理后栈中的内容
System.out.println(postfix); // 输出每个运算符或运算数处理后的后缀表达式
}
while(!stack.isEmpty()){ // 栈中运算符全部出栈
postfix.append(stack.pop());
}
return postfix;
}
// 计算后缀表达式的值
public static int toValue(StringBuffer postfix){
LinkedStack<Integer> stack=new LinkedStack<Integer>();
int value=0;
System.out.println("\n计算过程：");
for(int i=0;i<postfix.length();i++){
char ch=postfix.charAt(i);
if(ch>='0' && ch<='9'){
String s="";
while(ch!=' '){// 求运算数
s+=ch;
i++;
ch=postfix.charAt(i);
}
stack.push(Integer.parseInt(s)); // 将运算数入栈
}else{
if(ch!=' '){
int y=stack.pop(); // 第二个运算数
int x=stack.pop(); // 第一个运算数
switch(ch){
case '+':
value=x+y;
break;
case '-':
value=x-y;
break;
case '*':
value=x*y;
break;
case '/':
value=x/y;
break;
}//switch
// 输出计算表达式
if(y>=0){
System.out.println(x+(ch+"")+y+"="+value);
}else{
System.out.println(x+(ch+"")+"("+y+")"+"="+value);
}
// 计算结果入栈
stack.push(value);
}
}
}
return stack.pop(); // 返回栈中计算的最终结果
}
// 测试表达式求值算法
public static void main(String[] args) {
Scanner r=new Scanner(System.in);
// 表达式求值
System.out.print("输入表达式：");
String infix = r.nextLine();
String match=isMatched(infix);
if(match.equals("")){// 括号匹配
StringBuffer postfix=toPostfix(infix);
System.out.println("\n后缀表达式:"+postfix);
System.out.println("\n计算结果："+toValue(postfix));
}else{// 括号不匹配
System.out.println("表达式错误："+match);
}
}
}
运行结果如下：
到此这篇关于java数据结构关于栈的实例应用的文章就介绍到这了,更多相关java数据结构内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
java数据结构基础:栈
目录 准备工作 编码环节 push方法 pop方法 empty方法 全部代码 总结 准备工作 工具:idea+jdk8 技术要求:java基础语法 编码环节 首先,我们得先确定下来,用什么数据来模拟栈的操作.由于是一个一个的元素放入栈里面,我们可以考虑用数组来实现. 以上是Java官方文档中的栈定义,我们也只需要实现三个方法:判断是否为空.移除栈顶对象.添加元素到栈的尾部 所以我们事先得定义一个数组: Objects[] arr; 数组定义好了之后呢,想想,我们怎么去获取到栈尾部或者栈首的元素呢
-
Java数据结构之栈与队列实例详解
目录 一,栈 1,概念 2,栈的操作 3,栈的实现 4,实现mystack 二,队列 1,概念 2,队列的实现 3,实现myqueue 栈.队列与数组的区别? 总结 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页. 很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作,也是用栈这种方式来实现的,当然不同的
-
简单谈谈Java中的栈和堆
人们常说堆栈堆栈,堆和栈是内存中两处不一样的地方,什么样的数据存在栈,又是什么样的数据存在堆中? 这里浅谈Java中的栈和堆 首先,将结论写在前面,后面再用例子加以验证. Java的栈中存储以下类型数据,栈对应的英文单词是Stack 基本类型 引用类型变量 方法 栈的优势是,存取速度比堆要快,仅次于寄存器,栈数据可以共享.但缺点是,存在栈中的数据大小与生存期必须是确定的,缺乏灵活性. 栈中主要存放一些基本类型的变量(int, short, long, byte, float, double, b
-
java数据结构关于栈的实例应用
此文章介绍关于顺序栈,链式栈的实例操作,括号匹配,表达式求值(后缀表达式) 1.声明一个栈接口SStack package ch05; public interface SStack <T>{ boolean isEmpty(); // 判断栈是否为空 void push(T x); // 元素x入栈 T pop(); // 出栈,返回栈顶元素 T peek(); // 返回栈顶元素,但不出栈 } 2. 定义顺序栈类SeqStack<T>,包括数据元素的对象数组和栈顶元素下标两个
-
Java数据结构之栈的基本定义与实现方法示例
本文实例讲述了Java数据结构之栈的基本定义与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.基本概念: 栈是一种数据结构,是只能在某一端插入和删除的特殊线性表.它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来). 栈是允许在同一端进行插入和删除操作的特殊线性表.允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom):栈底固定,而栈顶 浮动:栈中元素个数为零时称为空栈.插入一般
-
java 数据结构之栈与队列
java 数据结构之栈与队列 一:对列 队列是一种先进先出的数据结构 实现代码: package Queue; /* * 使用java构建队列,并模拟实现队列的入队和出对方法 */ public class Queue { //队列类 private int maxSize; //定义队列的长度 private int[] arrQueue; //队列 private int rear; //定义队列的尾指针 private int front; //定义队列的头指针 private int e
-
Java数据结构之栈的线性结构详解
目录 一:栈 二:栈的实现 三:栈的测试 四:栈的应用(回文序列的判断) 总结 一:栈 栈是限制插入和删除只能在一个位置上进行的表,此位置就是表的末端,叫作栈顶. 栈的基本操作分为push(入栈) 和 pop(出栈),前者相当于插入元素到表的末端(栈顶),后者相当于删除栈顶的元素. 二:栈的实现 public class LinearStack { /** * 栈的初始默认大小为10 */ private int size = 5; /** * 指向栈顶的数组下标 */ int top = -1
-
JS中的算法与数据结构之栈(Stack)实例详解
本文实例讲述了JS中的算法与数据结构之栈(Stack).分享给大家供大家参考,具体如下: 栈(Stack) 上一篇我们说到了列表,它是一种最自然的数据组织方式,如果对数据的存储顺序要求不重要,那么列表就是一种非常适合的数据结构,但对于计算机其他的一些应用(比如后缀表达式),那么列表就显得有些无能为力, 所以,我们需要一种和列表功能相似但更复杂的数据结构. 栈,又叫堆栈,是和列表类似的一种数据结构,但是却更高效,因为栈内的元素只能通过列表的一端访问,称为栈顶,数据只能在栈顶添加或删除,遵循 先入后
-
Java数据结构与算法入门实例详解
第一部分:Java数据结构 要理解Java数据结构,必须能清楚何为数据结构? 数据结构: Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系. 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构. 而一个数据结构的设计过程分成抽象层.数据结构层和实现层. 数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构. 一.Java数据结构之:线性数据结构 线性数据结构:常见的
-
JAVA 数据结构之Queue处理实例代码
java Queue处理 实例代码: import java.util.LinkedList; import java.util.Queue; private static Queue<FrameStruct> frameQueue = new LinkedList<FrameStruct>(); private static Lock lock = new ReentrantLock(); private PlayerThread p = new PlayerThread();
-
Java数据结构之栈的详解
目录 栈的抽象定义 顺序栈-----------使用数组表示栈空间 总结 栈是先进后出的特殊线性表,只允许在表的末端进行插入和删除,后面将介绍两种实现栈的方式,分别是基于数组的实现.基于链表的实现. 栈的抽象定义 class Mystack { public: Mystack() {} virtual void push(int &x) = 0; virtual bool pop(int &x) = 0; virtual bool Top(int &x) const = 0; vi