先說什麼是棧：
1、後進先出 2、對數據的所有操作只能在固定的一端進行操作，不能再中間或者另一端對數據進行操作。
符合以上兩點的 存儲數據的類（對象） 叫做棧。
需要說明的是：棧是符合以上兩個特性的所有的數據結構都可以叫做棧，無論其用什麼基本容器實現的。
再說如何實現:
可以使用數組或者鏈表實現棧，在用鏈表實現的時候要屏蔽掉鏈表的一些特性：在鏈表中間對數據進行操作等。
看一下jdk中自帶的棧：
注意Stack(圖一)中： Stack繼承自Vactor Stack自己的方法種類
Vector(圖二)中 ： Vector中的方法
Stack繼承自Vactor，所以Stack是可以調用父類中的set(int index, E element),insertElementAt(E obj, int index)等操作的，這樣的話就與棧的特性有矛盾，我對這一點還沒有理解透徹，是不是第二條特性需要去掉？希望有朋友看到之後能夠指教指教。感謝！
圖一：Stack.java
圖二：Vector.java
既然是jdk自帶的有棧，我們還了解他干什麼？
在一些特殊情況下，需要根據實際情況封裝自己的棧。
下面給兩個自己做的示例，一個使用數組實現的棧，一個是用鏈表實現的棧。
數組實現：
package com.datastructure;
/**
* @author Perkins .Zhu
* @date:2016年7月17日 上午9:13:01
* @version :1.1
*
*/
public class ArrayStack implements Stack {
private int maxSize;
private Object[] myStack;
private int top = -1;// 指向最後入棧的對象
private final int DEFAULT_SIZE = 100;
private boolean canExpendSize = true;// 是否允許擴容
private int multiple = 2;// 擴容倍數
public ArrayStack() {
myStack = new Object[DEFAULT_SIZE];
}
public ArrayStack(int size, boolean canExpendSize) {
if (size < 1) {
size = DEFAULT_SIZE;
}
myStack = new Object[size];
this.canExpendSize = canExpendSize;
}
@Override
public void push(Object obj) {
if (top == myStack.length - 1) {
if (canExpendSize) {
exspandSize();
} else {
move();
}
}
myStack[++top] = obj;
}
// 刪除棧底元素，所有元素向後移動一位，top指向 myStack.length-2
private void move() {
for (int i = 0; i < myStack.length - 1; i++) {
myStack[i] = myStack[i + 1];
}
top = myStack.length - 2;
}
// 擴容
private void exspandSize() {
Object[] temp = new Object[multiple * myStack.length];
for (int i = 0; i < myStack.length; i++) {
temp[i] = myStack[i];
}
top = myStack.length - 1;
myStack = temp;
}
@Override
public Object pop() {
if (top == -1)
return null;
return myStack[top--];
}
@Override
public boolean isEmpty() {
return top == -1;
}
}
鏈表實現：(只實現了基本功能，可根據實際需要添加參數或者方法)
package com.datastructure;
import java.util.LinkedList;
/**
* @author Perkins .Zhu
* @date:2016年7月17日 下午1:16:26
* @version :1.1
*
*/
public class LinkStack implements Stack {
private Node top;
private class Node {
private Object obj;
private Node nextNode;
public Node(Object obj, Node node) {
this.obj = obj;
this.nextNode = node;
}
}
public void push(Object obj) {
if (top != null) {
top = new Node(obj, top);
} else {
top = new Node(obj, null);
}
}
public Object pop() {
Node res = top;
res.nextNode = null;
top = top.nextNode;
return res.obj;
}
public boolean isEmpty() {
return top == null;
}
}
再給個測試類:
package com.datastructure;
import org.junit.Test;
/**
* @author Perkins .Zhu
* @date:2016年7月17日 上午9:16:50
* @version :1.1
*
*/
public class StackTest {
@Test
public void testArrayStack() {
ArrayStack stack = new ArrayStack(100, false);
int loop = 0;
while (loop < 150) {
stack.push(loop++);
}
print(stack);
}
public void print(Object obj) {
if (obj instanceof Stack) {
Stack stack = (Stack) obj;
while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
}
System.out.println();
}
@Test
public void testLinkStack() {
LinkStack stack = new LinkStack();
int loop = 0;
while (loop < 150) {
stack.push(loop++);
}
print(stack);
}
}
有些問題暫時還沒有搞清楚，暫時做個記錄。在學習的過程中遇到如下幾個問題，如果有大神請不吝賜教,在此謝過！
1、有沒有棧的官方標准定義？
2、泛型 T和object有什麼區別，接收參數的時候有什麼不同的？？
3、棧要不要實現其刪除、插入、查找操作？
4、除了使用數組和鏈表還有沒有其他棧實現方式？
後期把這幾個問題搞清楚之後會更新此文章。
