1.前言：

在計(jì)算機(jī)科學(xué)中，棧（Stack）是一種基礎(chǔ)而存在的數(shù)據(jù)結(jié)構(gòu)，它的核心特性是后進(jìn)先出（LIFO，Last In, First Out）。想象一下，在現(xiàn)實(shí)生活中我們?nèi)绾翁幚硪欢淹斜P(pán)——我們總是將新托盤(pán)放在最上面，而取托盤(pán)時(shí)則從最上面開(kāi)始，這正好與托盤(pán)的操作方式相吻合。

棧的簡(jiǎn)單結(jié)構(gòu)和高效的操作，使得在許多計(jì)算機(jī)程序和算法中扮演關(guān)鍵的角色。從方法調(diào)用、遞歸過(guò)程到表達(dá)求值、短語(yǔ)匹配，棧幾乎暗示在。只允許在前置插入和刪除元素的數(shù)據(jù)結(jié)構(gòu)，不僅能簡(jiǎn)化問(wèn)題的高效初始化過(guò)程，還能提供的性能，尤其是在處理需要回溯和深度優(yōu)先搜索的問(wèn)題時(shí)，堆棧外形更架構(gòu)。

無(wú)論是Smashing初學(xué)者還是豐富的開(kāi)發(fā)者，理解Stack的工作原理及其應(yīng)用，都是構(gòu)建健壯軟件系統(tǒng)的基礎(chǔ)。本文將深入探討Stack的概念、操作以及應(yīng)用場(chǎng)景，并通過(guò)實(shí)例經(jīng)驗(yàn)演示如何在Java中中實(shí)現(xiàn)和使用棧。讓我們一起來(lái)走進(jìn)這個(gè)簡(jiǎn)單但強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，了解它在實(shí)際編程中的巨大價(jià)值。

2.講解棧：

2.1概念：

棧：一種特殊的線(xiàn)性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱(chēng)為棧 頂，另一端稱(chēng)為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。 壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。 出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)在棧頂。

2.2棧的使用：

import java.util.Stack;

public class StackExample {
??? public static void main(String[] args) {
??????? Stack<Integer> stack = new Stack<>();
?????? ?
??????? stack.push(10);? // 入棧
??????? stack.push(20);? // 入棧
??????? stack.push(30);? // 入棧
?????? ?
??????? System.out.println("Top of the stack: " + stack.peek());? // 查看棧頂元素 (30)
?????? ?
??????? System.out.println("Popped element: " + stack.pop());? // 彈出棧頂元素 (30)
?????? ?
??????? System.out.println("Is stack empty? " + stack.isEmpty());? // 判斷棧是否為空 (false)
?????? ?
??????? System.out.println("Size of stack: " + stack.size());? // 查看棧大小 (2)
??? }
}

2.3 棧的模擬實(shí)現(xiàn)：

1.實(shí)現(xiàn)棧前的模擬：

1.private int[] elem;

這行代碼聲明了一個(gè)容器的整型倉(cāng)庫(kù)elem，它用于存儲(chǔ)棧中的元素。在棧中，我們需要一個(gè)容器來(lái)保存被壓入棧的值，因此這里選擇了一個(gè)倉(cāng)庫(kù)。

• 類(lèi)型：int[]表示這是一個(gè)隊(duì)列，用于存儲(chǔ)棧中的數(shù)據(jù)。
• 訪(fǎng)問(wèn)控制：private關(guān)鍵字表示該隊(duì)列只能在MyStack類(lèi)內(nèi)部訪(fǎng)問(wèn)，外部無(wú)法直接訪(fǎng)問(wèn)。

2.private int usedSize;

這行代碼聲明了一個(gè)原始的整型變量usedSize，它用來(lái)記錄棧中當(dāng)前存儲(chǔ)的元素個(gè)數(shù)。

• 類(lèi)型：int，用于表示棧中當(dāng)前的元素個(gè)數(shù)。
• 訪(fǎng)問(wèn)控制：private關(guān)鍵字使得usedSize只能在MyStack類(lèi)內(nèi)部訪(fǎng)問(wèn)，外部無(wú)法直接修改或讀取。

