android栈式存储,线性表数据结构解读（三）栈结构Stack
在上一篇文章中，我們詳細介紹了鏈式存儲結(jié)構(gòu)，并結(jié)合LinkedList源碼進行了分析，相關(guān)文章大家可以點擊這里回看我的博客：線性表數(shù)據(jù)結(jié)構(gòu)解讀(二)鏈式存儲結(jié)構(gòu)LinkedList
棧的定義
棧是一種特殊的線性表，其全部操作都被限制在表的固定一端進行，而且構(gòu)成棧的元素必須是同一數(shù)據(jù)類型。
棧的特點
允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom),不含任何數(shù)據(jù)元素的棧稱為空棧。棧又稱為后進先出的線性表
棧的操作
棧的常用操作包括建立棧、元素入棧、元素出棧、取棧頂元素等。
空棧
當建立一個棧時，不包括任何元素，此時稱其為空棧。棧為空時top和bottom共同指向棧底。向棧中插入元素成為入棧，使top指向的元素退出棧，稱為出棧，出棧和入棧操作全部是針對棧頂元素進行操作的。
棧的存儲結(jié)構(gòu)
● 順序棧
將棧在順序存儲結(jié)構(gòu)下所得到的結(jié)構(gòu)成為順序棧。順序棧類類似于數(shù)組，因此可以使用數(shù)組實現(xiàn)順序棧的相關(guān)運算，通常棧底是下標為0的一端。
● 鏈式棧
將棧在鏈式存儲結(jié)構(gòu)下所得到的結(jié)構(gòu)，稱為鏈式棧。鏈式棧類似于指針，在java中可以通過類的對象引用實現(xiàn)指針運算。
鏈式棧的入棧操作
把top的引用指向新的結(jié)點，新結(jié)點的下一個引用指向原來的top結(jié)點
鏈式棧的出棧操作
把top的引用指向原棧頂元素的下一個元素，并釋放原棧頂元素的引用
棧結(jié)構(gòu)在Android中的應(yīng)用
在Android中，我們常見具有代表性的棧結(jié)構(gòu)為Stack，下面我們進行分析，看看它內(nèi)部是如何實現(xiàn)入棧和出棧操作的。
public class Stack extends Vector {
private static final long serialVersionUID = 1224463164541339165L;
/** * 無參構(gòu)造方法 */
public Stack() {
}
/** * 判斷是否為空 * Returns whether the stack is empty or not. * @return {@code true} if the stack is empty, {@code false} otherwise. */
public boolean empty() {
return isEmpty();
}
/** * 返回棧頂?shù)脑?* Returns the element at the top of the stack without removing it. * @return the element at the top of the stack. * @throws EmptyStackException if the stack is empty. * @see #pop */
@SuppressWarnings("unchecked")
public synchronized E peek() {
try {
return (E) elementData[elementCount - 1];
} catch (IndexOutOfBoundsException e) {
throw new EmptyStackException();
}
}
/** * 彈出棧 * Returns the element at the top of the stack and removes it. * @return the element at the top of the stack. * @throws EmptyStackException if the stack is empty. * @see #peek * @see #push */
@SuppressWarnings("unchecked")
public synchronized E pop() {
if (elementCount == 0) {// 如果為0則為空棧
throw new EmptyStackException();// 拋出空棧異常
}
// index是被彈出棧元素的下標(先減再賦值)
final int index = --elementCount;
final E obj = (E) elementData[index];
elementData[index] = null;// 把彈出棧的元素值設(shè)為空
modCount++;
return obj;
}
/** * 推入棧操作 * Pushes the specified object onto the top of the stack. * @param object The object to be added on top of the stack. * @return the object argument. * @see #peek * @see #pop */
public E push(E object) {
// 添加一個元素
addElement(object);
return object;
}
/** * 查詢操作，該方法一定要是線程安全的，不能一邊遍歷一邊增刪 * Returns the index of the first occurrence of the object, starting from * the top of the stack. * @return the index of the first occurrence of the object, assuming that * the topmost object on the stack has a distance of one. * @param o the object to be searched. */
public synchronized int search(Object o) {
final Object[] dumpArray = elementData;
// 非空棧元素的數(shù)量
final int size = elementCount;
if (o != null) {// 如果傳進來的元素不等于空
for (int i = size - 1; i >= 0; i--) {// 從棧頂遍歷下去
if (o.equals(dumpArray[i])) {//如果傳進來的元素等于dumpArray[i]
return size - i;
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (dumpArray[i] == null) {// 如果dumpArray[i]等于null
return size - i;
}
}
}
return -1;
}
}
我們注意到源碼中push方法中用到了父類的addElement()，這里我們?nèi)tack的父類Vector中一探究竟。
addElement方法
/** * 添加元素方法 * Adds the specified object at the end of this vector. *@param object the object to add to the vector. */
public synchronized void addElement(E object) {
// 容量長度和非空元素數(shù)量相同
if (elementCount == elementData.length) {
growByOne();
}
elementData[elementCount++] = object;
modCount++;
}
growByOne方法
/** * JIT optimization */
private void growByOne() {
int adding = 0;
if (capacityIncrement <= 0) {
// 判斷是否是空棧，如果為空增加1
if ((adding = elementData.length) == 0) {
adding = 1;
}
} else {// 否則擴容capacityIncrement
adding = capacityIncrement;
}
// 新創(chuàng)建一個數(shù)組，把數(shù)組長度擴容，然后數(shù)組復制
E[] newData = newElementArray(elementData.length + adding);
System.arraycopy(elementData, 0, newData, 0, elementCount);
elementData = newData;
}
參考來源：動腦學院Danny老師數(shù)據(jù)結(jié)構(gòu)課程
總結(jié)
以上是生活随笔為你收集整理的android栈式存储,线性表数据结构解读（三）栈结构Stack的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： android圆角布局阴影,Androi
- 下一篇： android 代码生成 keyhash