目錄
鏈式存盤 (鏈堆疊)
基本運算實作
堆疊的應用舉例
圓括號匹配檢驗
字串回文的判斷
數制轉換
鏈式存盤 (鏈堆疊)
概述：插入和洗掉限制在表頭位置(堆疊頂)進行，將單鏈表的頭指標head改為堆疊頂指標top即可，
圖示：
基本運算實作
//鏈表結點類
public class Node {
//資料域
private Object data;
//指標域
private Node next;
public Node() {
}
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}public class StackNode {
//定義頭指標
Node top = null;
//定義鏈堆疊長度
int size;
//判堆疊空
public boolean StackEmpty(){
return size == 0;
}
//進堆疊（入堆疊）
public void Push(Object x){
//申請新結點
Node n = new Node();
//資料域賦值
n.setData(x);
//新結點插入堆疊頂
n.setNext(top);
//top指向新的堆疊頂
top = n;
//鏈表長度加1
size++;
}
//退堆疊（出堆疊）
public Object Pop(){
//保存堆疊頂指標
Node node = top;
if (StackEmpty()){
System.out.println("stack empty!");
return null;
}else {
//保存洗掉的結點值
Object x = node.getData();
//堆疊頂指標指向下一個結點
top = node.getNext();
//鏈表長度減1
size--;
//回傳被洗掉的元素值
return x;
}
}
//遍歷堆疊
public void StackNodeShow(){
//定義一個新結點
Node node = top;
for (int i = 0; i < size; i++) {
System.out.println(node.getData());
//移動新結點
node = node.getNext();
}
}
//取堆疊頂元素
public Object GetTop() {
//判斷是否堆疊空
if (StackEmpty()) {
System.out.println("stack empty!");
return null;
} else return top.getData();
}
}public class StackNodeTest {
public static void main(String[] args) {
//創建鏈堆疊
StackNode stackNode = new StackNode();
//判堆疊空
boolean b = stackNode.StackEmpty();
System.out.println("堆疊是否為空：" + b);
System.out.println();
//進堆疊（入堆疊）
stackNode.Push("xx");
stackNode.Push("hh");
stackNode.Push("zz");
stackNode.Push("kk");
//遍歷堆疊
System.out.println("遍歷堆疊(先進后出)：");
stackNode.StackNodeShow();
//取堆疊頂元素
Object o = stackNode.GetTop();
System.out.println("堆疊頂元素為："+o);
System.out.println("鏈表長度為："+stackNode.size);
System.out.println();
//退堆疊（出堆疊）
stackNode.Pop();
stackNode.Pop();
//遍歷堆疊
System.out.println("遍歷堆疊(先進后出)：");
stackNode.StackNodeShow();
//取堆疊頂元素
Object o1 = stackNode.GetTop();
System.out.println("堆疊頂元素為："+o1);
System.out.println("鏈表長度為："+stackNode.size);
}
}
運行結果：
堆疊的應用舉例
圓括號匹配檢驗
說明：對于輸入的一個算術運算式字串，該演算法用于判斷其中圓括號是否匹配，匹配回傳True，否則回傳False，
實作思路：回圈讀入運算式中的字符，如遇左括號 “(” 就進堆疊，遇右括號 ”)“ 則判斷是否為空，若為空，回傳False，否則退堆疊；回圈結束后再判斷堆疊是否為空，若堆疊空說明括號匹配，否則說明不匹配，
代碼實作：基于上邊定義的鏈堆疊實作的，
public class StackNodeTest { public static void main(String[] args) { String s = "(15+36)*(4*5)"; boolean expr = Expr(s); System.out.println("括號是否合法：" + expr); String s1 = "(15)+36(()*(4*5)"; boolean expr1 = Expr(s1); System.out.println("括號是否合法：" + expr1); } public static boolean Expr(String s) { //創建一個鏈堆疊 StackNode stackNode = new StackNode(); //回圈字串 for (int i = 0; i < s.length(); i++) { //遇到左括號進堆疊 if (s.charAt(i) == '(') { stackNode.Push(s.charAt(i)); } else if (s.charAt(i) == ')') { //判堆疊空 if (stackNode.StackEmpty()) { //結束運行 System.exit(0); } else stackNode.Pop(); //遇右括號退堆疊 } } if (stackNode.StackEmpty()) return true; else return false; } }運行結果：
字串回文的判斷
說明：判斷一個字串是否具有中心對稱，正讀和反讀均相同的字符序列，例如：ababbbaba和 abcba都是中心對稱的字串，
實作思路：首先要知道中心在哪，從中間向兩頭進行比較，若完全相同，則該字串是中心對稱，否則不是，首先求出字串的長度，然后將前一半字符入堆疊，再利用退堆疊操作將其與后一半字符進行比較，
代碼實作：基于上邊定義的鏈堆疊實作的，
public class StackNodeTest { public static void main(String[] args) { String s = "abcdaad"; boolean symmetry = symmetry(s); System.out.println("是否是回文字串：" + symmetry); String s1 = "ababbaba"; boolean symmetry1 = symmetry(s1); System.out.println("是否是回文字串：" + symmetry1); } public static boolean symmetry(String s) { //創建一個鏈堆疊 StackNode stackNode = new StackNode(); //回圈字串長度的一半 for (int i = 0; i < s.length() / 2; i++) { //前一半字符入堆疊 stackNode.Push(s.charAt(i)); } //后一半字符在串中的起始位置 int k = (s.length() + 1) / 2; //后一半字符與堆疊中字符比較 for (int i = k; i < s.length(); i++) { //退堆疊依次獲取元素,如果有不相同的字符就是不對稱 if ((char) stackNode.Pop() != s.charAt(i)) return false; } return true; } }運行結果：
數制轉換
說明：將一個非負的十進制整數N轉換成d進制，原理：N = (N/d)*d + N%d，解該題的前提是要會各個進制之間的轉換，如果有不懂或者忘了的小伙伴可以參考博主這篇文章：各個進制的概念與轉換（二、八、十、十六進制）_South.return-CSDN博客
實作思路：將計算程序中得到的d進制數的各位數字順序進堆疊，按出堆疊序列順序輸出得到的數就是十進制數所對應的d進制數，
代碼實作：基于上邊定義的鏈堆疊實作的，
public class StackNodeTest { public static void main(String[] args) { conversion(150, 8); System.out.println(); conversion(150, 16); System.out.println(); System.out.println(); conversion(3553, 8); System.out.println(); conversion(3553, 16); System.out.println(); } //將一個非負的十進制數N轉換成任意的d進制數 public static void conversion(int N, int d) { //創建一個鏈堆疊 StackNode stackNode = new StackNode(); //當N大于1時回圈 while (N > 1) { //取模，獲取余數 stackNode.Push(N % d); N = N / d; } //退堆疊 while (!stackNode.StackEmpty()) { Object pop = stackNode.Pop(); System.out.print(pop); } } }運行結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/350910.html
標籤：java