《一起学习java和数据结构》系列-栈

如何理解栈这种数据结构？

关于栈，我们生活中有非常多的例子，比如手枪弹夹中的子弹，往弹夹中一颗一颗从下往上压子弹，相当于入栈；而发射子弹只能从上面往下一颗一颗弹出子弹，相当于出栈。我们不能通过任何手段发射弹夹中间的子弹。先进着后出，后进着先出，这种结构就是典型的栈。

从上面的例子不难看出，栈是一种受限制的线性表，只允许在栈的顶端进行出栈和入栈操作。

为什么会出现栈这种数据结构？

我们前面学习过数组和链表，它们和栈一样都是线性表结构，而且没有栈在删除和添加时的操作限制。我们直接用数组和链表去代替栈是否可行？

答案是否定的，数组和链表可以在数据结构上代替栈，但是在一些需要使用到先进者后出，后进着先出业务场景的时候，数组和链表暴露了太多的接口去操作数据，可能会使数据不可控制。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选栈这种数据结构。

如何实现一个栈？

从栈的定义，我们不难看出栈有两种实现方式，分别是数组和链表。数组实现的栈是顺序栈，链表实现的栈是链式栈。

顺序栈（数组实现）

public class ArrayStack {
    
    private int[] arr;//数组
    private int count;//元素个数
    private int size;//栈的大小
    private final static int DEFAULT_SIZE=16; //默认容量
    public ArrayStack(int size) {
        this.arr=new int[size];
        this.count=0;
        this.size=size;
    }
    public ArrayStack() {
        this.arr=new int[DEFAULT_SIZE];
        this.count=0;
        this.size=DEFAULT_SIZE;
    }

    /**
     * 入栈
     * @param a
     */
    public void push(int a){
        if (count==size){//如果栈满了，则申请一个2倍容量大小的数组，实现动态扩容
            arr = Arrays.copyOf(arr, arr.length * 2);
        }
        arr[count]=a;
        count++;
    }
    
    /**
     * 出栈，将栈顶元素删除，并返回该元素
     * @return 栈顶元素
     */
    public int pop(){
        if (count==0){//如果栈中元素为空
            return -1;
        }
       int result=arr[count-1];
       count--;
       return result;
    }
}

链式栈（链表实现）

/**
 * 链式栈
 */
public class LinkedStack<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 topNode;//记录栈顶元素
    private int size;//栈的大小

    public LinkedStack() {
        this.topNode = null;
        this.size=0;
    }

    /**
     * 入栈
     * @param element
     */
    public void push(T element){
         topNode = new Node(element, topNode);//让新加入的节点指向老的节点
         size++;
    }

    /**
     * 移除栈顶元素并返回
     * @return
     */
    public T pop(){
        Node oldTop=topNode;
        topNode= topNode.next;
        oldTop.next=null;
        size--;
        return oldTop.data;
    }
}

本文是关于数据结构的栈，希望大家可以和我一起学习成长，早日找到自己想要的生活。

我是方褚，一个努力成长的程序员。

希望可以多多转发、收藏、关注我，和我一起讨论！！