一、定义

栈（stack）是一种线性数据结构，

栈中的元素只能先入后出（First In Last Out，简称FILO）。

最早进入的元素存放的位置叫作栈底（bottom），

最后进入的元素存放的位置叫作栈顶 （top），

出栈从栈顶出。

二、存储原理

栈既可以用数组来实现，也可以用链表来实现。

数组实现的栈也叫顺序栈或静态栈。栈底的数组下标是0。

链表实现的栈也叫做链式栈或动态栈。栈底是链表的尾部，栈顶是链表的头部。

三、操作

1、入栈

入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶

//1、数组栈实现//数组private int[] nums;//栈元素数量private int count;public ArrayStack(int n){    this.nums = new int[n];    count = 0;}public boolean push(int n){    if(count >= nums.length) return false;    nums[count] = n;    count++;    return true;}//2、链表栈实现    //链表    Node head;    //栈元素数量		int size;    //初始化    public LinedStack(){        head = null;        size = 0;    }    //入栈（head头部是栈顶）    public void push(Node node){        if(size == 0){            head = node;        }else {          	//新入栈的元素要存入栈顶即链表头部,因此新元素的下个指针指向当前头部            node.next = head;            //头部赋值为新入栈的元素            head = node;        }       size++;    }

2、出栈

出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

//1、数组栈实现public int pop(){    if(count == 0) return 0;    int n = nums[count-1];    count--;    return n;}//2、链表栈实现public Node pop(){        if(size > 0){            Node  oldHead = head;            head = head.next;            size--;            return oldHead;        }else {            return null;        }  }

入栈和出栈的时间复杂度都是O(1)

支持动态扩容的顺序栈 ，当数组空间不够时，我们就重新申请一块更大的内存，将原来数组中数据统统拷贝过去。这样就实现了 一个支持动态扩容的数组，通过前面学过的知识，可以得知支持动态扩容的顺序栈的入栈时间复杂度是O(n)

五、应用

1、函数调用

每进入一个函数，就会将临时变量作为一个栈入栈，当被调用函数执行完成，返回之后，将这个函 数对应的栈帧出栈

2、浏览器的后退功能

我们使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据， 放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了