棧簡介
- 棧(Stack)是一種插入刪除操作都只能在一個位置上進行,這個位- 置位于表的末端,叫做棧頂(Top)；
- 對棧的基本操作有push和pop,表示進棧和出棧.也就相當于插入和刪除操作；
- 棧結(jié)構(gòu)又叫做LIFO(后進先出)表.歸根結(jié)底是一個表結(jié)構(gòu),因此任何能夠?qū)崿F(xiàn)表結(jié)構(gòu)的方法都能實現(xiàn)棧；
- 在java語言中,ArrayList和LinkedList都支持棧操作,棧操作都是常數(shù)時間的操作,棧的實現(xiàn)方式一般有兩種,一種是使用順序存儲的方式,即使用數(shù)組來實現(xiàn),用ArrayList可以輕易實現(xiàn)棧結(jié)構(gòu),也可以自己使用數(shù)組來實現(xiàn),一會下面我就用數(shù)組來實現(xiàn)棧,第二種是使用鏈式存儲實現(xiàn),即可以使用LinkedList來實現(xiàn).
基于數(shù)組實現(xiàn)的棧
/*
* 后進先出（LIFO）或先進后出
* 方法：
* 1.進棧 push()
* 2.出棧 pop()
* 3. 獲取棧頂元素 peek()
* 4. 棧的大小 size
* 5. 擴容
* 使用泛型，以便棧中能夠存儲我們想要的數(shù)據(jù)
* 基于數(shù)組的棧實現(xiàn)
*/
public class MyStack<E> {
private Object[] stack;
/*棧中元素的個數(shù),這里沒有對size1進行初始化懦窘，
是因為size是類成員變量，程序在實例化類的時
候會把size初始化為默認值0
*/
private int size;
public MyStack() {
stack=new Object[10]; //初始長度為10
}
// 判斷棧是都為空
public boolean isEmpty() {
return size==0;
}
// 返回棧頂元素
public E peek() {
if(isEmpty()) {
return null;
}
return (E) stack[size-1];
}
public E pop() {
E e = peek(); //獲取棧頂元素
if(size>0) {
stack[size-1]=null; //將出棧后的位置置為空
size--; //將棧中元素減一
}
return e; //返回棧頂元素
}
// 檢測棧是否滿，滿的話需要擴容
private void ensureCapacity(int size) {
int len = stack.length;
if(size>len) {
int newLen= len+10; //每次擴容增10
stack = Arrays.copyOf(stack, newLen);
}
}
public E push(E e) {
ensureCapacity(size+1); //先進行擴容檢測
stack[size++]=e; //把元素加進數(shù)組最后末尾缚忧，并將元素個數(shù)size加1
return e; //返回該元素
}
public void printStack() {
System.out.println("start print stack....");
for(int index=0;index<size;index++) {
System.out.println(stack[index]);
}
System.out.println("finish!");
}
// 測試
public static void main(String[] args) {
MyStack<String> myStack = new MyStack<String>();
myStack.push("as");
myStack.push("c");
myStack.push("d");
System.out.println(myStack.pop());
myStack.printStack();
}
}