3.private static final int DEFAULT_SIZE = 10;

這行代碼定義了一個(gè)常量DEFAULT_SIZE，它表示棧的最終容量，默認(rèn)為 10。

• 類(lèi)型：int，表示棧的容量大小。
• 訪(fǎng)問(wèn)控制：private關(guān)鍵字表示常量只能在MyStack類(lèi)內(nèi)部使用。
• 修飾符：
  • static：意味著該常量是類(lèi)級(jí)別的，而不是實(shí)例級(jí)別的。那么，所有MyStack類(lèi)的實(shí)例共享這個(gè)常量。
  • final：表示這個(gè)常量的值一旦被賦值后就不能修改。
• 作用：為棧的初始大小提供一個(gè)默認(rèn)值。如果沒(méi)有指定棧的大小，棧的容量將默認(rèn)為10。

4.public MyStack() {

這是MyStack類(lèi)的構(gòu)造方法。構(gòu)造方法是類(lèi)的實(shí)例化時(shí)調(diào)用的特殊方法，用于初始化對(duì)象的狀態(tài)。

• 訪(fǎng)問(wèn)控制：public關(guān)鍵字表示構(gòu)造方法可以被外部類(lèi)訪(fǎng)問(wèn)，否則允許通過(guò)構(gòu)造方法創(chuàng)建MyStack的實(shí)例。
• 方法名：構(gòu)造方法的名稱(chēng)是MyStack，與類(lèi)名相同。

5.elem = new int[DEFAULT_SIZE];

在構(gòu)造方法的主體中，這行代碼用于初始化elem內(nèi)存。

• 隊(duì)列初始化：new int[DEFAULT_SIZE]創(chuàng)建了一個(gè)大小為DEFAULT_SIZE（即10）的內(nèi)存隊(duì)列，并賦予其賦值elem。這表示堆棧一開(kāi)始的容量為10。
• ：棧的最終容量設(shè)為10，當(dāng)棧中的元素數(shù)量小于10時(shí)，棧能夠承載更多元素。當(dāng)元素?cái)?shù)量超過(guò)10時(shí)，通常會(huì)觸發(fā)動(dòng)態(tài)擴(kuò)容。

這需要構(gòu)造方法的結(jié)束。構(gòu)造方法結(jié)束后，MyStack類(lèi)的實(shí)例會(huì)完成初始化，可以開(kāi)始使用棧。

?

2.push添加元素：

public void push(int val) {

• 訪(fǎng)問(wèn)控制：public 關(guān)鍵字表示這個(gè)方法可以被外部類(lèi)調(diào)用，允許用戶(hù)向棧中添加元素。
• 方法名：push 是棧數(shù)據(jù)結(jié)構(gòu)中的常見(jiàn)操作，用于向棧中添加元素。
• 參數(shù)：int val 是棧要添加的元素，它表示一個(gè)整數(shù)，用戶(hù)希望將其壓入棧中。
• 返回類(lèi)型：void 表示這個(gè)方法沒(méi)有返回值。

2. if (isFull()) {

• 這行代碼檢查棧是否已滿(mǎn)。isFull() 是一個(gè)方法，通常用來(lái)判斷棧是否達(dá)到了最大容量。

• isFull()：我們可以推測(cè)它的作用是判斷棧的當(dāng)前容量是否已滿(mǎn)?？赡艿膶?shí)現(xiàn)方式是檢查 usedSize 是否等于棧的當(dāng)前容量 elem.length。如果棧已滿(mǎn)，則 isFull() 返回 true，否則返回 false。

3.grow();

• 這是一個(gè)調(diào)用 grow() 方法的語(yǔ)句，意味著當(dāng)棧滿(mǎn)時(shí)，棧將擴(kuò)容。grow() 是擴(kuò)展棧容量的操作。
• 擴(kuò)容操作：在棧滿(mǎn)時(shí)，我們需要增加棧的容量，通常是通過(guò)創(chuàng)建一個(gè)更大的數(shù)組，并將原數(shù)組的元素復(fù)制到新的數(shù)組中。擴(kuò)容后，?？梢匀菁{更多的元素。

4. elem[usedSize] = val;

• 這行代碼將 val 插入到棧頂。具體來(lái)說(shuō)，它將 val 賦值給 elem[usedSize]，即將 val 存儲(chǔ)到當(dāng)前棧的下一個(gè)可用位置。
• usedSize：在棧未滿(mǎn)時(shí)，usedSize 表示棧中已經(jīng)存儲(chǔ)的元素個(gè)數(shù)，它也可以用作 elem 數(shù)組的下標(biāo)。當(dāng)插入一個(gè)新元素時(shí)，usedSize 會(huì)指向棧的頂部元素的位置。
• 棧的壓棧操作是通過(guò)把元素存儲(chǔ)在 elem[usedSize] 來(lái)實(shí)現(xiàn)的，然后 usedSize 自增，表示棧中元素個(gè)數(shù)增加了。

5. usedSize++;

• 這行代碼執(zhí)行后，usedSize 增加 1，表示棧中元素個(gè)數(shù)增加了一個(gè)。
• usedSize：這個(gè)變量用于追蹤棧中實(shí)際存儲(chǔ)的元素?cái)?shù)量。每當(dāng)我們向棧中壓入一個(gè)元素時(shí)，usedSize 就會(huì)遞增，以保證在后續(xù)操作中可以準(zhǔn)確地知道棧的大小。

