文章來(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)稱(chēng)棧),它是在同一端進(jìn)行插入和刪除數(shù)據(jù)的線(xiàn)性表。
棧是最基礎(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ù)叫作出棧或退棧(Pop)。棧是后進(jìn)先出(Last In First Out,LIFO)的線(xiàn)性表。
物理結(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)和上面的概念類(lèi)似,所謂的物理結(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)的話(huà),那么真實(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ù)據(jù)結(jié)構(gòu)](https://atts.w3cschool.cn/attachments/image/20200923/1600831705876009.png "鏈表的數(shù)據(jù)結(jié)構(gòu)")
使用鏈表實(shí)現(xiàn)棧的流程如下:
![鏈表實(shí)現(xiàn)棧的流程](https://atts.w3cschool.cn/attachments/image/20200923/1600831725907957.gif "鏈表實(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://m.hgci.cn/java/) 中的 `List`,我們只需要保證在操作棧時(shí)是后進(jìn)先出的執(zhí)行順序,并且至少包含 3 個(gè)重要方法:入棧、出棧和查詢(xún)棧頂元素就可以了。
## 最后
**算法和數(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ì)大家有所幫助。