棧的分類
- 棧是特殊的線性表
- 棧的典型應(yīng)用遞歸籽御，四則運(yùn)算表達(dá)式求值话浇。
棧的分類有兩種：
- 靜態(tài)棧(數(shù)組實(shí)現(xiàn))
- 動(dòng)態(tài)棧(鏈表實(shí)現(xiàn))
我們接下來(lái)會(huì)分別實(shí)現(xiàn)這兩種棧增蹭。
棧的操作
數(shù)組方式
代碼GitHub地址 - 歡迎star
棧節(jié)點(diǎn)
public class Node {
private int value;
public Node() {
}
public Node(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
由于是數(shù)組方式存儲(chǔ)的杆逗，每個(gè)節(jié)點(diǎn)都能方便的存取它的前驅(qū)后繼節(jié)點(diǎn)学少。所以我們聲明的棧節(jié)點(diǎn)只需要存在一個(gè)存值的value屬性即可剪个。
棧
public class Stacks {
private static final int MAX_SIZE = 100;
private static final int MIN_SIZE = -1;
/**
* 空棧默認(rèn) top = 1
*/
private int top = -1;
/**
* 順序棧默認(rèn)最大 100
*/
private Node[] nodes = new Node[MAX_SIZE];
public Stacks() {
}
public Stacks(int top) {
this.top = top;
}
public Stacks(Node[] nodes) {
this.nodes = nodes;
}
public Stacks(int top, Node[] nodes) {
this.top = top;
this.nodes = nodes;
}
}
由于是數(shù)組形式聲明的棧，所以我們需要規(guī)定棧最大容量版确，并且設(shè)立top變量來(lái)定位棧頂元素扣囊。
入棧
/**
* 入棧
*
* @param stacks
* @param value
* @return
*/
public static int push(Stacks stacks, int value) {
Node node = new Node(value);
if (stacks.top == MAX_SIZE) {
return 0;
}
stacks.top++;
stacks.nodes[stacks.top] = node;
return 1;
}
很簡(jiǎn)單，只需要注意代碼執(zhí)行順序即可绒疗，需要明白棧頂指針指向棧頂元素侵歇。每次入棧操作執(zhí)行完top必然會(huì)++那么它又需要在入棧后指向最新插入的新元素，就必然在賦值前++,同時(shí)賦值的時(shí)候找數(shù)組的top索引處給就是最方便快捷的吓蘑。
出棧
/**
* 出棧
*
* @param stacks
* @return
*/
public static int pop(Stacks stacks) {
if (stacks.top == MIN_SIZE) {
return 0;
}
stacks.nodes[stacks.top] = null; //
stacks.top--;
return 1;
}
和入棧操作相反惕虑，需要把棧的top索引處的元素置空，在top還在指向該節(jié)點(diǎn)的時(shí)候置空磨镶，然后top--即可溃蔫。
遍歷
/**
* 遍歷
*
* @param stacks
*/
public static void traverse(Stacks stacks) {
int top = stacks.top;
while (top > MIN_SIZE) {
System.out.println(stacks.nodes[top--].getValue());
}
}
根據(jù)top從頂?shù)降祝瑥淖畲笾档?遍歷即可琳猫。
需要注意的是：不要直接操作Stack.top變量伟叛，而是把他取出來(lái)?yè)Q其他局部變量操作。否則在你遍歷完之后脐嫂，棧中就真的沒(méi)有元素了痪伦。因?yàn)?code>Stack.top變量已經(jīng)被你指向了棧底。
判斷是否為空
/**
* 判斷是否為空
*
* @param stacks
* @return
*/
public static boolean isEmpty(Stacks stacks) {
return stacks.top == MIN_SIZE;
}
清空棧
/**
* 清空棧
*
* @param stacks
*/
public static void clean(Stacks stacks) {
while (stacks.top > MIN_SIZE) {
stacks.nodes[stacks.top] = null;
stacks.top--;
}
}
也可以循環(huán)調(diào)用出棧(pop)方法雹锣。通過(guò)while循環(huán)來(lái)判斷top變量是否大于0來(lái)判斷是否空棧网沾。
共享?xiàng)?/h3>
共享?xiàng)Ｒ话愕氖褂脠?chǎng)景是兩個(gè)棧的空間有相反的需求關(guān)系的時(shí)候。也就是一個(gè)棧增長(zhǎng)的時(shí)候另一個(gè)棧在縮短的情況蕊爵。比如購(gòu)買股票辉哥，有人買入就一定有人賣出，總量放在那里不變。不可能兩面都有人一直買入醋旦，那么棧很快就會(huì)溢出了恒水。所以在使用共享?xiàng)５臅r(shí)候考慮好使用場(chǎng)景是否符合。
public class SharedStack {
private static final int MAX_SIZE = 100;
private static final int MIN_SIZE = -1;
public Node[] stackElement = new Node[MAX_SIZE];
/**
* 棧1的棧頂指針初始為-1
*/
public int top_1 = MIN_SIZE;
/**
* 棧2的棧頂指針 初始為n
*/
public int top_2 = MAX_SIZE;
public SharedStack() {
}
}
共享?xiàng)?- 入棧
/**
* 入棧
*
* @param stack 棧
* @param value 插入的元素值
* @param stackNumber 棧序號(hào)饲齐，棧1钉凌，還是棧2
* @return 成功與否，失敗0捂人，成功返回插入的值
*/
public static int push(SharedStack stack, int value, int stackNumber) {
Node newNode = new Node(value);
if (stack.top_1 + 1 == stack.top_2) {
return 0;
}
if (stackNumber == 1) {
// 棧1插入元素
stack.stackElement[++stack.top_1] = newNode;
} else if (stackNumber == 2) {
// 棧2插入元素
stack.top_2--;
stack.stackElement[--stack.top_2] = newNode;
}
return value;
}
共享?xiàng)?- 出棧
/**
* 出棧
*
* @param stack
* @param stackNumber
* @return 刪除的棧頂元素的值
*/
public static int pop(SharedStack stack, int stackNumber) {
int value = 0;
if (stackNumber == 1) {
if (stack.top_1 == MIN_SIZE) {
return 0;
}
value = stack.stackElement[stack.top_1--].getValue();
} else if (stackNumber == 2) {
if (stack.top_2 == MAX_SIZE) {
return 0;
}
value = stack.stackElement[stack.top_2++].getValue();
}
return value;
}
鏈表方式
代碼GitHub地址 - 歡迎star
棧節(jié)點(diǎn)
public class Node {
private int value;
private Node nextNode;
public Node() {
}
public Node(int value) {
this.value = value;
}
public Node(Node nextNode) {
this.nextNode = nextNode;
}
public Node(int value, Node nextNode) {
this.value = value;
this.nextNode = nextNode;
}
getter/setter
可以看出相比于數(shù)據(jù)方式御雕，棧節(jié)點(diǎn)多了一個(gè)nextNode指針域。指向它的后繼節(jié)點(diǎn)
棧
public class Stacks {
/**
* 棧頂結(jié)點(diǎn)
*/
private Node topElement;
/**
* 棧底節(jié)點(diǎn)
*/
private Node bottmElement;
public Stacks() {
}
public Stacks(Node topElement, Node bottmElement) {
this.topElement = topElement;
this.bottmElement = bottmElement;
}
}
此時(shí)棧如果是空棧的話topElement = bottmElement
入棧
/**
* 入棧
*
* @param stacks
* @param value
* @return
*/
public static int push(Stacks stacks, int value) {
Node node = new Node(value);
// 下一節(jié)點(diǎn)為根節(jié)點(diǎn)
node.setNextNode(stacks.topElement);
stacks.topElement = node;
return 1;
}
需要記住的一個(gè)思路就是滥搭，新插入節(jié)點(diǎn)的后繼節(jié)點(diǎn)是當(dāng)前棧的棧頂元素酸纲。插入之后才能移動(dòng)該棧頂元素的指針topElement。
出棧
/**
* 出棧
*
* @param stacks
* @return
*/
public static int pop(Stacks stacks) {
if (stacks.topElement == stacks.bottmElement) {
return 0;
}
stacks.topElement = stacks.topElement.getNextNode();
return 1;
}
棧頂指針指向其后繼節(jié)點(diǎn)即可瑟匆。
遍歷
/**
* 遍歷
*
* @param stacks
*/
public static void traverse(Stacks stacks) {
Node node = stacks.topElement;
while (node != stacks.bottmElement) {
System.out.println(node.getValue());
node = node.getNextNode();
}
}
換一個(gè)節(jié)點(diǎn)指向當(dāng)前棧頂節(jié)點(diǎn)的節(jié)點(diǎn)即可闽坡。然后一直遍歷輸出到棧底節(jié)點(diǎn)為止。
判斷是否為空
/**
* 判斷是否為空
*
* @param stacks
* @return
*/
public static boolean isEmpty(Stacks stacks) {
return stacks.topElement == stacks.bottmElement;
}
清空
/**
* 清空
*
* @param stacks
*/
public static void clean(Stacks stacks) {
stacks.bottmElement = null;
stacks.topElement = stacks.bottmElement;
}