3.pop刪除元素：

1.public int pop()：

• 訪(fǎng)問(wèn)控制：public 表示這個(gè)方法對(duì)外可見(jiàn)，可以被其他類(lèi)調(diào)用。
• 返回類(lèi)型：int，表示該方法返回一個(gè)整數(shù)，即棧頂?shù)脑刂怠?/li>
• 方法名：pop 是棧的基本操作之一，表示從棧頂移除元素并返回被移除的元素。

2. if (isEmpty()) {

• 在執(zhí)行 pop 操作之前，方法會(huì)首先檢查棧是否為空，防止對(duì)空棧執(zhí)行彈棧操作。
• isEmpty() 方法：這個(gè)方法通常用于判斷棧是否為空?？赡艿膶?shí)現(xiàn)邏輯是檢查 usedSize 是否為 0：

3. throw new RuntimeException();

• 如果棧為空，直接拋出一個(gè) RuntimeException。
• 異常的目的：防止非法操作（即對(duì)空棧執(zhí)行彈棧操作）。這種設(shè)計(jì)能夠提醒用戶(hù)修復(fù)程序中潛在的問(wèn)題。
• 替代方案：注釋中的代碼顯示了一種替代方式，即返回一個(gè)特殊值（如 -1）來(lái)表示操作失敗。然而，拋出異常更加嚴(yán)謹(jǐn)，因?yàn)榉祷靥厥庵悼赡軐?dǎo)致邏輯混淆（-1 可能與有效數(shù)據(jù)沖突）。

4. usedSize--;

• 這行代碼將 usedSize 減 1，表示棧中元素的數(shù)量減少了一個(gè)。
• 減少后的作用：
  • usedSize 減少后，指向的索引位置就是被彈出的元素的索引。
  • elem[usedSize] 表示當(dāng)前棧頂?shù)脑亍?/li>

5. return elem[usedSize];

• 返回當(dāng)前棧頂元素，即 elem[usedSize]。
• 邏輯：
  • 由于前面已經(jīng)執(zhí)行了 usedSize--，此時(shí) usedSize 的值指向的是剛剛被移除的棧頂元素所在的索引。
  • 直接返回 elem[usedSize]，實(shí)現(xiàn)彈棧并返回被移除的元素。

4.獲取棧頂元素 但是不刪除當(dāng)前元素peek

1.public int peek()

• 訪(fǎng)問(wèn)控制：public 表示該方法對(duì)外可見(jiàn)，允許外部代碼調(diào)用。
• 返回類(lèi)型：int，表示該方法返回一個(gè)整數(shù)，即棧頂?shù)脑刂怠?/li>
• 方法名：peek，這是棧數(shù)據(jù)結(jié)構(gòu)中的常見(jiàn)操作，用于查看棧頂元素而不改變棧的狀態(tài)。

