数据结构与算法学习之(五)栈

<!-- index-menu -->

一、如何理解“栈”?

1、栈是一种操作受限的数据结构,只支持入栈和出栈操作。
2、典型的“栈”结构:后进者先出,先进者后出。
3、从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。
4、特定的数据结构是对特定场景的抽象,而且,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。

二、如何实现“栈”?

1、栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,叫作顺序栈,用链表实现的栈,叫作链式栈。
2、不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)。
不管是顺序栈还是链式栈,存储数据只需要一个大小为 n 的数组就够了。
在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1)。
入栈、出栈只涉及栈顶个别数据的操作,所以时间复杂度都是 O(1)。

数组实现栈:

/**
 * 数组实现栈-入栈出栈
 *
 * @Author: chenqi
 * @Date: 2020.7.9 15:18
 */
public class MyStackByArray {
    // 数据存储
    private Object[] array;
    // 数组大小
    private int size;
    // 数组数据大小
    private int count;
    
   // 省略get set toString()...
  
   // 构造方法
    public MyStackByArray(int size) {
        this.array = new Object[size];
        this.size = size;
        this.count = 0;
    }

    /**
     * 入栈操作
     *
     * @param s
     */
    private void push(String s) {
        if (count >= size) {
            throw new RuntimeException("array已满,无法继续存储");
        }
        if (count == 0) {
            array[0] = s;
        } else {
            array[count] = s;
        }
        count++;
    }

    /**
     * 出栈操作
     */
    private void pop() {
        String result = (String) array[count - 1];
        array[count - 1] = null;
        count--;
        System.out.println(result);

    }

    public static void main(String[] args) {
        MyStackByArray stack = new MyStackByArray(5);
        stack.push("1");
        stack.push("2");
        stack.push("3");
        stack.push("4");
        stack.push("5");
        System.out.println(stack);
        stack.pop();
        System.out.println(stack);
        stack.push("6");
        System.out.println(stack);
    }
}

链表实现栈,以及实现浏览器前进后退功能

/**
 * 链表实现栈-入栈出栈
 * 栈实现浏览器的前进后退功能
 *
 * @Author: chenqi
 * @Date: 2020.7.9 15:18
 */
public class MyStackByLinked {

    private Node first;
    private Node last;
    private int count;

    public MyStackByLinked() {
        this.count = 0;
    }

    class Node {
        private String value;
        private Node next;

        public Node(String value, Node next) {
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value='" + value + '\'' +
                    ", next=" + next +
                    '}';
        }
    }

    @Override
    public String toString() {
        return "MyStackByLinked{" +
                "first=" + first +
                ", last=" + last +
                ", count=" + count +
                '}';
    }

    /**
     * 入栈操作
     * 尾插法插入链表
     * 时间复杂度O(1)
     *
     * @param s
     */
    private void push(String s) {
        Node node = new Node(s, null);
        if (first == null) {
            first = node;
            last = node;
        } else {
            last.next = node;
            last = node;
        }
        this.count++;
    }

    /**
     * 出栈操作
     * 时间复杂度O(n)
     */
    private String pop() {
        // 处理链表为空的情况
        if (first == null) {
            return null;
        } else {
            String value = null;
            // 单独处理链表只有一个元素的情况
            if (count == 1) {
                value = first.value;
                first = null;
                last = null;
                this.count--;
                return value;
            }
            value = this.last.value;
            Node preValue = this.first;
            // 遍历元素,找到最后的元素和倒数第二的元素,让倒数第二的元素变为最后一个元素
            for (int i = 0; i < count; i++, preValue = preValue.next) {
                if (i == count - 2) {
                    last = preValue;
                    last.next = null;
                    this.count--;
                    return value;
                }
            }
        }
        return null;

    }

    MyStackByLinked goLinked = null;
    MyStackByLinked backLinked = null;

