??棧(Stack)
??棧的概念
??棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。
棧中的數(shù)據(jù)元素遵守后進先出LIFO（Last In First Out）的原則
-
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
-
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)在棧頂。
-
比如下面數(shù)據(jù)的出棧與進棧
就像槍的彈匣一樣，先壓進去的子彈，最后出來
??棧的使用
在java中，提供了這些方法用于操作棧
使用如下：
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> s = new Stack();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
System.out.println(s.size()); // 獲取棧中有效元素個數(shù)---> 4
System.out.println(s.peek()); // 獲取棧頂元素---> 4
s.pop(); // 4出棧，棧中剩余1 2 3，棧頂元素為3
System.out.println(s.pop()); // 3出棧，棧中剩余1 2 棧頂元素為3
if(s.empty()){
System.out.println("棧為空");
}else{
System.out.println(s.size());
}
}
}
?? 棧的模擬實現(xiàn)
從下圖中可以看到，Stack繼承了Vector，Vector和ArrayList類似，都是動態(tài)的順序表，不同的是Vector是線程安全的
接下來我們模擬實現(xiàn)一個棧
??棧的創(chuàng)建
我們創(chuàng)建一個MyStack的類，用于模擬實現(xiàn)我們的棧
-
我們的這里的模擬棧用數(shù)組的形式給大家呈現(xiàn)
-
創(chuàng)建一個int型的elem數(shù)組
-
再創(chuàng)建一個usedSize的常數(shù)，用于記錄棧中元素個數(shù)
-
-
再給一個構(gòu)造方法，構(gòu)造棧初始的長度
代碼實現(xiàn)如下：
public class MyStack {
public int[] elem;
public int usedSize;
public MyStack() {
this.elem = new int[10];
}
}
??棧是否為空
若usedSize為0則為空，所以直接比較返回就好
代碼實現(xiàn)如下
public boolean isEmpty() {
return usedSize == 0;
}
??壓棧
做法如下：
- 首先對現(xiàn)有棧進行判斷是否為滿，若滿則需要進行擴容
- 若沒有滿，則只需要將該元素放在數(shù)組elem下標為usedSize的位置
- 然后usedSize加一即可
代碼實現(xiàn)如下：
//壓棧
public void push(int val) {
if(isFull()) {
//擴容
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++] = val;
}
public boolean isFull() {
return usedSize == elem.length;
}
??出棧
做法如下：
- 首先得判斷棧是否為空，若為空我們需要拋出異常
- 這里我們自定義一個異常為EmptyException如下
public class EmptyException extends RuntimeException{
public EmptyException() {
}
public EmptyException(String message) {
super(message);
}
}
- 若不為空，則usedSize變?yōu)?mark>usedSize-1
- 然后返回usedSize下標的元素即可
代碼實現(xiàn)如下：
//出棧
public int pop() {
if(isEmpty()) {
throw new EmptyException("棧是空的！");
}
return elem[--usedSize];
}
public boolean isEmpty() {
return usedSize == 0;
}
??獲取棧頂元素
做法如下：
- 我們同樣需要對棧進行是否為空的判斷
- 若為空，拋出我們自定義棧為空的異常EmptyException
- 若不為空，則返回數(shù)組elem下標為usedSize-1的元素
代碼實現(xiàn)如下：
public int peek() {
if(isEmpty()) {
throw new EmptyException("棧是空的！");
}
return elem[usedSize-1];
}
??MyStack完整代碼實現(xiàn)
import java.util.Arrays;
public class MyStack {
public int[] elem;
public int usedSize;
public MyStack() {
this.elem = new int[10];
}
//壓棧
public void push(int val) {
if(isFull()) {
//擴容
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++] = val;
}
public boolean isFull() {
return usedSize == elem.length;
}
//出棧
public int pop() {
if(isEmpty()) {
throw new EmptyException("棧是空的！");
}
return elem[--usedSize];
}
public boolean isEmpty() {
return usedSize == 0;
}
public int peek() {
if(isEmpty()) {
throw new EmptyException("棧是空的！");
}
return elem[usedSize-1];
}
}
自定義異常
public class EmptyException extends RuntimeException{
public EmptyException() {
}
public EmptyException(String message) {
super(message);
}
}
??概念區(qū)分（棧、虛擬機棧、棧幀）
棧（stack） ：是只允許在一端進行插入或刪除的線性表，滿足后入先出的特點。
虛擬機棧 ：邏輯結(jié)構(gòu)，是具有特殊作用的一塊內(nèi)存空間 。 主管Java程序的運行，它保存方法的局部變量 (8種基本數(shù)據(jù)類型、對象的引用地址)、部分結(jié)果，并參與方法的調(diào)用和返回。
棧幀 ：函數(shù)從調(diào)用過程到結(jié)束的體現(xiàn)，一個函數(shù)從調(diào)用到銷毀其中占用的空間，內(nèi)部的局部變量統(tǒng)一放在棧幀中。 每個函數(shù)在運行時，jvm都會創(chuàng)建一個棧幀，然后將棧幀壓入到虛擬機棧中，當函數(shù)調(diào)用結(jié)束時，該函數(shù)對應(yīng)的棧幀會從虛擬機棧中出棧。文章來源：http://www.zghlxwxcb.cn/news/detail-675189.html
?總結(jié)
關(guān)于《 【數(shù)據(jù)結(jié)構(gòu)】 棧（Stack）與棧的模擬實現(xiàn)》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評指正，如果文章對您有幫助或者覺得作者寫的還不錯可以點一下關(guān)注，點贊，收藏支持一下！文章來源地址http://www.zghlxwxcb.cn/news/detail-675189.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】 棧（Stack）與棧的模擬實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