2. if (isEmpty()) {

• 在執(zhí)行 peek 操作之前，方法首先檢查棧是否為空，以防止在空棧上進(jìn)行不合法的操作。
• isEmpty() 方法：判斷棧是否為空。通常的實(shí)現(xiàn)方式是檢查 usedSize 是否為 0：

3. throw new RuntimeException();

• 如果棧為空，拋出一個(gè) RuntimeException。

• 異常處理：拋出異常意味著對(duì)空棧執(zhí)行 peek 操作是非法的，并且程序會(huì)拋出一個(gè)運(yùn)行時(shí)異常來(lái)提醒用戶(hù)。這樣可以防止程序在不正確的狀態(tài)下繼續(xù)運(yùn)行。

  這種方式相較于返回特殊值（如 -1）更為嚴(yán)謹(jǐn)，因?yàn)榉祷?-1 可能會(huì)與有效的數(shù)據(jù)沖突，導(dǎo)致邏輯錯(cuò)誤。

4. return elem[usedSize - 1];

• 這行代碼返回棧頂元素的值，但并不移除該元素。
• usedSize - 1：棧的大小 usedSize 表示棧中當(dāng)前有效元素的個(gè)數(shù)。由于數(shù)組索引從 0 開(kāi)始，因此棧頂?shù)脑匚挥?usedSize - 1 的索引位置。例如：
  • 如果棧有 3 個(gè)元素，usedSize = 3，棧頂元素的位置是 elem[2]，即 usedSize - 1。
• 通過(guò)返回 elem[usedSize - 1]，我們能夠獲取棧頂?shù)脑刂?#xff0c;而不影響棧的內(nèi)容。

5.返回棧大小：

• 返回 usedSize：usedSize 是一個(gè)成員變量，用于記錄棧中當(dāng)前元素的數(shù)量。當(dāng)我們創(chuàng)建棧時(shí)，usedSize 從 0 開(kāi)始，隨著元素的壓棧操作（push）而增加，隨著彈棧操作（pop）而減少。
• 因此，size 方法返回的就是棧當(dāng)前的有效元素個(gè)數(shù)，也就是 usedSize 的值。

2.4? 完整代碼展示：

