龙空技术网

算法入门之栈

Java面试365 228

前言:

现时同学们对“出栈顺序如何计算”大约比较珍视,姐妹们都想要了解一些“出栈顺序如何计算”的相关知识。那么小编同时在网摘上搜集了一些关于“出栈顺序如何计算””的相关文章,希望同学们能喜欢,大家一起来学习一下吧!

算法入门之栈前言

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

数组简介

链表简介

什么是栈

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

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

栈也就是这样,只能从一端入栈和出栈,这种顺序我们称为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 RuntimeException("超过栈的最大容量");        }        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)。

标签: #出栈顺序如何计算