如何正确实现数据结构栈

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

栈简介

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

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

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

数组实现

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

/**
 * 栈 数组实现
 *
 * @author ervin
 * @Date 2021/4/20
 */
public class ArrayStack<T> {
    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<T> {

    private static class Node<T>{
        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 中。

• 检查符号是否成对出现

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串， 判断该字符串是否有效。 有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

比如 "()"、"()[]{}"、"{[]}" 都是有效字符串，而 "(]" 、"([)]" 则不是。

这个问题实际是 Leetcode 的一道题目，我们可以利用栈 Stack 来解决这个问题。

1. 首先我们将括号间的对应规则存放在 Map 中，这一点应该毋容置疑；

2. 创建一个栈。遍历字符串，如果字符是左括号就直接加入stack中，否则将stack 的栈顶元素与这个括号做比较，如果不相等就直接返回 false。遍历结束，如果stack为空，返回 true。

• 反转字符串

将字符串中的每个字符先入栈再出栈就可以了。

• 维护函数调用

最后一个被调用的函数必须先完成执行，符合栈的 后进先出（LIFO, Last In First Out） 特性。

感谢各位的阅读，以上就是“如何正确实现数据结构栈”的内容了，经过本文的学习后，相信大家对如何正确实现数据结构栈这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！