import java.util.Arrays;public class MyStack {private int[] elem;private int usedSize;private static final int DEFAULT_SIZE = 10;public MyStack() {elem = new int[DEFAULT_SIZE];}//存儲(chǔ)數(shù)據(jù)public void push(int val) {if(isFull()) {//擴(kuò)容grow();}elem[usedSize] = val;usedSize++;}private void grow() {elem = Arrays.copyOf(elem,elem.length);}public boolean isFull() {return usedSize == elem.length;}//刪除數(shù)據(jù)public int pop() {if(isEmpty()) {//return -1;throw new RuntimeException();}usedSize--;return elem[usedSize];}public boolean isEmpty() {return usedSize == 0;}//獲取棧頂元素 但是不刪除當(dāng)前元素public int peek() {if(isEmpty()) {//return -1;throw new RuntimeException();}//usedSize--;return elem[usedSize-1];}public int size() {return usedSize;}}

2.5棧的使用場(chǎng)景

• 方法調(diào)用棧（堆棧） Java中的方法調(diào)用棧是由虛擬機(jī)（JVM）管理的?？臻g。當(dāng)一個(gè)方法被調(diào)用時(shí)，JVM 會(huì)在棧中為該方法分配一個(gè)棧幀，用于存儲(chǔ)方法的局部變量、操作數(shù)棧、返回地址等信息。方法執(zhí)行完畢后，棧幀會(huì)被銷(xiāo)毀。

• 表達(dá)式求值 棧在算術(shù)表達(dá)式求值中非常重要。例如，在中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式時(shí)，棧用來(lái)保存運(yùn)算符，并且根據(jù)運(yùn)算符的優(yōu)先級(jí)來(lái)控制棧中的內(nèi)容。

• 回溯算法 在深度優(yōu)先搜索（DFS）算法和回溯算法中，棧用于存儲(chǔ)遞歸過(guò)程中的狀態(tài)信息。

• 括號(hào)匹配 在編程中，檢查一段代碼中的括號(hào)是否匹配也可以通過(guò)棧來(lái)實(shí)現(xiàn)。遇到左括號(hào)時(shí)入棧，遇到右括號(hào)時(shí)出棧。如果棧為空或括號(hào)不匹配，則說(shuō)明括號(hào)不合法。

2.6棧的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 高效性：棧的插入和刪除操作是常數(shù)時(shí)間操作（O(1)），不需要查找、排序等復(fù)雜操作。
• 簡(jiǎn)潔性：棧的操作非常簡(jiǎn)單，只有棧頂訪(fǎng)問(wèn)，避免了復(fù)雜的數(shù)據(jù)結(jié)構(gòu)管理。
• 適用性強(qiáng)：棧可以用來(lái)解決許多常見(jiàn)的算法問(wèn)題，如括號(hào)匹配、回溯算法、遞歸、深度優(yōu)先搜索等。

缺點(diǎn)：

• 訪(fǎng)問(wèn)受限：棧只能訪(fǎng)問(wèn)棧頂?shù)脑?#xff0c;無(wú)法直接訪(fǎng)問(wèn)棧中的其他元素。對(duì)于需要隨機(jī)訪(fǎng)問(wèn)的場(chǎng)景，棧就不太合適。
• 空間限制：棧的大小通常是有限的，如果棧的空間耗盡（比如在遞歸調(diào)用時(shí)），會(huì)導(dǎo)致棧溢出（StackOverflowError）。

3.棧的拓展方法：

1.toArray（）將棧轉(zhuǎn)換為一個(gè)數(shù)組，方便進(jìn)行其他操作或輸出棧的內(nèi)容。

public int[] toArray() {
??? return Arrays.copyOf(elem, usedSize);? // 返回棧中有效部分的數(shù)組
}

• 返回值：返回一個(gè)數(shù)組，包含棧中的所有元素。
• 功能：將棧的內(nèi)容轉(zhuǎn)換為數(shù)組。
• 復(fù)雜度：時(shí)間復(fù)雜度 O(n)，需要遍歷棧中的元素并將其復(fù)制到數(shù)組中。

比較重要所以詳細(xì)講解：

• Arrays.copyOf(elem, usedSize)：
  • Arrays.copyOf() 是 Java 提供的一個(gè)靜態(tài)方法，它可以復(fù)制一個(gè)數(shù)組的前幾個(gè)元素到新的數(shù)組中。這里它將 elem 數(shù)組中從索引 0 到 usedSize - 1 的所有元素復(fù)制到一個(gè)新的數(shù)組。
  • elem 是棧的存儲(chǔ)數(shù)組，它的長(zhǎng)度可能大于當(dāng)前棧的實(shí)際元素個(gè)數(shù)（usedSize）。
  • usedSize 表示棧中當(dāng)前存儲(chǔ)的元素個(gè)數(shù)，因此我們只需要復(fù)制前 usedSize 個(gè)元素。
  • copyOf 方法返回一個(gè)新的數(shù)組，包含棧中當(dāng)前的所有有效元素。

為什么使用 Arrays.copyOf？

• Arrays.copyOf() 方法能夠處理數(shù)組的拷貝，并自動(dòng)管理目標(biāo)數(shù)組的大小。它會(huì)創(chuàng)建一個(gè)新的數(shù)組，并將原數(shù)組的元素復(fù)制到新數(shù)組中。
• 使用 copyOf 的好處是可以確保不會(huì)出現(xiàn)數(shù)組越界問(wèn)題，而且代碼簡(jiǎn)潔。

4. 方法返回值

toArray() 方法返回的是一個(gè)新的數(shù)組，其中包含棧中當(dāng)前所有的元素。返回值的類(lèi)型是 int[]，也就是一個(gè)整型數(shù)組。

