温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

如何正确实现数据结构栈

发布时间:2021-10-12 15:41:26 来源:亿速云 阅读:138 作者:iii 栏目:编程语言

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

栈简介

栈 (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) 特性。

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

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI