返回棧頂?shù)脑兀也粍h除
public synchronized E peek() {
try {
//elementData數(shù)據(jù)元素的集合 elementCount元素集合的數(shù)量 棧是先進(jìn)后出的
return (E) elementData[elementCount - 1];
} catch (IndexOutOfBoundsException e) {
throw new EmptyStackException();
}
}
出棧赐俗，返回棧頂元素并且刪除
public synchronized E pop() {
if (elementCount == 0) {//如果數(shù)據(jù)為空，拋出異常
throw new EmptyStackException();
}
final int index = --elementCount;
//獲得最后一個元素的對象
final E obj = (E) elementData[index];
//設(shè)置最后一個元素為空
elementData[index] = null;
modCount++;
return obj;
}
入棧贤笆，添加對象到棧頂
public E push(E object) {
addElement(object);
return object;
}
public synchronized void addElement(E object) {
//elementCount除去空元素數(shù)組的數(shù)量 如果相等表示沒有空間了现斋，則進(jìn)行擴(kuò)容
if (elementCount == elementData.length) {
growByOne();
}
//添加對象入棧
elementData[elementCount++] = object;
modCount++;
}
private void growByOne() {
int adding = 0;//默認(rèn)添加為0
//如果capacityIncrement為0或者復(fù)數(shù)，如果需要增加俐末，那么大小將增加一倍料按。
if (capacityIncrement <= 0) {
if ((adding = elementData.length) == 0) {//如果元素集合為空
adding = 1;
}
} else {
adding = capacityIncrement;
}
E[] newData = newElementArray(elementData.length + adding);
System.arraycopy(elementData, 0, newData, 0, elementCount);
elementData = newData;
}
search查詢
public synchronized int search(Object o) {
//獲得數(shù)據(jù)和大小
final Object[] dumpArray = elementData;
final int size = elementCount;
if (o != null) {
//從棧頂開始遍歷
for (int i = size - 1; i >= 0; i--) {
//使用dumpArray，是安全問題卓箫，elementData可能進(jìn)行入棧载矿，出棧的問題
if (o.equals(dumpArray[i])) {
return size - i;
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (dumpArray[i] == null) {
return size - i;
}
}
}
return -1;
}
棧的經(jīng)典實用:逆波蘭表達(dá)式
- 標(biāo)準(zhǔn)的四則表達(dá)式：9+（3-1）*3+10/2
- 計算機(jī)采用—后綴表達(dá)式:931-3*+102/+
首先看下怎么計算的
931-3*+102/+
923*+102/+
96+102/+
15102/+
155+
20
中綴表達(dá)式9+（3-1）*3+10/2轉(zhuǎn)化為 后綴表達(dá)式931-3 *+102/+
原則：
a. 若為 '('，入棧;
b. 若為 ')'烹卒，則依次把棧中的的運算符加入后綴表達(dá)式中闷盔，直到出現(xiàn)'('，從棧中刪除'(' ;
c. 若為 除括號外的其他[運算符]旅急， 當(dāng)其優(yōu)先級高于除'('以外的棧頂運算符時逢勾，直接入棧。否則從棧頂開始藐吮，依次彈出比當(dāng)前處理的[運算符優(yōu)先級]高和優(yōu)先級相等的運算符溺拱，直到一個比它優(yōu)先級低的或者遇到了一個左括號為止。
·當(dāng)掃描的中綴表達(dá)式結(jié)束時炎码，棧中的的所有運算符出棧
①首先9輸出盟迟，+入棧頂
②因為 ( 所以直接入棧,3直接輸出 - 入棧1直接輸出 ) 把之前()入棧的元素直接輸出,此時931-
③3是數(shù)字直接輸出, * 運算符比+高直接進(jìn)棧，隨后+進(jìn)棧潦闲，優(yōu)先級低攒菠，依次彈出*和+
④ 10是數(shù)字直接輸出，然后/入棧歉闰，2是數(shù)字直接輸入辖众，/的優(yōu)先級比+優(yōu)先級高進(jìn)棧卓起，此時已經(jīng)運算符，依次彈出