例如，假設(shè)棧中有以下元素：

• elem = [10, 20, 30, 0, 0]
• usedSize = 3

調(diào)用 toArray() 后，會(huì)返回一個(gè)包含棧中前 3 個(gè)元素的新數(shù)組：

• 返回的數(shù)組：[10, 20, 30]

5. 使用場(chǎng)景

toArray() 方法主要用于以下幾種場(chǎng)景：

• 輸出棧內(nèi)容：有時(shí)需要輸出棧的內(nèi)容，toArray() 可以將棧元素轉(zhuǎn)換成數(shù)組，然后方便地打印或者操作。
• 與其他API交互：有些算法或庫(kù)可能需要將棧轉(zhuǎn)換為數(shù)組進(jìn)行處理。toArray() 可以方便地將棧的元素傳遞給這些函數(shù)。
• 復(fù)制棧內(nèi)容：如果需要保持棧的副本，或者用于歷史數(shù)據(jù)的存儲(chǔ)時(shí)，toArray() 會(huì)返回一個(gè)包含棧元素的數(shù)組副本。

6. 時(shí)間復(fù)雜度分析

• 時(shí)間復(fù)雜度：Arrays.copyOf(elem, usedSize) 會(huì)復(fù)制 usedSize 個(gè)元素，因此時(shí)間復(fù)雜度為 O(n)，其中 n 是棧中當(dāng)前元素的個(gè)數(shù)。
• 空間復(fù)雜度：toArray() 會(huì)創(chuàng)建一個(gè)新的數(shù)組，因此空間復(fù)雜度是 O(n)，其中 n 是棧中元素的個(gè)數(shù)。

7. 與其他集合類(lèi)的對(duì)比

toArray() 是將棧中的元素轉(zhuǎn)換為數(shù)組的常見(jiàn)方法。與其他集合類(lèi)（如 ArrayList、LinkedList 等）中的 toArray() 方法類(lèi)似，棧的 toArray() 方法返回一個(gè)包含當(dāng)前棧元素的數(shù)組。不過(guò)，棧通常是一個(gè)基于數(shù)組或動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)，因此 toArray() 返回的數(shù)組通常是連續(xù)存儲(chǔ)的，和數(shù)組的順序一致。

8. 示例使用

假設(shè)我們使用 MyStack 類(lèi)來(lái)測(cè)試 toArray() 方法：

import java.util.Stack;
import java.util.Arrays;

public class StackToArrayExample {
??? public static void main(String[] args) {
??????? // 創(chuàng)建一個(gè)棧對(duì)象
??????? Stack<Integer> stack = new Stack<>();

??????? // 使用 push() 方法壓入元素
??????? stack.push(10);
??????? stack.push(20);
??????? stack.push(30);
??????? stack.push(40);
??????? stack.push(50);

??????? // 打印棧內(nèi)容
??????? System.out.println("棧的內(nèi)容（通過(guò) printStack() 方法查看）：");
??????? for (Integer item : stack) {
??????????? System.out.print(item + " ");
??????? }
??????? System.out.println();

??????? // 使用 toArray() 方法將棧轉(zhuǎn)換為數(shù)組
??????? Integer[] array = stack.toArray(new Integer[0]);

??????? // 打印轉(zhuǎn)換后的數(shù)組
??????? System.out.println("棧轉(zhuǎn)換成的數(shù)組：");
??????? System.out.println(Arrays.toString(array));? // 輸出：[10, 20, 30, 40, 50]
?????? ?
??????? // 彈出棧頂元素
??????? stack.pop();
?????? ?
??????? // 再次打印棧轉(zhuǎn)換成的數(shù)組
??????? array = stack.toArray(new Integer[0]);
??????? System.out.println("棧彈出一個(gè)元素后的數(shù)組：");
??????? System.out.println(Arrays.toString(array));? // 輸出：[10, 20, 30, 40]
??? }
}

2.contains()判斷棧中是否包含指定的元素。

