算法入门之栈

前言

了解完算法的基本数据结构 链表 和数组后，我们就可以开始了解基于这些基本数据衍生出来的其它数据结构，如堆、栈、队列等，今天详细聊聊栈，其它文章参考

数组简介

链表简介

什么是栈

栈是一种线性结构，最常见的生活中的例子就是羽毛球筒

羽毛球筒只开放一端入口，那么先放入的球一定是在底部，最后放入的球在最顶部，拿球时先获取的就是靠近顶部的球，只有不停的获取才能将底部的球拿到。

栈也就是这样，只能从一端入栈和出栈，这种顺序我们称为FILO（First In Last Out）先进后出，最早进入的元素称为栈底，最后进入的元素我们称为栈顶，如下

栈是链表和数组的基本数据的衍生结构，所以可以采用链表或者数据实现，具体思路如下

数组实现栈

用数组来实现栈太简单，我们可以参考之前数组的相关文章

数组简介

入栈就是在数组的尾部插入元素不涉及到数组元素移动，出栈就是将数组尾部的元素清除，示意图如下

入栈

出栈

实现代码

 /**
 * 用数组实现栈
 */class MyStack1 {
    // 数组的实际大小
     private  int size;
    private Object[] arr;
    public MyStack1(int capacity){
        arr = new Object[capacity];
        size = 0;
    }
    // 入栈
    public  void  push(Object data){
        if (size == arr.length){
            throw new Runtime Exception ("超过栈的最大容量");
        }
        arr[size] = data;
        size++;
    }
    // 出栈
    public Object pull(){
        if (size == 0){
            throw new RuntimeException("栈为空！");
        }
        Object data = arr[size-1];
        // 恢复数组指定位置默认值
        arr[size-1] = null;
        size--;
        return data;
    }
    public void show(){
        System.out.println("打印栈存放数据："+ Arrays.toString(arr));
    }
}
  

链表实现栈

链表实现栈同样是尾部指针的移动，如下是链表实现的示意图

入栈就是将原队尾的next指针指向新节点即可，而出栈就是将原队尾节点的上一个节点的next指针指向null。

入栈

出栈

实现代码如下

 /**
 * 用链表实现栈
 */class MyStack2 {
    // 链表元素个数
    private int size;
    // 头节点
    private Node head;
    // 尾节点
    private Node last;
    // 入栈
    public void push(Object data){
        Node node = new Node(data);
        if (size == 0){
            head = node;
            last = node;
        }else {
            last.next = node;
            last = node;
        }
        size++;
    }
    // 出栈
    public Object pull(){
        if (size == 0){
            throw new RuntimeException("栈数据为空");
        }
        Object data = last.data;
        if (size == 1){
            head = null;
            last = null;
        }else {
            // 获取倒数第二个节点
            Node index = getIndex(size - 2);
            index.next = null;
            last = index;
        }
        size--;
        return data;
    }
    // 获取指定下标的元素从0开始
    public Node getIndex(int index){
        if (index <0 || index>=size){
            throw  new RuntimeException("数组下标异常");
        }
        Node temp = head;
        for (int i = 0; i <index; i++) {
            temp = temp.next;
        }
        return temp;
    }
    public void show(){
        Node temp = head;
        while (temp!=null){
            System.out.println(temp);
            temp = temp.next;
        }
    }
}
class Node{
    // 数据
    Object data;
    // 下一个节点指针
    Node next;
    public Node(Object data){
        this.data = data;
        next = null;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", next=" + next +
                '}';
    }
}
  

总结

从操作代码可以看出，无论栈的实现方式是采用数组还是链表，入栈出栈都非常简单仅仅是一个元素的移动，所以入栈和出栈操作时间复杂度都为O(1)。