聞理似悟，遇境則迷！！！
堆疊與佇列來說也算是一種特殊的線性表，堆疊的特點是后進先出，佇列的特點是先進先出，
堆疊
堆疊的特點是后進先出，堆疊的操作只有出堆疊和入堆疊（也叫壓堆疊），除此之外，還包含堆疊頂與堆疊底的指向以及堆疊的長度，
因此堆疊的定義如下
public class ZStack {
/**
* 堆疊頂指向
*/
private int top = 0;
/**
* 堆疊底指向
*/
private int bottom = 0;
/**
* 堆疊長度
*/
public int length = 0;
/**
* 堆疊內資料
*/
private Object[] datas;
/**
* 堆疊內最大空間
*/
public int MAX_SIZE = 100;
/**
* 出堆疊
*
* @return
*/
public Object pop() {
// 堆疊頂與堆疊底指向同一個位置
if (top == 0) {
return null;
} else {
// 堆疊頂下移
top--;
// 取出堆疊頂資料
Object data = datas[top];
// 堆疊頂置為空
datas[top] = null;
length--;
return data;
}
}
/**
* 入堆疊
*
* @param o
*/
public void push(Object o) {
if (top < MAX_SIZE){
datas[top] = o;
top++;
length++;
}else {
throw new OutOfMemoryError("堆疊已滿，不能再加了");
}
}
// 初始化堆疊
public ZStack() {
// 默認堆疊長度為100
datas = new Object[MAX_SIZE];
}
}
進制轉換（十進制轉二進制）
將十進制轉為二進制
第一步，將該數除以二，取余，將余數入堆疊
第二步，重復第一步，直到最后除數為0或者1
第三步，依次出堆疊，最后的順序就是二進制數
例如 11轉為二進制
11 %2 = 5.,…1
5 % 2 = 2…1
2 % 2 =1…0
入堆疊順序 1 1 0 1，最后輸出 1 0 1 1，驗證一下，1 + 2 +0 +8 = 11
核心代碼如下
// 初始化堆疊
ZStack zStack = new ZStack();
while (num > 0) {
// 余數入堆疊
zStack.push(num % 2);
num = num / 2;
if (num == 1) {
zStack.push(num);
num = 0;
}
}
// 出堆疊，列印出二進制內容
StringBuffer sb =new StringBuffer();
while (zStack.length > 0) {
sb.append(zStack.pop());
}
中綴運算式轉后綴運算式
逆波蘭運算式就是后綴運算式，舉個例子吧，我們要計算1+（2-3）*4，轉為后綴運算式就是 1 2 3 - 4 * +，怎么來的呢
計算規則如下：
第一步，如果是數字，直接輸出
第二步，如果是運算式符號，入堆疊，入堆疊需要對符號優先級進行判斷，如果當前運算子優先級小于堆疊頂元素，需要先出堆疊頂元素，然后再入堆疊
第三步，如果是（，直接入堆疊，
第四步，如果是），依次出堆疊，直到遇到（或者堆疊為空
第五步，將堆疊內剩余符號出堆疊
例子，
1>>> 堆疊 []，輸出（1）
+>>>堆疊[+]，輸出（1）
（>>>堆疊[+ ,（ ]，輸出（1）
2>>>堆疊[+ ,（ ]，輸出（1 2）
->>>堆疊[+ ,（ ,- ]，輸出（1 2）
3>>>堆疊[+ ,（, - ]，輸出（1 2 3）
）>>> 堆疊[+]，輸出（1 2 3 -）
× >>> 堆疊[+,×]，輸出（1 2 3 -）
4 >>> 堆疊[+,×]，輸出（1 2 3 - 4）
最后輸出（1 2 3 - 4 + ×）
1+（2*3 - 4）/ 1
1>>> 堆疊 []，輸出（1）
+>>>堆疊[+]，輸出（1）
（>>>堆疊[+ ,（ ]，輸出（1）
2>>>堆疊[+ ,（ ]，輸出（1 2）
× >>>堆疊[+ ,（，× ]，輸出（1 2）
3 >>>堆疊[+ ,（，× ]，輸出（1 2 3）
_ >>>堆疊[+ ,（，- ]，輸出（1 2 3 ×）注意，×出堆疊了
4 >>>堆疊[+ ,（，- ]，輸出（1 2 3 × 4）
） >>>堆疊[+ ]，輸出（1 2 3 × 4 -）
/ >>>堆疊[+ ,/ ]，輸出（1 2 3 × 4 -）
1>>>堆疊[+ ,/ ]，輸出（1 2 3 × 4 -1）
最后輸出1 2 3 × 4 -1/+
驗證
核心代碼
private static String parseSuffixExpression(String next) {
StringBuffer suffixSb = new StringBuffer();
char[] chars = next.toCharArray();
ZStack zStack = new ZStack();
for (int i = 0; i < chars.length; i++) {
char thisChar = chars[i];
// 判斷字符是否是數字，如果是數字，直接輸出
if (Character.isDigit(thisChar)) {
suffixSb.append(thisChar);
} else if (thisChar == ')') {
/**
* 當入堆疊時是）時，堆疊為空時依次出堆疊，堆疊不為空依次出堆疊，直到遇到（停止
*/
// 堆疊為空
if (zStack.length == 0) {
zStack.push(thisChar);
} else {
Object pop = zStack.pop();
while (pop != null && !String.valueOf(pop).equals("(")) {
suffixSb.append(pop);
pop = zStack.pop();
}
}
} else if (thisChar == '+' || thisChar == '-') {
/**
* 當為+，或者-入堆疊時，需要與堆疊頂元素的優先級比較，優先級高的需要先出堆疊，直到遇到（或者堆疊為空
*/
// 堆疊為空，直接push
if (zStack.length == 0) {
zStack.push(thisChar);
} else {
Object pop = zStack.pop();
while (pop!=null && !String.valueOf(pop).equals("(")){
suffixSb.append(pop);
pop = zStack.pop();
}
/**
* （出堆疊了，需要重新入堆疊，重點
*/
if (String.valueOf(pop).equals("(")){
zStack.push("(");
}
zStack.push(thisChar);
}
} else if (thisChar == '*' || thisChar == '/' || thisChar == '(') {
/**
* 為* ，/，（ 直接入堆疊
*/
zStack.push(thisChar);
} else {
System.err.println("輸入錯誤");
}
}
/**
* 輸出堆疊內其它元素
*/
while (zStack.length!=0) {
suffixSb.append(zStack.pop());
}
return suffixSb.toString();
}
RPN（逆波蘭運算式）
上面介紹了中綴運算式轉后綴運算式（波蘭運算式），這里主要是講波蘭運算式如何計算為我們想要的值，以上面例子講解計算規則
一句來說就是，數字入堆疊，遇到運算子將堆疊頂兩個元素出堆疊，運算后再入堆疊，
例 1 2 3 × 4 -1/+
前3為數字 堆疊 1 2 3
× >>> 堆疊1 6
4 >>>> 堆疊 1 6 4
->>> 1 2
1>>> 1 2 1
/ >>>1 2
＋ 1+2 = 3(結果)
與上圖結果吻合
核心代碼
/**
* 逆波蘭運算式計算器，輸入的是一個波蘭運算式
* @param next
*/
private static void rpn(String next) {
if (!next.isEmpty()) {
ZStack zStack = new ZStack();
char[] chars = next.toCharArray();
for (int i = 0; i < chars.length; i++) {
char thisChar = chars[i];
// 判斷字符是否是數字，如果是數字，就入堆疊
if (Character.isDigit(thisChar)) {
zStack.push(thisChar);
} else {
// 先出的是后面的運算元
Double behind = Double.parseDouble(String.valueOf(zStack.pop()));
Double front = Double.parseDouble(String.valueOf(zStack.pop()));
switch (thisChar) {
case '+':
zStack.push(front + behind);
break;
case '-':
zStack.push(front - behind);
break;
case '*':
zStack.push(front * behind);
break;
case '/':
if (behind == 0) {
throw new NumberFormatException("被除數不能為0");
}
zStack.push(front / behind);
break;
default:
break;
}
}
}
System.out.println(next + "計算結果為：" + zStack.pop());
}
}
這里還有很多bug，例如，只支持10以內的計算（一個字符），還有一些特殊輸入沒有判斷，反正我是比較滿意的，哈哈，
佇列
佇列是一種先進先出的資料結構，就像我們在食堂打飯排隊一樣，每次入佇列都在隊尾操作，每次出佇列就在隊頭操作，使用java代碼實作如下，佇列使用鏈式存盤結構實作比較好，我這里采用的是順序存盤結構，通過隊頭隊尾形成一個環狀佇列，
/**
* 佇列類實作(順序存盤實作)
*/
public class ZQueue {
// 當前佇列長度
private int length = 0;
// 佇列最大長度
private int MAX_SIZE = 5;
// 佇列資料
private Object[] datas;
/**
* 隊頭索引
*/
private int head = 0;
/**
* 隊尾索引
*/
private int tail = 0;
/**
* 出佇列操作
*
* @return
*/
public Object delete() {
Object returnObj = new Object();
if (head == tail) {
if (datas[head] == null) {
System.err.println("佇列已空，不能出佇列");
;
} else {
returnObj = datas[head];
datas[head] = null;
}
} else {
/**
* 佇列頭置為空，將頭往后移
*/
returnObj = datas[head];
datas[head] = null;
head = (head + 1) % MAX_SIZE;
}
length--;
return returnObj;
}
/**
* 入佇列操作
*/
public void add(Object obj) {
if (length == MAX_SIZE) {
System.err.println("佇列已滿，不能入隊");
} else {
// 隊尾累加，如果到頂了，頭尾相接，再從頭開始，形成一個回圈佇列
datas[tail++ % MAX_SIZE] = obj;
length++;
}
}
public ZQueue() {
this.datas = new Object[MAX_SIZE];
}
}
主類
ZQueue zQueue = new ZQueue();
zQueue.add("1");
zQueue.add("2");
zQueue.delete();
zQueue.add("3");
zQueue.add("4");
zQueue.add("5");
zQueue.add("6");
Object delete = zQueue.delete();
zQueue.add("7");
運行結果
以上就是堆疊與佇列相關的操作，最后附上git地址: https://gitee.com/zhoujie1/data-structure-and-algorithm.git
順便提一個有趣的事情，昨天一前端同事問道將一堆陣列平均分成3份的問題，當時我腦海里閃過通過通過快慢指標的方式，定義3個指標，一個指標每次+1，一個指標每次+2，一個指標每次+3，當走得最快的指標到達陣列結尾，剩余兩個指標的位置就將整個資料分成了3份，從而達到了目的，此時我也深深的感受到了演算法的魅力，也堅定了我往下走的決心，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/241311.html
標籤：java
上一篇：Java入門