public boolean contains(int value) {
??? for (int i = 0; i < usedSize; i++) {
??????? if (elem[i] == value) {
??????????? return true;
??????? }
??? }
??? return false;
}

• 功能：檢查棧中是否包含某個(gè)元素。通常需要遍歷棧中的元素。
• 復(fù)雜度：時(shí)間復(fù)雜度 O(n)，因?yàn)樾枰闅v棧中的所有元素。
• 使用場(chǎng)景：當(dāng)你需要判斷棧中是否存在特定元素時(shí)使用。

3. peekAt(int index)返回棧中指定位置的元素，不修改棧的狀態(tài)。

public int peekAt(int index) {
??? if (index < 0 || index >= usedSize) {
??????? throw new IndexOutOfBoundsException("Index out of bounds");
??? }
??? return elem[index];
}

• 功能：返回棧中指定索引位置的元素。這里的索引是棧內(nèi)的相對(duì)位置，不是從棧頂開(kāi)始的。
• 復(fù)雜度：時(shí)間復(fù)雜度 O(1)。
• 使用場(chǎng)景：可以用來(lái)查看棧中某個(gè)特定位置的元素。需要注意的是，它不保證返回棧頂元素，而是指定索引位置的元素。

4. reverse()將棧中的元素反轉(zhuǎn)。這個(gè)操作通常修改棧的順序。

public void reverse() {
??? int[] reversed = new int[usedSize];
??? int j = 0;
??? for (int i = usedSize - 1; i >= 0; i--) {
??????? reversed[j++] = elem[i];
??? }
??? System.arraycopy(reversed, 0, elem, 0, usedSize);
}

• 功能：反轉(zhuǎn)棧中的所有元素，棧頂元素變?yōu)闂５?#xff0c;棧底元素變?yōu)闂ｍ敗?/li>
• 復(fù)雜度：時(shí)間復(fù)雜度 O(n)，因?yàn)樾枰闅v棧的所有元素并進(jìn)行重新排序。
• 使用場(chǎng)景：如果需要將棧中的元素順序反轉(zhuǎn)，可以使用此方法。

5. toString()將棧轉(zhuǎn)換為字符串形式，方便查看棧的內(nèi)容。

@Override
public String toString() {
??? StringBuilder sb = new StringBuilder();
??? sb.append("[");
??? for (int i = 0; i < usedSize; i++) {
??????? sb.append(elem[i]);
??????? if (i < usedSize - 1) {
??????????? sb.append(", ");
??????? }
??? }
??? sb.append("]");
??? return sb.toString();
}

• 功能：返回棧中元素的字符串表示。
• 復(fù)雜度：時(shí)間復(fù)雜度 O(n)，需要遍歷棧中的所有元素并構(gòu)建字符串。
• 使用場(chǎng)景：當(dāng)需要打印棧的內(nèi)容時(shí)，可以使用 toString() 方法。對(duì)于調(diào)試和日志記錄非常有用。

6. clone()（深拷貝棧）克隆棧，創(chuàng)建棧的副本。確保副本與原棧是兩個(gè)獨(dú)立的對(duì)象。

@Override
public MyStack clone() {
??? MyStack newStack = new MyStack();
??? newStack.elem = Arrays.copyOf(this.elem, this.elem.length);
??? newStack.usedSize = this.usedSize;
??? return newStack;
}

• 功能：創(chuàng)建棧的一個(gè)副本，確保副本的元素與原棧相同，但兩個(gè)棧是獨(dú)立的對(duì)象，互不影響。
• 復(fù)雜度：時(shí)間復(fù)雜度 O(n)，因?yàn)樾枰獙Ｖ械脑貜?fù)制到新的棧中。
• 使用場(chǎng)景：需要操作棧的副本，而不改變?cè)瓧５膬?nèi)容時(shí)使用。

7. shrink()（可選）如果棧的容量比元素?cái)?shù)量大很多，進(jìn)行收縮，減少不必要的內(nèi)存占用。

private void shrink() {
??? if (usedSize < elem.length / 4) {
??????? int newCapacity = elem.length / 2;
??????? elem = Arrays.copyOf(elem, newCapacity);
??? }
}

