栈 Stack

栈的特点是:先进后出(LIFO, Last In First Out)

定义

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。

操作

向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈的基本运算

1. 判断栈是否为空
   boolean isEmpty();
2. 清空栈
   void clear();
3. 栈的长度
   int length();
4. 数据入栈
   boolean push(T data);
5. 数据出栈 ，栈中删除
   T pop();
6. 数据出栈 ,栈中不删除
   T peek();

类型

栈的分类有两种：
– 静态栈(数组实现)
– 动态栈(链表实现)

栈的接口定义

栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
CustomStack.java

public interface CustomStack<T> {

    /**
     * 判断是否为空
     *
     * @return
     */
    public boolean isEmpty();


    /**
     * 获取长度
     *
     * @return
     */
    public int length();


    /**
     * 清空栈
     */
    public void clear();


    /**
     * 入栈
     *
     * @param data
     * @return
     */
    public boolean push(T data);

    /**
     * 出栈,移除最后一个
     *
     * @return
     */
    public T pop();


    /**
     * 出栈不移除
     *
     * @return
     */
    public T peek();
}

• 基于数组的实现
  CustomArrayStack.java

class CustomArrayStack<T> implements CustomStack<T> {

    private Object[] objectArray = new Object[16];
    private int size;

    public boolean isEmpty() {
        return size == 0;
    }

    public int length() {
        return size;
    }

    public void clear() {

        for (int i = 0; i < objectArray.length; i++) {
            objectArray[i] = null;
            size--;
        }

    }

    public boolean push(T data) {

        if (size == objectArray.length - 1) {
            Object[] temp = new Object[objectArray.length * 2];

            for (int i = 0; i < objectArray.length; i++) {
                temp[i] = objectArray[i];
            }
            objectArray = temp;
        }


        objectArray[size++] = data;
        return true;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        return size == 0 ? null : (T) objectArray[(size--) - 1];
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        return size == 0 ? null : (T) objectArray[size - 1];
    }

}

• 基于链表的实现

/**
 * 列表实现
 *
 * @param <T>
 */
class CustomListStack<T> implements CustomStack<T> {

    private int size;
    private Node top;

    public class Node {//数据节点
        T data;// 数据
        Node pre;// 前一个
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int length() {
        return size;
    }

    public void clear() {

        top = null;
    }

    public boolean push(T data) {
        Node node = new Node();
        node.data = data;

        if (size == 0) {

            top = node;
        } else {

            node.pre = top;
            top = node;
        }
        size++;
        return true;
    }

    public T pop() {
        if (size == 0) {
            return null;
        }
        T data = top.data;
        top = top.pre;
        size--;
        return data;
    }

    public T peek() {
        if (size == 0) {
            return null;
        }
        T data = top.data;
        return data;
    }

}

(完)