栈之Java实现数据结构

一、什么是栈？

　　栈（stack）又叫先进后出表，它是一种运算受限的线性表。它只允许在表的一端进行插入和删除操作，我们称之为栈顶，相对另一端称为栈底。

　　我们可以通俗一点，将栈比喻为一个垃圾桶，垃圾桶底就类似我们的栈底（bottom），垃圾桶口就类似我们的栈顶（top）,当有第一个垃圾扔进去时肯定在最底上，直至桶满，我们把垃圾往出倒肯定是最后扔进去的垃圾最先出来。这就类似我们的栈元素先进后出，用一张图来进行表示：

 　　栈有两个基本操作：

　　（1）进栈：入栈或压栈，将新元素放到栈顶元素的上面，使之成为新的栈顶元素；

　　（2）出栈：退栈，将栈顶元素删除掉，使得与其相邻的元素成为新的栈顶元素；

二、栈的数据结构

　　栈和队列及ArrayList以及LinkedList一样，都可以通过顺序结构的数组或者链式结构的链表来实现。分别以两个示意图来表示两种结构：

三、栈结构的代码实现

　　前面几节我们都是通过链表来实现的，这节我们就用顺序表数组来实现栈。

class Stack<E>{
    Object[] data; //数据存储，0栈底，STACK_SIZE栈顶
    transient int top; //栈顶位置标志
    transient final static int DEFAULT_STACK_SIZE = 5; //模拟默认栈大小为5，就不在写如何扩容

    public Stack(){
       this(DEFAULT_STACK_SIZE);
    }
    public Stack(int size){
        data = new Object[size];
        top = -1;
    }

    /**
     * 入栈
     */
    public synchronized boolean push(E e){
        checkStackOutOfMemory();
        data[++top] = e;
        return true;
    }
    /**
     * 出栈,将栈顶元素移除，先进后出
     */
    public synchronized E pop(){
        if(empty())
            return null;
        Object e = data[top];
        data[top--] = null;
        return (E)e;
    }

    /**
     * 获取栈顶元素，并不移除
     * @return
     */
    public synchronized E peek(){
        if(empty())
            return null;
        return (E)data[top];
    }
    /**
     * 获取栈中元素个数
     */
    public synchronized int size(){
        return top + 1;
    }
    /**
     * 栈是否为空
     */
    public synchronized boolean empty(){
        return top == -1;
    }
    /**
     * 栈是否已满
     */
    void checkStackOutOfMemory(){
        if(top == data.length - 1)
            throw new IndexOutOfBoundsException("栈溢出，入栈失败! Stack size : " + data.length);
    }
}

　　看完之后是不是很简单？栈有个典型的应用算法，叫做-逆波兰表达式法（是一种使用栈来进行运算的表达式）。我将该算法描述记下来，有兴趣的可以去写一下。

　　例如：

  标准四则运算表达式—中缀表达式； 逆波兰表达之后为　  

　　算法：

　　　　中缀表达式转为后缀表达式：

　　　　1）设置一个堆栈，初始时将堆栈顶设置为#

　　　　2）顺序读入中缀表达式，到读到的单词为数字时将其输出，接着读下一个单词；

　　　　3）令x1 为栈顶运算符变量，x2 为扫描到的运算符变量，当顺序从表达试中读到的运算符时赋值给x2，然后比较x1 和 x2 的优先级，若x1 的优先级高于x2的优先级，将x1退栈并输出，接着比较新的栈顶运算符x1，x2的优先级；若 x1的优先级低于x2的优先级，将x2 入栈;如果x1 = “（”且 x2 = “）”，将x1 退栈；若x1的优先级等于x2的优先级且x1 = “#”而x2=“#”时，算法结束

四、Java中栈Stack存在的问题

　　Java中栈Stack继承了Vector,所以Stack中就拥有了Vector中的方法，对于栈来讲，只能在栈顶进行操作元素，而Vector中有一个很明显的问题，如：

 1     /**
 2      * Inserts the specified element at the specified position in this Vector.
 3      * Shifts the element currently at that position (if any) and any
 4      * subsequent elements to the right (adds one to their indices).
 5      *
 6      * @param index index at which the specified element is to be inserted
 7      * @param element element to be inserted
 8      * @throws ArrayIndexOutOfBoundsException if the index is out of range
 9      *         ({@code index < 0 || index > size()})
10      * @since 1.2
11      */
12     public void add(int index, E element) {
13         insertElementAt(element, index);
14     }

 

　　此时就是说这个栈可以在栈中间一个位置插入元素，这就跟栈的思想不一致。所在在使用Java提供的栈时需要注意这点。

　　我们经常说到堆栈，那么堆和栈到底有什么区别？在Java虚拟机中，

　　1）栈主要解决的是程序的运行问题，即程序如何执行，如何处理数据，负责的是运算逻辑；

　　2）堆主要解决的是数据存储问题，既告诉数据怎么放，放在什么位置，负责的是存储逻辑；