Question

栈与队列的概述

• 栈是限定仅在表尾进行插入和删除操作的线性表 。
• 队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

栈的定义

• 我们把允许插入和删除的一端称为栈顶(top) ,另一端称为核底 (bottom),不含任何数据元素的称为空钱。栈又称为后进先出 (LastIn FilrstOut) 的线性表，简 称 LlFO 结构 。
• 首先它是一个统性表 ,也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶 ,而不是栈底 。

栈的顺序存储结构

• 栈的顺序存储其实也是线性表顺序存储 的简化，我 们简称为顺序栈。下标为 0 的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底 。

顺序栈代码实现

public interface Stack<E> {

    //返回栈的长度
     int length();
     //出栈
     E pop();

    //进栈
     void push(E element);

    //访问栈顶元素
     E peek();

    //判断栈是否为空
     boolean empty();

     //清空栈
     void clear();

     String toString();
}

/**
 * 栈的顺序存储结构
 * 栈是先进后出的线性表
 * @author qinxuewu
 * @create 19/2/7 下午 1:23
 * @since 1.0.0
 *
 */
public class SequenceStack<E> implements  Stack<E> {
    //定义栈长度  给个默认值
    private int capacity = 16;
    //保存顺序栈中元素的个数
    private int size;
    //定义一个数组用于保存顺序栈中的元素
    private Object[] elementData;

    public SequenceStack(){
        this.elementData = new Object[capacity];
        this.size=0;
    }
    //以指定的大小来创建栈
    public SequenceStack(int initSize){
        this.capacity=initSize;
        this.elementData = new Object[capacity];
        this.size=0;
    }

    @Override
    public int length() {
        return size;
    }

    /**
     * 出栈思路：
     * 1.判断当前炸是否为空
     * 2. 栈不为空。先进后出原则。直接去栈顶的元素出栈 szie-1 的元素
     * 3. 返回出栈的元素，
     *
     * @return
     */
    @Override
    public E pop() {
        if(empty()){
            throw new IndexOutOfBoundsException("栈已空不能出栈");
        }
        E oldValue = (E)elementData[size - 1];
        //让垃圾回收器及时回收，避免内存泄露
        elementData[--size] = null;
        return oldValue;
    }

    /**
     * 进栈:
     * 1. 判断当前默认的栈长度是否已用完
     * 2. 如果栈空间已用完每次增加 16 位的长度
     * 3. 在新的栈空间的末尾元素增加新元素
     *
     * @param element
     */
    @Override
    public void push(E element) {
        //炸已满  每次增加 16 的长度
        if((size+1)>capacity){
            capacity=capacity+16;
            elementData = Arrays.copyOf(elementData, capacity);
        }
        elementData[size++]=element;
    }

    /**
     * 访问访问栈顶元素：
     * 先进后出。访问栈顶元素
     * @return
     */
    @Override
    public E peek() {
        if(empty()){
            return null;
        }
        E value = (E)elementData[size - 1];
        return value;
    }

    @Override
    public boolean empty() {
        return size==0;
    }

    @Override
    public void clear() {
        for (int i = 0; i <size ; i++) {
            elementData[i] = null;
        }
        this.size=0;
    }

    @Override
    public String toString() {
        StringBuilder str=new StringBuilder();
        str.append("[");
        for (int i = 0; i <size ; i++) {
            str.append(elementData[i]+",");
        }
        str.append("]");
        return str.toString();
    }

    public static void main(String[] args) {
        SequenceStack<Integer> stack=new SequenceStack<>();
        for (int i = 0; i <50 ; i++) {
            stack.push(i);
        }
        System.out.println(stack.toString());
        System.out.println(stack.size);
        System.out.println(stack.pop());
        System.out.println(stack.toString());
    }
}

栈的链式存储结构

• 栈的链式存储结构简称为链栈。通常栈顶是放在单链表的头部，对于链栈来说，是不需要头结点的。
• 对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间
• 对于空栈来说，链表原定义是头指针指向空 , 那么链栈的空其实就是 top=null 的时候。

进栈思路

• 让栈顶 top 指向新创建的元素，并且新元素的 next 指针指向原来的栈顶元素

出栈思路

• 出栈就是把当前栈顶替换为栈顶的 next 指向的结点。然后释放原栈顶的 next 引用

链栈代码实现

public class LinkStack<T> {

    private class Node {
        private T data;
        // 指向下个节点的指针
        private Node next;
        // 无参构造器
        public Node() {
        }
        public Node(T data, Node next) {
            this.data = data;
            this.next = next;

        }
    }

    //链栈的栈顶元素
    private Node top;
    // 结点数量
    private int size;

    public  LinkStack(){
        //空链栈，top 的值为 null
        top = null;
    }

    // 以指定数据元素来创建链栈，该链栈只有一个元素
    public LinkStack(T element) {
        top = new Node(element, null);
        size++;
    }
    public int length() {
        return size;
    }

    /**
     * 进栈思路：
     * 让栈顶 top 指向新创建的元素，并且新元素的 next 指针指向原来的栈顶元素
     * @param element
     */
    public void push(T element) {
        top = new Node(element, top);
        size++;

    }

    /**
     * 出栈思路：
     * 出栈就是把当前栈顶替换为栈顶的 next 指向的结点。然后释放原栈顶的 next 引用
     * @return
     */
    public T pop() {
        Node oldTop = top;
        // 让 top 引用指向原栈顶元素的下一个元素
        top = top.next;
        // 释放原栈顶元素的 next 引用
        oldTop.next = null;
        size--;
        return oldTop.data;

    }

    // 访问栈顶元素，但不删除栈顶元素
    public T peek(){
        return top.data;
    }

    // 请空链栈
    public void clear() {
        top = null;
        size = 0;
    }



    public static void main(String[] args) {
        LinkStack<Integer> stack=new LinkStack<Integer>();

        for (int i = 0; i <5 ; i++) {
            stack.push(i);
        }
        System.out.println(stack.pop());
        System.out.println(stack.size);

    }
}

栈的应用（递归)

斐波那契数列实现

说如果兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子 来。假设所有兔都不死，那么一年以后可以繁殖多少对兔子呢?

我们拿新出生的一对小兔子分析一下;第一个月小兔子没有繁殖能力，所以还是 一对 i 两个月后，生下一对小兔子数共有两对; 三个月以后，老兔子又生下一对，因 为小兔子还没有繁殖能力 , 所以一共是三对......依次类推可以列出下表（表 4-8-1)。

前面相邻两项之和，构成了后一项

public class DiGuiTest {
    public static void main(String[] args) {
        for (int i=1;i<=12;i++){
            System.out.println(test(i));
        }
    }
    /**
     *
     * @param n 月份
     */
    public static int test(int n){
        if(n==1 || n==2){
            /**
             * 两个月后新出生的兔子才有繁殖能力。
             * 所以前两个月都没有兔子出生 都是开始的第一对兔子
             */
            return  1;
        }
        //前面相邻两项之和，构成了后一项
        return  test(n-1)+test(n-2);
    }
}