java數據結構關于棧的實例應用
更新時間：2021年12月22日 08:49:29 作者：小石學編程
大家好，本篇文章主要講的是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;
// 構造方法，創(chuàng)建一個空棧，存儲容量大小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 '-':
// 當棧不空且棧頂運算符優(yōu)先級高時，包括+、-、*、/
while(!stack.isEmpty() && !stack.peek().equals('(')){ // 棧中的'('優(yōu)先級最低
postfix.append(stack.pop()+" "); // 將出棧的運算符追加到后綴表達式中（空格間隔）
}
stack.push(ch); // 第i個字符入棧
i++;
break;
case '*':
case '/':
// 當棧不空且棧頂運算符優(yōu)先級高時，包括*、/
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數據結構內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了java 實現單鏈表逆轉實例代碼的相關資料,需要的朋友可以參考下2017-02-02
這篇文章主要介紹了詳解Java實現單例的五種方式,小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-07-07
Java8中l(wèi)ambda表達式的應用及一些泛型相關知識
這篇文章主要介紹了Java8中l(wèi)ambda表達式的應用及一些泛型相關知識的相關資料2017-01-01
這篇文章主要介紹了Java日期時間格式化操作DateUtils 的整理的相關資料,這里總結了java日期格式化的操作，需要的朋友可以參考下2017-07-07
FreeMarker 是一款?模板引擎： 即一種基于模板和要改變的數據， 并用來生成輸出文本(HTML網頁，電子郵件，配置文件，源代碼等)的通用工具，這篇文章主要介紹了springboot常用語法庫的基本語法,需要的朋友可以參考下2022-12-12
簡單了解JAVA SimpleDateFormat yyyy和YYYY的區(qū)別
這篇文章主要介紹了簡單了解JAVA SimpleDateFormat yyyy和YYYY的區(qū)別,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-03-03
這篇文章主要為大家詳細介紹了SpringMVC如何實現賬號只能在一處登陸，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-03-03
Spring中TransactionSynchronizationManager的使用詳解
這篇文章主要介紹了Spring中TransactionSynchronizationManager的使用詳解,TransactionSynchronizationManager是事務同步管理器,監(jiān)聽事務的操作,來實現在事務前后可以添加一些指定操作,需要的朋友可以參考下2023-09-09
這篇文章主要介紹了Java數組動態(tài)增加容量過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-09-09
這篇文章主要給大家介紹了關于SpringBoot日志注解與緩存優(yōu)化的相關資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2021-10-10