    /**
     * 浏览器前进操作
     *
     * @param s
     * @param isNew
     */
    private void goWebsite(String s, boolean isNew) {
        if (goLinked == null) {
            goLinked = new MyStackByLinked();
        }
        // 点击前进,插入数据
        if (null != s && !isNew) {
            System.out.println("前进栈插入数据:" + s);
            goLinked.push(s);
        } else if (null != s && isNew) {
            // 处理这种情况
            // 前进栈 a-b-c-d-e 再后退,后退栈变成 e-d 前进栈变成a-b-c 此时打开新的页面 f
            // 则 前进栈变成 a-b-c-f 后退栈为空
            goLinked.push(s);
            backLinked = null;

        } else {
            // 点击前进,但是没有插入数据,这个操作是先点后退,再点前进,这个时候是没有插入数据的
            String lastValue = backLinked.last.value;
            backLinked.pop();
            System.out.println("没有插入前进数据,点击前进:" + lastValue);
            goLinked.push(lastValue);
            System.out.println("没有插入前进数据,正在浏览:" + goLinked.last.value);
        }
    }


    /**
     * 浏览器后退操作
     */
    private void backWebsite() {
        String pop = goLinked.pop();
        System.out.println("点击后退,弹出前进栈栈顶元素:" + pop);
        if (backLinked == null) {
            backLinked = new MyStackByLinked();
        }
        backLinked.push(pop);
        System.out.println("点击后退,弹出前进栈栈顶元素插入后退栈");
        System.out.println("点击后退后,正在浏览:" + goLinked.last.value);
    }

    /**
     * 测试浏览器前进后退
     */
    @Test
    public void testGoAndBackWebsite() {
        goWebsite("a", false);
        goWebsite("b", false);
        goWebsite("c", false);
        goWebsite("d", false);
        goWebsite("f", false);
        System.out.println("前进栈:" + goLinked);
        System.out.println("后退栈:" + backLinked);
        backWebsite();
        System.out.println("前进栈:" + goLinked);
        System.out.println("后退栈:" + backLinked);
        goWebsite(null, false);
        System.out.println("前进栈:" + goLinked);
        System.out.println("后退栈:" + backLinked);
        backWebsite();
        backWebsite();
        System.out.println("前进栈:" + goLinked);
        System.out.println("后退栈:" + backLinked);
        goWebsite("f", true);
        System.out.println("前进栈:" + goLinked);
        System.out.println("后退栈:" + backLinked);
    }

    public static void main(String[] args) {
        MyStackByLinked linked = new MyStackByLinked();
        linked.push("a");
        linked.push("b");
        linked.push("c");
        linked.push("d");
        linked.push("e");
        System.out.println(linked);
        System.out.println(linked.pop());
        System.out.println(linked.pop());
        System.out.println(linked.pop());
        System.out.println(linked.pop());
        System.out.println(linked.pop());
        System.out.println(linked);
        linked.push("f");
        System.out.println(linked);
    }
}

三、支持动态扩容的顺序栈

1、如果要实现一个支持动态扩容的栈,我们只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后,我们就申请一个更大的数组,将原来的数据搬移到新数组中。
2、出栈的时间复杂度是 O(1)。
入栈操作,最好情况时间复杂度是 O(1),最坏情况时间复杂度是 O(n)。均摊时间复杂度为O(1)。

四、栈的应用

栈在函数调用中的应用

1、经典应用场景:函数调用栈。
2、操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。

栈在表达式求值中的应用

1、常见的应用场景,编译器如何利用栈来实现表达式求值。比如:34+13*9+44-12/3。
2、编译器就是通过两个栈来实现的。其中一个保存操作数的栈,另一个是保存运算符的栈。
从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较。
如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。

栈在括号匹配中的应用

1、借助栈来检查表达式中的括号是否匹配。比如,{[{}]}或 [{()}([])] 等都为合法格式,而{[}()] 或 [({)] 为不合法的格式。
2、用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号。如果能够匹配,比如“(”跟“)”匹配,“[”跟“]”匹配,“{”跟“}”匹配,则继续扫描剩下的字符串。如果扫描的过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。
当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明有未匹配的左括号,为非法格式。

七、如何实现浏览器的前进、后退功能?
1、使用两个栈,X 和 Y,把首次浏览的页面依次压入栈 X,当点击后退按钮时,再依次从栈 X 中出栈,并将出栈的数据依次放入栈 Y。当点击前进按钮时,依次从栈 Y 中取出数据,放入栈 X 中。当栈 X 中没有数据时,那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据,那就说明没有页面可以点击前进按钮浏览了。

最后修改:2020 年 07 月 13 日 06 : 47 PM