栈

一、定义

栈（Stack）是一种基于后进先出（LIFO，Last In First Out）原则的数据结构。在栈中，最后插入的元素首先被移除，而最先插入的元素最后被移除。栈具有压栈（Push）和弹栈（Pop）两个基本操作，以及查看栈顶元素的操作。

二、特点

栈具有以下特点：

后进先出：最后压入栈的元素会最先弹出，形成了后进先出的特性。
限制访问：栈只允许在栈顶进行插入和删除操作，其他位置的元素无法直接访问。
快速操作：由于栈的限制，压栈、弹栈和查看栈顶元素的操作通常具有常数时间复杂度，即O(1)。

利用栈比使用递归的效率要高，递归本质上也是使用了栈的方式，以java为例子，java的递归使用的是虚拟机栈，会占用更多的资源，并且虚拟机栈的大小一般不大，所以在超过一定层数就会导致栈溢出

三、实现方式

栈可以通过数组或链表等不同的数据结构来实现（动态数组和链表的一种应用方式）：

数组实现：使用数组来存储栈中的元素，同时使用一个指针来表示栈顶元素的位置。压栈操作将元素插入数组的末尾，弹栈操作将数组末尾的元素移除。
链表实现：使用链表来存储栈中的元素，同时使用链表的头部来表示栈顶元素。压栈操作将元素插入链表的头部，弹栈操作将链表头部的元素移除。

四、应用场景

栈在计算机科学和工程领域有着广泛的应用，例如：

函数调用：函数的调用栈（Call Stack）是栈的一个典型应用场景，用于保存函数的调用信息，包括参数、局部变量和返回地址等。
表达式求值：栈可以用于中缀表达式转换为后缀表达式，并且通过后缀表达式进行求值。
内存管理：操作系统中的内存管理和调度算法中，栈用于保存进程的上下文信息，如程序计数器、寄存器值等。
回溯算法：在深度优先搜索（DFS）等算法中，栈被用于保存当前的状态和路径信息，以便进行回溯。

五、实现

/**
 * @Description 链表实现的泛型
 * @Author lcy
 * @Date 2020/9/14 9:44
 */
public class LinkStack<E> {

    /**
     * 第一个节点值
     */
    private Node<E> top;

    /**
     * 大小
     */
    private int size = 0;

    public int size(){
        return size;
    }

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

    /**
     * 入栈
     */
    public void push(E element){
        top = new Node<>(element,top);
        size++;
    }

    /**
     * 出栈
     */
    public E pop(){
        rangeCheck();
        Node<E> node = top;
        top = top.next;
        size--;
        return node.element;
    }

    /**
     * 获取栈顶位置
     */
    public E peek(){
        rangeCheck();
        return top.element;
    }

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

    /**
     * 校验下标
     */
    private void rangeCheck(){
        if (size <= 0) {
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * 单向节点内部类
     * @author lcy
     * @date 2020/9/7 10:22
     **/
    static class Node<E> {

        /**
         * 当前节点值
         */
        E element;

        /**
         * 下个节点值
         */
        Node<E> next;

        public Node(E element,Node<E> next){
            this.element = element;
            this.next = next;

        }
    }

    @Override public String toString(){

        StringBuilder stringBuilder = new StringBuilder("LinkStack:{");
        Node<E> node = top;
        while (node != null) {
            stringBuilder.append("[").append(node.element).append("],");
            node = node.next;
        }
        stringBuilder.setLength(stringBuilder.length() - 1);
        stringBuilder.append("}");

        return stringBuilder.toString();
    }

    public static void main(String[] args){
        LinkStack<Object> stack = new LinkStack<>();
        stack.push("1");
        stack.push("2");
        stack.push("3");
        System.out.println(stack);
        System.out.println(stack.pop());
        System.out.println(stack);
        stack.push("5");
        System.out.println(stack);
        System.out.println(stack.peek());
    }

}

六、总结

栈是一种常见的数据结构，具有后进先出的特性，适用于各种需要临时保存和管理数据的场景。栈可以通过数组或链表等不同的数据结构来实现，每种实现方式都有着各自的特点和适用范围。对栈的深入理解和熟练运用，有助于提高程序的效率和性能。

栈 ​

一、定义 ​

二、特点 ​

三、实现方式 ​

四、应用场景 ​

五、实现 ​