數(shù)據(jù)結(jié)構(gòu)—棧

先說什么是棧：

　　　　　　1、后進(jìn)先出  2、對(duì)數(shù)據(jù)的所有操作只能在固定的一端進(jìn)行操作，不能再中間或者另一端對(duì)數(shù)據(jù)進(jìn)行操作。

 符合以上兩點(diǎn)的 存儲(chǔ)數(shù)據(jù)的類（對(duì)象） 叫做棧。

  需要說明的是：棧是符合以上兩個(gè)特性的所有的數(shù)據(jù)結(jié)構(gòu)都可以叫做棧，無論其用什么基本容器實(shí)現(xiàn)的。

再說如何實(shí)現(xiàn):

　　　　　　可以使用數(shù)組或者鏈表實(shí)現(xiàn)棧，在用鏈表實(shí)現(xiàn)的時(shí)候要屏蔽掉鏈表的一些特性：在鏈表中間對(duì)數(shù)據(jù)進(jìn)行操作等。

看一下jdk中自帶的棧：

　　　　注意Stack(圖一)中：  Stack繼承自Vactor     Stack自己的方法種類

　　　　Vector(圖二)中 ： Vector中的方法

   Stack繼承自Vactor，所以Stack是可以調(diào)用父類中的set(int index, E element),insertElementAt(E obj, int index)等操作的，這樣的話就與棧的特性有矛盾，我對(duì)這一點(diǎn)還沒有理解透徹，是不是第二條特性需要去掉？希望有朋友看到之后能夠指教指教。感謝！

圖一：Stack.java

圖二：Vector.java

既然是jdk自帶的有棧，我們還了解他干什么？

  在一些特殊情況下，需要根據(jù)實(shí)際情況封裝自己的棧。

下面給兩個(gè)自己做的示例，一個(gè)使用數(shù)組實(shí)現(xiàn)的棧，一個(gè)是用鏈表實(shí)現(xiàn)的棧。

數(shù)組實(shí)現(xiàn)：

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;// 指向最后入棧的對(duì)象
    private final int DEFAULT_SIZE = 100;    private boolean canExpendSize = true;// 是否允許擴(kuò)容
    private int multiple = 2;// 擴(kuò)容倍數(shù)

    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;
    }    // 刪除棧底元素，所有元素向后移動(dòng)一位，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;
    }    // 擴(kuò)容
    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;
    }

}

鏈表實(shí)現(xiàn)：(只實(shí)現(xiàn)了基本功能，可根據(jù)實(shí)際需要添加參數(shù)或者方法)

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 ==

 再給個(gè)測(cè)試類:

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);
    }
}

遇到的幾個(gè)問題：

　　　　1、有沒有棧的官方標(biāo)準(zhǔn)定義？

　　　　　　只要符合后進(jìn)先出(last in first off，LIFO)的數(shù)據(jù)結(jié)構(gòu)都是棧。

　　　　2、泛型 T和object有什么區(qū)別，接收參數(shù)的時(shí)候有什么不同的？？ 

　　　　　　a:約束了此容器中只能存儲(chǔ)一種類型數(shù)據(jù)。

　　　　　　b:在從容器中取出對(duì)象的時(shí)候不需要進(jìn)行類型強(qiáng)轉(zhuǎn)，容器已經(jīng)知道（因?yàn)樵趎ew 容器的時(shí)候在<>中已經(jīng)制定了存儲(chǔ)對(duì)象類型）你存儲(chǔ)的是什么類型，但是object需要進(jìn)行強(qiáng)轉(zhuǎn)。

　　　　3、棧要不要實(shí)現(xiàn)其刪除、插入、查找操作？

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

　　　　4、除了使用數(shù)組和鏈表還有沒有其他棧實(shí)現(xiàn)方式？

　　　　　　應(yīng)該沒有了吧？