Java教程

数据结构与算法-栈

本文主要是介绍数据结构与算法-栈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

概念

栈(stack)是一种线性数据结构,栈中的元素只能先入后出(First In Last Out,简称FILO)。
最早进入的元素存放的位置叫作栈底(bottom),最后进入的元素存放的位置叫作栈顶 (top)。

image

存储原理

栈既可以用数组来实现,也可以用链表来实现

数组实现

栈的数组实现如下:
image

数组实现的栈也叫顺序栈或静态栈

链表实现

栈的链表实现如下:
image

链表实现的栈也叫做链式栈或动态栈

操作

入栈(压栈)

入栈操作(push)就是把新元素放入栈中,只允许从栈顶一侧放入元素,新元素的位置将会成为新的栈顶
image
image

出栈(弹栈)

出栈操作(pop)就是把元素从栈中弹出,只有栈顶元素才允许出栈,出栈元素的前一个元素将会成为新的栈顶。
image

应用

  • 函数调用
    每进入一个函数,就会将临时变量作为一个栈入栈,当被调用函数执行完成,返回之后,将这个函
    数对应的栈帧出栈

案例

利用栈实现字符串逆序

public static void reversalStr() {
        ArrayStack stack = new ArrayStack(10);
        String str = "how are you";
        char[] cha = str.toCharArray();
        for (char c : cha) {
            stack.push(c);
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop());
        }
    }

利用栈判断分隔符是否匹配

写过xml标签或者html标签的,我们都知道<必须和最近的>进行匹配,[ 也必须和最近的 ] 进行匹配。

public static void matchHtml() {
        ArrayStack stack = new ArrayStack(5);
        String str = "12<a[b{}c}]>";
        char[] cha = str.toCharArray();
        for (char c : cha) {
            switch (c) {
                case '{':
                case '[':
                case '<':
                    stack.push(c);
                    break;
                case '}':
                case ']':
                case '>':
                    if (!stack.isEmpty()) {
                        char ch = stack.pop().toString().toCharArray()[0];
                        if (c == '}' && ch != '{'
                                || c == ']' && ch != '['
                                || c == ')' && ch != '(') {
                            System.out.println("Error: 开分隔符=" + ch + " 闭分隔符=" + c);
                        }
                    }
                    break;
                default:
                    break;
            }
        }
    }

总结

根据栈后进先出的特性,我们实现了单词逆序以及分隔符匹配。所以其实栈是一个概念上的工具,具体能实现什么功能可以由我们去想象。栈通过提供限制性的访问方法push()和pop(),使得程序不容易出错。

对于栈的实现,我们稍微分析就知道,数据入栈和出栈的时间复杂度都为O(1),也就是说栈操作所耗的时间不依赖栈中数据项的个数,因此操作时间很短。而且需要注意的是栈不需要比较和移动操作,我们不要画蛇添足。

这篇关于数据结构与算法-栈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!