一、栈的原理与特性

栈其实是一种特殊的线性表，因为栈只限定了一头进行增加和删除，其实这种应用场景还是蛮广的，比如递归操作，运算符匹配，只要是符合先进后出的队列都可以用栈来表达。因为限定了只能是一头进行增删，如果用顺序存储来实现，也减少了删除结点移动的带来的开销，所以栈如何能确定大小，使用顺序存储来实现也是高效的。

因为栈是一种特殊的线性表，所以跟线性表一样都可以使用顺序存储和链式存储来实现。

二、栈顺序存储的实现-java

public class MyArrayStack {

    Object[] elemArray = null;
    int MaxLength; //stack的最大空间
    int top; //栈顶脚标

    // 使用顺序存储实现stack
    public MyArrayStack(int MaxLen){
        // 初始化一个stack
        this.MaxLength = MaxLen;
        top = -1; //因为数组的脚标初始为0，所以将top初始为-1
        elemArray = new Object[this.MaxLength];
    }

    /**
     * 栈常用方法如下：
     * 1、InitStack 初始化一个栈
     * 2、DestroyStack 若栈存在，则销毁该栈
     * 3、ClearStack 清空一个栈
     * 4、StackEmtry 判断一个栈是否为空
     * 5、GetTop 若栈存在，并且非空，返回栈顶元素
     * 6、push 若栈存在，往栈顶插入一个新的元素
     * 7、pop 若栈存在，并且非空，弹出栈顶元素
     * 8、StackLenth 若栈存在，返回该栈的长度
     */
    public void DestroyStack(){
        elemArray = null;
    }

    public Boolean ClearStack(){
        if (top == -1){return true;}
        for (int index = 0;index <= top;index++){
            //清空就是将数组每个值都置为null
            elemArray[index] = null;
        }
        top = -1;
        return true;
    }

    public Boolean StackEmtry(){
        return top == -1?true:false;
    }

    public Object GetTop(){
        if (top == -1 || elemArray == null){return false;}
        return elemArray[top];
    }

    public Boolean push(Object elem){
        if (top == MaxLength-1 || elemArray == null){return false;}
        elemArray[++top] = elem;
        return true;
    }

    public Object pop(){
         if (top == -1 || elemArray == null){return false;}
        Object elem = elemArray[top];
        elemArray[top] = null;
        top--;
        return elem;
    }

    public int StackLenth(){
        return elemArray.length;
    }

    public String toString(){
        if (top == -1 || elemArray == null){return "";}
        StringBuffer stringBuffer = new StringBuffer();
        for (int index = top;index > -1;index--){
            if (index-1>-1){
                stringBuffer.append(elemArray[index]);
                stringBuffer.append(",");
            }else{
                stringBuffer.append(elemArray[index]);
            }
        }
        return stringBuffer.toString();
    }

    public static void main(String[] args) {
    }
}

三、栈链式存储的实现-java

import java.util.Stack;

public class MyListStack {

    int currLength; //栈大小
    StackNode top; //栈顶指针，也是头结点

    class StackNode{
        Object nodeData; //结点值
        StackNode next; //指向下一个结点的引用
    }

    public MyListStack(){
        currLength = 0;
        top = new StackNode();
        top.nodeData = top.next = null; //初始化一个栈顶指针（头指针）
    }

    /**
     * 栈常用方法如下：
     * 1、InitListStack 初始化一个栈
     * 2、ClearListStack 清空一个栈
     * 3、ListStackEmtry 判断一个栈是否为空
     * 4、GetTop 若栈存在，并且非空，返回栈顶元素
     * 5、push 若栈存在，往栈顶插入一个新的元素
     * 6、pop 若栈存在，并且非空，弹出栈顶元素
     * 7、ListStackLenth 若栈存在，返回该栈的长度
     */

    public Boolean ClearListStack(){
        if (currLength == 0){return true;}
        else {
            StackNode nextNode = top.next;
            StackNode currNode = top;
            for (;currNode != null;currNode = currNode.next){
                currNode.next = null;
                currNode.nodeData = null;
                currNode = nextNode;
            }
            currLength = 0;
            return true;
        }
    }

    public Boolean ListStackEmtry(){
        return currLength == 0 ? true : false;
    }

    public Object GetTop(){
        if (currLength == 0){return false;}
        else{
            return top.nodeData;
        }
    }

    public Boolean push(Object elem){
        if (top.nodeData == null){
            //说明这是一个空栈
            top.nodeData = elem;
            currLength++;
            return true;
        }else{
            StackNode insertNode = new StackNode();
            insertNode.nodeData = elem;
            insertNode.next = top;
            top = insertNode;
            currLength++;
            return true;
        }
    }

    public Object pop(){
        if (currLength == 0){return false;}
        else{
            Object returnData = top.nodeData;
            top = top.next;
            currLength--;
            return returnData;
        }
    }

    public int ListStackLenth(){
        return currLength;
    }

    public String toString(){
        if (currLength == 0){return "";}
        else{
            StringBuffer stringBuffer = new StringBuffer();
            StackNode currNode = top;
            for (;currNode != null;currNode = currNode.next){
                if (currNode.next != null){
                    stringBuffer.append(currNode.nodeData);
                    stringBuffer.append(",");
                }else{
                    stringBuffer.append(currNode.nodeData);
                }
            }
            return stringBuffer.toString();
        }
    }

    public static void main(String[] args) {
    }
}

四、两种实现方式的差异

其实就是因为栈的特殊限制，使得stack的实现还是很简单的，因为只能在一头进行增删，所以不管是顺序实现还是链式实现，增删的时间复杂度都是O(1)，栈只能查看栈顶元素，所以也跟增删一样，时间复杂度都是O(1)。如果能够确定大小，那么就可以使用顺序方式来实现栈，毕竟比链式方式更加节省空间，如果不能确定栈大小，那么还是使用链式方式来实现。普通栈只是一种特殊的线性表，还是属于基础的数据结构，可以用栈实现更加复杂的数据结构。