Java三十一篇：棧
平安春運
棧
棧是一種先進后出的數(shù)據(jù)結(jié)構(gòu)，最后入棧的元素，最先讀取出來。就像向箱子里放書一樣，最后放進去的那本書，我們可以最先從箱子里取出來。
?？梢苑譃殪o態(tài)棧(數(shù)組實現(xiàn))和動態(tài)棧(鏈表實現(xiàn))
Java實現(xiàn)動態(tài)棧
通過鏈表實現(xiàn)棧，我們可以想象有個棧頂節(jié)點，當入棧的時候，原先的棧頂節(jié)點成為新的節(jié)點后繼節(jié)點，新的節(jié)點成為新的棧頂節(jié)點。同理，出棧的時候，講棧頂節(jié)點彈出，第二個節(jié)點成為新的棧頂節(jié)點。
入棧
/**
? ? * 入棧
? ? * @param value
? ? */
? ?public void push(Object value){
? ? ? ?Node pushedNode = new Node(value);
? ? ? ?pushedNode.next = top;
? ? ? ?top = pushedNode;
? ? ? ?size++;
? ?}
出棧
/**
? ? * 出棧
? ? */
? ?public Object pop() throws Exception {
? ? ? ?if(size == 0){
? ? ? ? ? ?thrownew Exception("空棧異常");
? ? ? ?}
? ? ? ?Node popedNode = top;
? ? ? ?top = top.next;
? ? ? ?size --;
? ? ? ?return ?popedNode.data;
? ?}
返回棧頂元素
/**
? ? * 返回棧頂元素
? ? */
? ?public Object peek() throws Exception {
? ? ? ?if(size == 0){
? ? ? ? ? ?thrownew Exception("空棧異常");
? ? ? ?}
? ? ? ?return ?top.data;
? ?}
遍歷棧
/**
? ? * 遍歷棧
? ? */
? ?public void traverse(){
? ? ? ?Node temp = top;
? ? ? ?while (temp != null){
? ? ? ? ? ?System.out.println(""+temp.data);
? ? ? ? ? ?temp = temp.next;
? ? ? ?}
? ?}
Java 實現(xiàn)靜態(tài)棧
通過數(shù)組實現(xiàn)棧，我們可以想象棧頂索引，當入棧的時候，棧頂索引加一，賦值給棧頂。當出棧的時候，返回棧頂?shù)闹?，并且棧頂索引減一。
publicclass ArrayStatck {
? ?private Object[] data;
? ?privateint top;
? ?privateint maxSize;
? ?public ArrayStatck(int maxSize) {
? ? ? ?this.maxSize = maxSize;
? ? ? ?this.top = -1;
? ? ? ?data = new Object[maxSize];
? ?}
? ?/**
? ? * 入棧
? ? * @param value
? ? */
? ?public void push(Object value) throws Exception {
? ? ? ?if(top == maxSize-1){
? ? ? ? ? ?thrownew Exception("棧滿異常");
? ? ? ?}
? ? ? ?data[++top] = value;
? ?}
? ?/**
? ? * 出棧
? ? * @throws Exception
? ? */
? ?public void pop()throws Exception{
? ? ? ?if(top == -1){
? ? ? ? ? ?thrownew Exception("?？债惓?#34;);
? ? ? ?}
? ? ? ?Object value = data[top--];
? ?}
? ?/**
? ? * 遍歷棧
? ? */
? ?public void traverse(){
? ? ? ?while (top != -1){
? ? ? ? ? ?System.out.println(""+data[top--]);
? ? ? ?}
? ?}
}
棧的實際需求
請計算表達式：[722-5+1-5+3-3] 的值
請問: 計算機底層是如何運算得到結(jié)果的？ 注意不是簡單的把算式列出運算，因為我們看這個算式 7 * 2 * 2 - 5，但是計算機怎么理解這個算式的
對計算機而言， 它接收到的就是一個字符串， 我們討論的是這個問題：棧
棧的基本性質(zhì)
棧的英文為(stack)
棧是一個先入后出(FILO-First In Last Out)的有序列表
棧(stack)是限制線性表中元素的插入和刪除只能在線性表的同一端進行的一種特殊線性表。 允許插入和刪除的一端， 為變化的一端， 稱為棧頂(Top)， 另一端為固定的一端， 稱為棧底(Bottom)。
根據(jù)棧的定義可知， 最先放入棧中元素在棧底， 最后放入的元素在棧頂， 而刪除元素剛好相反， 最后放入的元素最先刪除， 最先放入的元素最后刪除
圖解方式說明出棧(pop)和入棧(push)的概念
棧的應用場景
子程序的調(diào)用： 在跳往子程序前， 會先將下個指令的地址存到堆棧中， 直到子程序執(zhí)行完后再將地址取出， 以回到原來的程序中。
處理遞歸調(diào)用： 和子程序的調(diào)用類似， 只是除了儲存下一個指令的地址外， 也將參數(shù)、 區(qū)域變量等數(shù)據(jù)存入棧中。
表達式的轉(zhuǎn)換：[中綴表達式轉(zhuǎn)后綴表達式]與求值(實際解決)。
二叉樹的遍歷。
圖形的深度優(yōu)先(depth 一 first)搜索法。
數(shù)組模擬棧
代碼思路
maxSize ：棧的大小（數(shù)組的大?。?/p>
arr ：用來模擬棧的數(shù)組
top ：指向當前棧頂元素，初始值為 -1 ，表示?？?/p>
判斷棧滿：top == maxSize ，即已經(jīng)到達數(shù)組最后一個位置
判斷?？眨簍op == -1
入棧：arr[++top] = arr;
出棧：return arr[top–] ;
代碼實現(xiàn)
棧的定義
//定義一個 ArrayStack 表示棧
class ArrayStack {
privateint maxSize; // 棧的大小
privateint[] stack; // 數(shù)組，數(shù)組模擬棧，數(shù)據(jù)就放在該數(shù)組
privateint top = -1;// top表示棧頂，初始化為-1
// 構(gòu)造器
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = newint[this.maxSize];
}
// 棧滿
public boolean isFull() {
return top == maxSize - 1;
}
// ?？?br> public boolean isEmpty() {
return top == -1;
}
// 入棧-push
public void push(int value) {
// 先判斷棧是否滿
if (isFull()) {
System.out.println("棧滿");
return;
}
top++;
stack[top] = value;
}
// 出棧-pop, 將棧頂?shù)臄?shù)據(jù)返回
public int pop() {
// 先判斷棧是否空
if (isEmpty()) {
// 拋出異常
thrownew RuntimeException("?？?，沒有數(shù)據(jù)~");
}
int value = stack[top];
top--;
return value;
}
// 顯示棧的情況[遍歷棧]， 遍歷時，需要從棧頂開始顯示數(shù)據(jù)
public void list() {
if (isEmpty()) {
System.out.println("?？眨瑳]有數(shù)據(jù)~~");
return;
}
// 需要從棧頂開始顯示數(shù)據(jù)
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}
測試代碼
public static void main(String[] args) {
? ?// 測試一下ArrayStack 是否正確
? ?// 先創(chuàng)建一個ArrayStack對象->表示棧
? ?ArrayStack stack = new ArrayStack(4);
? ?String key = "";
? ?boolean loop = true; // 控制是否退出菜單
? ?Scanner scanner = new Scanner(System.in);
? ?while (loop) {
? ? ? ?System.out.println("show: 表示顯示棧");
? ? ? ?System.out.println("exit: 退出程序");
? ? ? ?System.out.println("push: 表示添加數(shù)據(jù)到棧(入棧)");
? ? ? ?System.out.println("pop: 表示從棧取出數(shù)據(jù)(出棧)");
? ? ? ?System.out.println();
? ? ? ?System.out.println("請輸入你的選擇");
? ? ? ?key = scanner.next();
? ? ? ?switch (key) {
? ? ? ? ? ?case"show":
? ? ? ? ? ? ? ?stack.list();
? ? ? ? ? ? ? ?break;
? ? ? ? ? ?case"push":
? ? ? ? ? ? ? ?System.out.println("請輸入一個數(shù)");
? ? ? ? ? ? ? ?int value = scanner.nextInt();
? ? ? ? ? ? ? ?stack.push(value);
? ? ? ? ? ? ? ?break;
? ? ? ? ? ?case"pop":
? ? ? ? ? ? ? ?try {
? ? ? ? ? ? ? ? ? ?int res = stack.pop();
? ? ? ? ? ? ? ? ? ?System.out.printf("出棧的數(shù)據(jù)是 %d\n", res);
? ? ? ? ? ? ? ?} catch (Exception e) {
? ? ? ? ? ? ? ? ? ?// TODO: handle exception
? ? ? ? ? ? ? ? ? ?System.out.println(e.getMessage());
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?break;
? ? ? ? ? ?case"exit":
? ? ? ? ? ? ? ?scanner.close();
? ? ? ? ? ? ? ?loop = false;
? ? ? ? ? ? ? ?break;
? ? ? ? ? ?default:
? ? ? ? ? ? ? ?break;
? ? ? ?}
? ?}
? ?System.out.println("程序退出~~~");
}
程序運行結(jié)果
show: 表示顯示棧
exit: 退出程序
push: 表示添加數(shù)據(jù)到棧(入棧)
pop: 表示從棧取出數(shù)據(jù)(出棧)
請輸入你的選擇
push
請輸入一個數(shù)
1
show: 表示顯示棧
exit: 退出程序
push: 表示添加數(shù)據(jù)到棧(入棧)
pop: 表示從棧取出數(shù)據(jù)(出棧)
請輸入你的選擇
push
請輸入一個數(shù)
2
show: 表示顯示棧
exit: 退出程序
push: 表示添加數(shù)據(jù)到棧(入棧)
pop: 表示從棧取出數(shù)據(jù)(出棧)
請輸入你的選擇
push
請輸入一個數(shù)
3
show: 表示顯示棧
exit: 退出程序
push: 表示添加數(shù)據(jù)到棧(入棧)
pop: 表示從棧取出數(shù)據(jù)(出棧)
請輸入你的選擇
push
請輸入一個數(shù)
4
show: 表示顯示棧
exit: 退出程序
push: 表示添加數(shù)據(jù)到棧(入棧)
pop: 表示從棧取出數(shù)據(jù)(出棧)
請輸入你的選擇
push
請輸入一個數(shù)
5
棧滿
show: 表示顯示棧
exit: 退出程序
push: 表示添加數(shù)據(jù)到棧(入棧)
pop: 表示從棧取出數(shù)據(jù)(出棧)
請輸入你的選擇
show
stack[3]=4
stack[2]=3
stack[1]=2
stack[0]=1
show: 表示顯示棧
exit: 退出程序
push: 表示添加數(shù)據(jù)到棧(入棧)
pop: 表示從棧取出數(shù)據(jù)(出棧)
請輸入你的選擇
pop
出棧的數(shù)據(jù)是 4
show: 表示顯示棧
exit: 退出程序
push: 表示添加數(shù)據(jù)到棧(入棧)
pop: 表示從棧取出數(shù)據(jù)(出棧)
請輸入你的選擇
pop
出棧的數(shù)據(jù)是 3
show: 表示顯示棧
exit: 退出程序
push: 表示添加數(shù)據(jù)到棧(入棧)
pop: 表示從棧取出數(shù)據(jù)(出棧)
請輸入你的選擇
pop
出棧的數(shù)據(jù)是 2
show: 表示顯示棧
exit: 退出程序
push: 表示添加數(shù)據(jù)到棧(入棧)
pop: 表示從棧取出數(shù)據(jù)(出棧)
請輸入你的選擇
pop
出棧的數(shù)據(jù)是 1
show: 表示顯示棧
exit: 退出程序
push: 表示添加數(shù)據(jù)到棧(入棧)
pop: 表示從棧取出數(shù)據(jù)(出棧)
請輸入你的選擇
pop
?？?，沒有數(shù)據(jù)~
show: 表示顯示棧
exit: 退出程序
push: 表示添加數(shù)據(jù)到棧(入棧)
pop: 表示從棧取出數(shù)據(jù)(出棧)
請輸入你的選擇
數(shù)組模擬棧全部代碼
publicclass ArrayStackDemo {
public static void main(String[] args) {
// 測試一下ArrayStack 是否正確
// 先創(chuàng)建一個ArrayStack對象->表示棧
ArrayStack stack = new ArrayStack(4);
String key = "";
boolean loop = true; // 控制是否退出菜單
Scanner scanner = new Scanner(System.in);
while (loop) {
System.out.println("show: 表示顯示棧");
System.out.println("exit: 退出程序");
System.out.println("push: 表示添加數(shù)據(jù)到棧(入棧)");
System.out.println("pop: 表示從棧取出數(shù)據(jù)(出棧)");
System.out.println();
System.out.println("請輸入你的選擇");
key = scanner.next();
switch (key) {
case"show":
stack.list();
break;
case"push":
System.out.println("請輸入一個數(shù)");
int value = scanner.nextInt();
stack.push(value);
break;
case"pop":
try {
int res = stack.pop();
System.out.printf("出棧的數(shù)據(jù)是 %d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case"exit":
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~~");
}
}
//定義一個 ArrayStack 表示棧
class ArrayStack {
privateint maxSize; // 棧的大小
privateint[] stack; // 數(shù)組，數(shù)組模擬棧，數(shù)據(jù)就放在該數(shù)組
privateint top = -1;// top表示棧頂，初始化為-1
// 構(gòu)造器
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = newint[this.maxSize];
}
// 棧滿
public boolean isFull() {
return top == maxSize - 1;
}
// ?？?br> public boolean isEmpty() {
return top == -1;
}
// 入棧-push
public void push(int value) {
// 先判斷棧是否滿
if (isFull()) {
System.out.println("棧滿");
return;
}
top++;
stack[top] = value;
}
// 出棧-pop, 將棧頂?shù)臄?shù)據(jù)返回
public int pop() {
// 先判斷棧是否空
if (isEmpty()) {
// 拋出異常
thrownew RuntimeException("?？眨瑳]有數(shù)據(jù)~");
}
int value = stack[top];
top--;
return value;
}
// 顯示棧的情況[遍歷棧]， 遍歷時，需要從棧頂開始顯示數(shù)據(jù)
public void list() {
if (isEmpty()) {
System.out.println("棧空，沒有數(shù)據(jù)~~");
return;
}
// 需要從棧頂開始顯示數(shù)據(jù)
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}
