栈

栈

栈（Stack）又名堆栈，是允许在同一端进行插入和删除操作的特殊线性表。其中，允许进行插入和删除操作的一端叫作栈顶（Top），另一端叫作栈底（Bottom），栈底固定，栈顶浮动。栈中的元素个数为零时，该栈叫作空栈。插入一般叫作进栈（Push），删除叫作退栈（Pop）。栈也叫作后进先出（FILO-First In Last Out）的线性表

实现一个栈

• push（）：向栈中压入一个数据，先入栈的数据在最下方，先入后出
• pop（）：弹出最顶的数据
• peek（）：返回当前栈顶的数据

栈的具体实现过程如下。

（1）定义栈的数据结构：

 * 基于数组实现的顺序栈
 * @Parm <E>
 *
 */
public class Test<E> {
    private  Object[] data = null;
    private  int maxSize = 0; //栈的容量
    private  int top = -1;  //栈的指针

    // 构造函数：根据指定的size初始化栈

    Test(){
        this(10); //默认栈的大小
    }
    Test(int initialSize){
        if (initialSize >= 0) {
            this.maxSize = initialSize;
            data = new Object[initialSize];
            top = -1;
        }else {
            throw new RuntimeException("Invalid initial size more than zero "+ initialSize);
        }
    }
}

JAVA

（2）数据入栈，向栈顶压入一个数据：

public  boolean push(E e){
       if(top == maxSize - 1) {
           throw new RuntimeException("栈已经满了，无法加入");
       }else {
           data[++top] = e;
           return true;
       }
   }

JAVA

以上代码定义了方法push()来向栈中压入数据，在数据入栈前首先判断栈是否满了，具体的判断依据为栈顶元素的指针位置等于栈的最大容量。注意，这里使用maxSize -1是因为栈顶元素的指针是从 0开始计算的。在栈有可用空间时，使用data[++top]=e在栈顶（top位置）上方新压入一个元素并为top加1。

（3）数据出栈，从栈顶移除一个数据：

public E pop(){
     if (top == -1 ) {
         throw new RuntimeException("栈为空");
     }else {
         return (E)data[top--];
     }
 }

JAVA

以上代码定义了方法pop()来从栈顶移除一个数据，移除前先判断栈顶是否有数据，如果有，则通过data[top–]将栈顶数据移出并给top减1。

（4）数据查询：

public E peek(){
     if (top == -1) {
         throw new RuntimeException("栈为空");
     }else {
         return (E)data[top];
     }
 }

JAVA

以上代码定义了方法peek()来取出栈顶的数据，在取出栈顶的数据前先判断栈顶的元素是否存在，如果存在，则直接返回栈顶元素（注意：这里没有对栈顶的元素进行删除），否则抛出异常。