動(dòng)圖演示：手?jǐn)]堆棧的兩種實(shí)現(xiàn)方法！
本文轉(zhuǎn)載自微信公眾號(hào)「Java中文社群」，作者磊哥 。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java中文社群公眾號(hào)。
正式開(kāi)始之前，先和各位朋友聊聊公眾號(hào)后期的一些打算，后面的文章計(jì)劃寫一些關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的內(nèi)容，原因很簡(jiǎn)單「底層結(jié)構(gòu)決定上層建筑嘛」，對(duì)于框架滿天飛的今天，我們不止要學(xué)習(xí)如何使用框架，更要了解它的原理以及底層數(shù)據(jù)結(jié)構(gòu)，只有這樣我們才能更好的應(yīng)用它。
當(dāng)然，除了上述原因之外，還有一個(gè)重要因素是為了搞定面試。
隨著軟件開(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í)一般叫作入棧或進(jìn)棧(Push)，刪除數(shù)據(jù)叫作出棧或退棧(Pop)。棧是后進(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<E> {
- 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 <= 0) {
- throw new Exception("棧容量必須大于 0");
- } else {
- value = new Object[initSize];
- maxSize = initSize;
- top = -1;
- }
- }
- }
其中棧中數(shù)據(jù)會(huì)存儲(chǔ)在 Object[] value 數(shù)組中，top 變量代表?xiàng)ｍ數(shù)闹羔槪鋵?shí)存儲(chǔ)的是棧頂元素的下標(biāo)，會(huì)隨著入棧不斷變化(后進(jìn)先出)，maxSize 表示棧的最大容量。
② 入棧
此方法是給棧添加數(shù)據(jù)的，實(shí)現(xiàn)代碼如下：
- // 入棧（數(shù)據(jù)添加）
- public boolean push(E e) throws Exception {
- if (maxSize - 1 == top) {
- throw new Exception("入棧失敗，棧已滿");
- } else {
- value[++top] = e;
- return true;
- }
- }
每次當(dāng)有數(shù)據(jù)插入時(shí)，只需在數(shù)組中添加一個(gè)值，并將棧頂?shù)南聵?biāo) +1 即可。
入棧操作如下圖所示：
③ 出棧
此方法是刪除棧中的數(shù)據(jù)的，實(shí)現(xiàn)代碼如下：
- // 數(shù)據(jù)移除（出棧）
- public E pop() throws Exception {
- if (top <= -1) {
- throw new Exception("移除失敗，棧中已無(wú)數(shù)據(jù)");
- } else {
- return (E) value[top--];
- }
- }
出棧只需刪除數(shù)組中棧頂數(shù)據(jù)(最后加入的數(shù)據(jù))，并修改棧頂下標(biāo) -1 即可。
出棧操作如下圖所示：
④ 數(shù)據(jù)查詢
除了以上操作方法之外，我們還需要添加一個(gè)查詢棧頂數(shù)據(jù)的方法：
- // 數(shù)據(jù)查詢
- public E peep() throws Exception {
- if (top <= -1) {
- throw new Exception("移除失敗，棧中已無(wú)數(shù)據(jù)");
- } else {
- return (E) value[top];
- }
- }
⑤ 代碼測(cè)試
到此為止棧的數(shù)據(jù)結(jié)構(gòu)就已經(jīng)實(shí)現(xiàn)完了，接下來(lái)我們來(lái)測(cè)試一下：
- // 代碼測(cè)試
- public static void main(String[] args) throws Exception {
- MyStack stack = new MyStack(10);
- stack.push("Hello");
- stack.push("Java");
- System.out.println(stack.peep());
- stack.pop();
- System.out.println(stack.pop());
- }
以上程序的執(zhí)行結(jié)果為：
Java
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 <= 0) {
- throw new Exception("棧容量不能小于等于0");
- }
- top = null;
- maxSize = initSize;
- leng = 0;
- }
- /**
- * 容量是否已滿
- * @return
- */
- public boolean isFull() {
- return leng >= maxSize;
- }
- /**
- * 是否為空
- * @return
- */
- public boolean isEmpty() {
- return leng <= 0;
- }
- /**
- * 入棧
- * @param val
- * @return
- * @throws Exception
- */
- public boolean push(Object val) throws Exception {
- if (this.isFull()) {
- // 容量已滿
- throw new Exception("容量已滿");
- }
- top = new Node(val, top); // 存入信息，并將當(dāng)前節(jié)點(diǎn)設(shè)置為頭節(jié)點(diǎn)
- leng++;
- return true;
- }
- /**
- * 出棧（移除）
- * @return
- * @throws Exception
- */
- public Node pop() throws Exception {
- if (this.isEmpty()) {
- throw new Exception("棧為空，無(wú)法進(jìn)行移除操作");
- }
- Node item = top; // 返回當(dāng)前元素
- top = top.next;
- leng--;
- return item;
- }
- /**
- * 查詢棧頂信息
- * @return
- */
- public Node peek() throws Exception {
- if (isEmpty()) {
- throw new Exception("你操作的是一個(gè)空棧");
- }
- return top;
- }
- // 代碼測(cè)試
- public static void main(String[] args) throws Exception {
- StackByLinked stack = new StackByLinked(10);
- stack.push("Hello");
- stack.push("Java");
- System.out.println(stack.peek().value);
- stack.pop();
- System.out.println(stack.pop().value);
- }
- }
以上程序的執(zhí)行結(jié)果是：
Java
Hello
總結(jié)
本文我們使用了數(shù)組和鏈表等物理結(jié)構(gòu)來(lái)實(shí)現(xiàn)了棧，當(dāng)然我們也可以使用其他容器來(lái)實(shí)現(xiàn)，比如 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ò)程都是一樣的。
