导航：首页 > 开发技术 >

如何正确实现数据结构栈

发表于：2025-01-28 作者：千家信息网编辑

千家信息网最后更新 2025年01月28日，这篇文章主要讲解了"如何正确实现数据结构栈"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"如何正确实现数据结构栈"吧！栈简介栈 (stack)只允许在有

千家信息网最后更新 2025年01月28日如何正确实现数据结构栈

这篇文章主要讲解了"如何正确实现数据结构栈"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"如何正确实现数据结构栈"吧！

栈简介

栈 (stack)只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照 后进先出（LIFO, Last In First Out）的原理运作。在栈中，push 和 pop 的操作都发生在栈顶。

栈常用一维数组或链表来实现，用数组实现的栈叫作 顺序栈 ，用链表实现的栈叫作 链式栈 。

举个例子：就像叠盘子一样，后放的盘子总是在上面，拿盘子时是从上面拿，也就是先拿后来放上面的盘子，最后的盘子是最早放的。

数组实现

对于数组来说，我们模拟栈的过程很简单，因为栈是后进先出，我们很容易在数组的末尾进行插入和删除。所以我们选定末尾为栈顶。

/** * 栈 数组实现 * * @author ervin * @Date 2021/4/20 */public class ArrayStack {    private Object[] data;    //栈顶    private int top;    public ArrayStack(int size) {        this.data = new Object[size];        this.top = -1;    }    public boolean isEmpty() {        return this.top == -1;    }    public boolean isFull() {        return this.top == data.length - 1;    }    public void push(T t) throws Exception {        if (isFull()) {            //扩容            Object[] newDate = new Object[top * 2];            for (int i = 0; i <= top; i++) {                newDate[i] = this.data[i];            }            data = newDate;        }        data[++top] = t;    }    public T pop() throws Exception {        if (isEmpty()) {            throw new Exception("stack empty");        }        return (T) data[top--];    }    @Override    public String toString() {        StringBuilder builder = new StringBuilder();        for (int i = 0; i < data.length; i++) {            builder.append("index:" + i + "value:" + data[i]).append("\n");        }        return builder.toString();    }}

链表实现

我们采用带头节点的单链表在头部插入删除，把头部当中栈顶。插入直接在头节点后插入。而删除也直接删除头节点后第一个元素即可。

/** * 栈 链表实现 * @author ervin * @Date 2021/4/20 */public class ListStack {    private static class Node{        T item;        Node next;        Node(T ele,Node next){            this.item = ele;            this.next = next;        }    }    private Node header;    private int size;    ListStack() {        this.header = new Node(null,null);        this.size = 0;    }    public int size() {        return this.size;    }    public boolean isEmpty() {        return this.size == 0;    }    public void push(T data){        Node n = null;        if (header.next != null){            n = new Node(data,header.next);        } else{            n = new Node(data,null);        }        this.header.next = n;        size++;    }    public T pop() throws Exception {        if (this.header.next == null){            throw new Exception("stack empty");        }        Node n = this.header.next;        if (n.next != null){            this.header.next = n.next;        } else {            this.header.next = null;        }        size--;        return (T)n.item;    }}

栈的常见应用场景

实现浏览器的回退和前进功能

我们只需要使用两个栈(Stack1 和 Stack2)和就能实现这个功能。比如你按顺序查看了 1,2,3,4 这四个页面，我们依次把 1,2,3,4 这四个页面压入 Stack1 中。当你想回头看 2 这个页面的时候，你点击回退按钮，我们依次把 4,3 这两个页面从 Stack1 弹出，然后压入 Stack2 中。假如你又想回到页面 3，你点击前进按钮，我们将 3 页面从 Stack2 弹出，然后压入到 Stack1 中。