數據結構—棧

先說什么是棧：

　　　　　　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;

 　　　　top = top.nextNode;

=   top ==

 再給個測試類:

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、有沒有棧的官方標準定義？

　　　　　　只要符合后進先出(last in first off，LIFO)的數據結構都是棧。

　　　　2、泛型 T和object有什么區別，接收參數的時候有什么不同的？？ 

　　　　　　a:約束了此容器中只能存儲一種類型數據。

　　　　　　b:在從容器中取出對象的時候不需要進行類型強轉，容器已經知道（因為在new 容器的時候在<>中已經制定了存儲對象類型）你存儲的是什么類型，但是object需要進行強轉。

　　　　3、棧要不要實現其刪除、插入、查找操作？

　　　　　　棧不需要這些方法，這些方法的存在沒意義。畫蛇添足。

　　　　4、除了使用數組和鏈表還有沒有其他棧實現方式？

　　　　　　應該沒有了吧？