• 功能：如果棧的元素?cái)?shù)量小于數(shù)組容量的四分之一，則將棧的容量縮小為原來(lái)的一半。
• 復(fù)雜度：時(shí)間復(fù)雜度 O(n)，因?yàn)樾枰獜?fù)制棧中的元素到新數(shù)組中。
• 使用場(chǎng)景：用于棧的動(dòng)態(tài)縮容，當(dāng)棧的元素?cái)?shù)目小于某個(gè)比例時(shí)，減少內(nèi)存浪費(fèi)。

8.clearAll()（可選）清空棧，并且將棧容量調(diào)整到默認(rèn)大小。

public void clearAll() {
??? usedSize = 0;
??? elem = new int[DEFAULT_SIZE];? // 將棧的容量恢復(fù)為默認(rèn)大小
}

• 功能：除了清空棧中的元素，還將棧的容量恢復(fù)為默認(rèn)大小。
• 復(fù)雜度：時(shí)間復(fù)雜度 O(n)（如果實(shí)現(xiàn)了 clear 操作）+ O(n)（重新分配數(shù)組）。
• 使用場(chǎng)景：當(dāng)你想要重置棧，包括清空棧內(nèi)容和恢復(fù)容量時(shí)使用。

9.peekBottom()（可選）返回棧底元素，但不刪除它。

public int peekBottom() {
??? if (isEmpty()) {
??????? throw new RuntimeException("Stack is empty");
??? }
??? return elem[0];? // 棧底元素是數(shù)組的第一個(gè)元素
}

• 功能：查看棧底的元素，而不刪除它。
• 復(fù)雜度：時(shí)間復(fù)雜度 O(1)，直接返回棧底元素。
• 使用場(chǎng)景：有時(shí)需要查看棧底的元素，或者從棧底進(jìn)行操作。

4.結(jié)語(yǔ)：

在本文中，我們?cè)敿?xì)探討了如何實(shí)現(xiàn)一個(gè)簡(jiǎn)單的棧數(shù)據(jù)結(jié)構(gòu)，并對(duì)棧的常見(jiàn)操作如 push、pop、peek 和 size 進(jìn)行了深入的分析。通過(guò)這些方法，我們不僅了解了棧的基本功能，還能看到如何通過(guò)調(diào)整 usedSize 來(lái)有效管理?xiàng)５臓顟B(tài)，保證其操作的高效性和安全性。

棧作為一種基本的數(shù)據(jù)結(jié)構(gòu)，具有廣泛的應(yīng)用場(chǎng)景，尤其在算法、數(shù)據(jù)解析、函數(shù)調(diào)用棧等方面扮演著重要角色。通過(guò)本文的學(xué)習(xí)，我們可以更好地理解棧的內(nèi)在機(jī)制，并能夠在實(shí)際編程中靈活運(yùn)用棧。

在實(shí)現(xiàn)棧的過(guò)程中，我們還探討了幾個(gè)常見(jiàn)的優(yōu)化點(diǎn)，例如動(dòng)態(tài)擴(kuò)容、異常處理、以及線(xiàn)程安全等，確保棧能夠在不同的環(huán)境和需求下穩(wěn)定高效地運(yùn)行。這些設(shè)計(jì)細(xì)節(jié)不僅提升了代碼的健壯性，還增強(qiáng)了棧的可擴(kuò)展性。

希望通過(guò)本文的介紹，讀者能夠?qū)＿@一數(shù)據(jù)結(jié)構(gòu)有更清晰的理解，并能夠在實(shí)際項(xiàng)目中更加熟練地使用和擴(kuò)展它。棧是很多算法和應(yīng)用的基礎(chǔ)，掌握它的設(shè)計(jì)和使用，將為解決更多復(fù)雜問(wèn)題打下堅(jiān)實(shí)的基礎(chǔ)。

感謝您的閱讀，期待您在實(shí)踐中不斷深入，探索更多有趣且實(shí)用的數(shù)據(jù)結(jié)構(gòu)和算法。