受限制的線性表

先進后出

實現一個棧

數組實現叫順序棧

public class ArrayStack {

private String[] items;//存儲數據的數組

private int count;//棧中的元素

private int n;//棧的大小

public ArrayStack(int n){

this.items = new String[n];

this.n = n;

this.count = 0;

}

//入棧操作

public boolean push(String item){

//如果棧滿了返回false，入棧失敗

if (count == n){

return false;

}

//將item放到下標為count的位置，count +1

items[count] = item;

//棧中元素+1

count++;

return true;

}

//出棧操作

public String pop(){

//如果棧為空返回null

if (count == 0){

return null;

}

//返回下標第n-1個元素

String temp = items[count - 1];

//元素總數減1

count--;

return temp;

}

}

支持動態擴容的順序棧

分析時間復雜度

對于出棧來說時間復雜度還是O(1)

對于入棧來說如果棧空間足夠時間復雜度為O(1)，如果棧空間不夠用需要擴容那么時間復雜度為O(n)

鏈表實現叫鏈式棧

性能分析

不論是順序棧還是鏈棧時間復雜度和空間復雜度都是O(1)

現實應用

函數調用棧

棧幀

表達式求值

兩個棧實現

括號是否匹配