文章來(lái)源于公眾號(hào)：Java中文社群 作者：磊哥
隨著軟件開(kāi)發(fā)行業(yè)競(jìng)爭(zhēng)的日益激烈，面試的難度也在逐漸增加，因?yàn)槠髽I(yè)要從眾多的面試人中選出最優(yōu)秀的人，只能提高面試的難度，而算法和數(shù)據(jù)結(jié)構(gòu)比較燒腦的硬核技能之一，自然也就成了面試的首選科目。并且隨著時(shí)間的推移，算法和數(shù)據(jù)結(jié)構(gòu)出現(xiàn)的頻率和占比也會(huì)不斷增加，因此為了順應(yīng)時(shí)代發(fā)展的潮流，我們也要做一些調(diào)整，所以在后面的一些文章中，我會(huì)陸續(xù)更新一些關(guān)于算法和數(shù)據(jù)結(jié)構(gòu)的文章，希望大家能夠喜歡。
PS：當(dāng)然隨著智能系統(tǒng)的普及（如今日頭條和抖音），算法和數(shù)據(jù)結(jié)構(gòu)在企業(yè)中應(yīng)用也越來(lái)越多，因此學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)也是迫在眉睫的事了。
棧定義
棧（Stack）又叫堆棧（簡(jiǎn)稱棧），它是在同一端進(jìn)行插入和刪除數(shù)據(jù)的線性表。
棧是最基礎(chǔ)也是最常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)之一，它的數(shù)據(jù)結(jié)構(gòu)和操作流程如下圖所示：
其中，允許進(jìn)行插入和刪除的一端叫作棧頂（Top），另一端叫作棧底（Bottom），棧底固定，棧頂浮動(dòng)。
當(dāng)棧中的元素為零時(shí)，該棧叫作空棧。添加數(shù)據(jù)時(shí)一般叫作入?；蜻M(jìn)棧（Push），刪除數(shù)據(jù)叫作出?；蛲藯＃≒op）。棧是后進(jìn)先出（Last In First Out，LIFO）的線性表。
物理結(jié)構(gòu) & 邏輯結(jié)構(gòu)
在手?jǐn)]算法之前，我們先來(lái)認(rèn)識(shí)一下數(shù)據(jù)結(jié)構(gòu)中的兩個(gè)重要概念：物理結(jié)構(gòu)和邏輯結(jié)構(gòu)。
當(dāng)談到“物理”和“邏輯”一詞時(shí)，我們可以會(huì)想到數(shù)據(jù)庫(kù)中的邏輯刪除和物理刪除。
所謂的物理刪除是指通過(guò)刪除命令真實(shí)的將數(shù)據(jù)從物理結(jié)構(gòu)中刪除的過(guò)程；而邏輯刪除是指通過(guò)修改命令將數(shù)據(jù)更改為“已刪除”的狀態(tài)，并非真實(shí)的刪除數(shù)據(jù)。
這里的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)和上面的概念類似，所謂的物理結(jié)構(gòu)是指可以將數(shù)據(jù)存儲(chǔ)在物理空間中，比如數(shù)組和鏈表都屬于物理數(shù)據(jù)結(jié)構(gòu)；而邏輯結(jié)構(gòu)則是用于描述數(shù)據(jù)間的邏輯關(guān)系的，比如本文要講的棧就屬于邏輯結(jié)構(gòu)。
可能有些人看到這里就蒙了，沒(méi)關(guān)系，我這里舉一個(gè)例子你就明白了。
如果用人來(lái)表示物理結(jié)構(gòu)和邏輯結(jié)構(gòu)的話，那么真實(shí)存在的有血有肉的人就屬于物理結(jié)構(gòu)，而人的思想和信念就屬于邏輯結(jié)構(gòu)了。
自定義棧I：數(shù)組實(shí)現(xiàn)
通過(guò)上面的內(nèi)容，我們知道了棧屬于邏輯結(jié)構(gòu)，因此它的實(shí)現(xiàn)方式就可以有很多種了，比如數(shù)組的實(shí)現(xiàn)方式或者是鏈表的實(shí)現(xiàn)方式。那么我們就先用數(shù)組實(shí)現(xiàn)一下，棧的主要方法有：
① 定義結(jié)構(gòu)
那么我們先來(lái)定義它的結(jié)構(gòu)：
public class MyStack {
private Object[] value = null; // 棧存儲(chǔ)容器
private int top = -1; // 棧頂（的指針）
private int maxSize = 0; // 棧容量
// 構(gòu)造函數(shù)（初始化默認(rèn)容量）
MyStack() {
this.maxSize = 10;
}
// 有參構(gòu)造函數(shù)
MyStack(int initSize) throws Exception {
if (initSize Hello
從上述代碼可以看出，我們添加棧的順序是 `Hello`、`Java` 而輸出的順序是 `Java`、 `Hello` 符合棧的定義（后進(jìn)先出）。
## 自定義棧II：鏈表實(shí)現(xiàn)
除了數(shù)組之外，我們可以還可使用鏈表來(lái)實(shí)現(xiàn)棧結(jié)構(gòu)，它的實(shí)現(xiàn)稍微復(fù)雜一些，我們先來(lái)看鏈表本身的數(shù)據(jù)結(jié)構(gòu)：
使用鏈表實(shí)現(xiàn)棧的流程如下：
也就是說(shuō)，入棧時(shí)我們將數(shù)據(jù)存儲(chǔ)在鏈表的頭部，出棧時(shí)我們從頭部進(jìn)行移除，并將棧頂指針指向原頭部元素的下一個(gè)元素，實(shí)現(xiàn)代碼如下。
我們先來(lái)定義一個(gè)鏈表節(jié)點(diǎn)：
public class Node { Object value; // 每個(gè)節(jié)點(diǎn)的數(shù)據(jù) Node next; // 下一個(gè)節(jié)點(diǎn)
public Node(Object value) { this(value, null); }
/**
- 創(chuàng)建新節(jié)點(diǎn)
- @param value 當(dāng)前節(jié)點(diǎn)數(shù)據(jù)
- @param next 指向下一個(gè)節(jié)點(diǎn)（頭插法）
*/
public Node(Object value, Node next) {
this.value = value;
this.next = next;
}
}
接下來(lái)我們使用鏈表來(lái)實(shí)現(xiàn)一個(gè)完整的棧：
public class StackByLinked {
private Node top = null; // 棧頂數(shù)據(jù)
private int maxSize = 0; // 棧最大容量
private int leng = 0; // 棧實(shí)際容量
public StackByLinked(int initSize) throws Exception {
if (initSize = maxSize;
}
/**
* 是否為空
* @return
*/
public boolean isEmpty() {
return leng Java
>
> Hello
## 總結(jié)
本文我們使用了數(shù)組和鏈表等物理結(jié)構(gòu)來(lái)實(shí)現(xiàn)了棧，當(dāng)然我們也可以使用其他容器來(lái)實(shí)現(xiàn)，比如 [Java](http://www.o2fo.com/java/) 中的 `List`，我們只需要保證在操作棧時(shí)是后進(jìn)先出的執(zhí)行順序，并且至少包含 3 個(gè)重要方法：入棧、出棧和查詢棧頂元素就可以了。
## 最后
**算法和數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)是 3 分學(xué) 7 分練**，只看不練是沒(méi)辦法學(xué)好算法的，而且**學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)是一個(gè)循序漸進(jìn)的過(guò)程，短時(shí)間內(nèi)不會(huì)有明顯的收效**。因?yàn)檫@些算法經(jīng)過(guò)了幾百年的發(fā)展和積累才得以流傳下來(lái)的，所以想要“玩得轉(zhuǎn)”還需要一點(diǎn)耐心。
這里給你講一個(gè)學(xué)習(xí)算法的“秘訣”：**看不懂的知識(shí)要反復(fù)看，如果反復(fù)看還是看不懂，那么別著急，休息一下再繼續(xù)看！**相信我，對(duì)于學(xué)習(xí)算法這件事，所有人的過(guò)程都是一樣的。
以上就是`W3Cschool編程獅`關(guān)于**動(dòng)圖演示：手?jǐn)]堆棧的兩種實(shí)現(xiàn)方法！**的相關(guān)介紹了，希望對(duì)大家有所幫助。
