美文网首页
栈(Stack)

栈(Stack)

作者: 老王子H | 来源:发表于2018-11-28 19:00 被阅读0次

    1.栈的特点:
    栈也是一种线性结构;
    相比数组,栈所对应的操作是数组的子集;
    栈只能从一端添加元素,也只能从这一端取出元素,这一端通常称之为"栈顶";
    向栈中添加元素的过程,称之为"入栈",从栈中取出元素的过程称之为"出栈";
    栈的形象化描述如下图:


    image.png

    "入栈"的顺序若为1-2-3-4,那么出栈的顺序只能为4-3-2-1,即,栈是一种"后进先出"(Last In First Out)的数据结构;
    从用户的角度,只能看到栈顶元素,其它元素对用户是不可见的;
    在计算机世界里,"栈"有着不可思议的作用;

    2.简单举例"栈"的应用
    应用程序中的"撤销"(Undo)操作的底层原理就是通过"栈"来实现的;
    程序调用的系统栈,通过下图简单示例:


    image.png image.png image.png
    1. 栈的实现

    任务目标如下:

        Stack<E>
        ·void push(E)   //入栈
        ·E pop()    // 出栈
        ·E peek()   // 查看栈顶元素
        ·int getSize()  // 查看栈中共有多少元素
        ·boolean isEmpty()   // 查看栈是否为空
    

    需要提一下,从用户的角度来看,只要实现上述操作就好,具体底层实现,用户并不关心,实际上,底层确实有多种实现方式。
    我们准备在之前实现的动态数组基础上,来实现"栈"这种数据结构。
    先定义一个接口Interface,如下:

        public interface Stack<E> {  // 支持泛型
            int getSize();
    
            boolean isEmpty();
    
            void push(E e);
    
            E pop();
    
            E peek();
        }
    

    然后实现一个ArrayStack类,如下:

        public class ArrayStack<E> implements Stack<E> {
            Array<E> array;
    
            //构造函数
            public ArrayStack(int capacity) {
                array = new Array<>(capacity);
            }
    
            //无参数构造函数
            public ArrayStack() {
                array = new Array<>();
            }
    
            //实现getSize方法
            @Override
            public int getSize() {
                return array.getSize();
            }
    
            //实现isEmpty方法
            @Override
            public boolean isEmpty() {
                return array.isEmpty();
            }
    
            //实现getCapacity方法
            public int getCapacity() {
                return array.getCapacity();
            }
    
            //实现push方法
            @Override
            public void push(E e) {
                array.addLast(e);
            }
    
            //实现pop方法
            @Override
            public E pop() {
                return array.removeLast();
            }
    
            //实现peek方法
            public E peek() {
                return array.getLast();
            }
    
            //方便打印测试
            @Override
            public String toString() {
                StringBuilder res = new StringBuilder();
                res.append("Stack: ");
                res.append('[');
                for (int i = 0; i < array.getSize(); i++) {
                    res.append(array.get(i));
                    if (i != array.getSize() - 1) {
                        res.append(", ");
                    }
                }
                res.append("] top");
                return res.toString();
            }
        }
    

    Array类的业务逻辑如下:

        public class Array<E> {
    
            private E[] data;  //设置为private,不希望用户从外部直接获取这些信息,防止用户篡改数据
            private int size;
    
            //构造函数,传入数组的容量capacity构造Array
            public Array(int capacity) {
                data = (E[]) new Object[capacity];
                size = 0;
            }
    
            //无参数构造函数,默认数组容量capacity=10
            public Array() {
                this(10);    //这里的capacity是IDE自动添加的提示信息,实际不存在
            }
    
            //获取数组中的元素个数
            public int getSize() {
                return size;
            }
    
            //获取数组的容量
            public int getCapacity() {
                return data.length;
            }
    
            //判断数组是否为空
            public boolean isEmpty() {
                return size == 0;
            }
    
            //向数组末尾添加一个新元素e
            public void addLast(E e) {
                add(size, e);
            }
    
            //向数组开头添加一个新元素e
            public void addFirst(E e) {
                add(0, e);
            }
    
            //在index位置插入一个新元素e
            public void add(int index, E e) {
    
                if (index < 0 || index > size) {
                    throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");
                }
                if (size == data.length) {
                    resize(2 * size); //扩大为原容量的2倍
                }
                for (int i = size - 1; i >= index; i--) {
                    data[i + 1] = data[i];
                }
                data[index] = e;
                size++;
            }
    
            //获取index位置的元素
            public E get(int index) {
                if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("Get failed. Index is illegal.");
                }
                return data[index];
            }
    
            //获取最后一个元素
            public E getLast() {
                return get(size - 1);
            }
    
            //获取开头的元素
            public E getFirst() {
                return get(0);
            }
    
            //修改index位置的元素为e
            public void set(int index, E e) {
                if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("Set failed. Index is illegal.");
                }
                data[index] = e;
            }
    
            //查找数组中是否存在元素e
            public boolean contains(E e) {
                for (int i = 0; i < size; i++) {
                    if (data[i].equals(e)) {
                        return true;
                    }
                }
                return false;
            }
    
            //查看数组中元素e的索引,若找不到元素e,返回-1
            public int find(E e) {
                for (int i = 0; i < size; i++) {
                    if (data[i].equals(e)) {
                        return i;
                    }
                }
                return -1;
            }
    
            //删除掉index位置的元素,并且返回删除的元素
            public E remove(int index) {
    
                if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("Remove failed. Index is illegal.");
                }
    
                E ret = data[index];
    
                for (int i = index + 1; i < size; i++) {
                    data[i - 1] = data[i];
                }
                size--;   //data[size]会指向一个类对象,这部分空间不会被释放loitering objects
                data[size] = null;
    
                if (size == data.length / 4 && data.length / 2 != 0) {
                    resize(data.length / 2);  //被利用的空间等于总空间的一半时,将数组容量减少一半
                }
                return ret;
            }
    
            //删除掉数组开头的元素,并返回删除的元素
            public E removeFirst() {
                return remove(0);
            }
    
            //删除掉数组末尾的元素,并返回删除的元素
            public E removeLast() {
                return remove(size - 1);
            }
    
            //如果数组中有元素e,那么将其删除,否则什么也不做
            public void removeElement(E e) {
                int index = find(e);
                if (index != -1) {
                    remove(index);
                }
            }
    
    
            @Override
            public String toString() {    //覆盖父类的toString方法
    
                StringBuilder res = new StringBuilder();
                res.append(String.format("Array: size=%d, capacity=%d\n", size, data.length));
                res.append('[');
                for (int i = 0; i < size; i++) {
                    res.append(data[i]);
                    if (i != size - 1) {
                        res.append(", ");
                    }
                }
                res.append(']');
                return res.toString();
            }
    
            private void resize(int newCapacity) {
                E[] newData = (E[]) new Object[newCapacity];
                for (int i = 0; i < size; i++) {
                    newData[i] = data[i];
                }
                data = newData;
            }
        }
    
    1. 对我们实现的栈进行测试:
        public class Main {
    
            public static void main(String[] args) {
    
                ArrayStack<Integer> stack = new ArrayStack<>();
    
                //测试入栈push
                for (int i = 0; i < 5; i++) {
                    stack.push(i);
                    System.out.println(stack);
                }
    
                //测试出栈
                stack.pop();
                System.out.println(stack);
            }
        }
    
    
    输出结果如下:
    
    Stack: [0] top
    Stack: [0, 1] top
    Stack: [0, 1, 2] top
    Stack: [0, 1, 2, 3] top
    Stack: [0, 1, 2, 3, 4] top
    Stack: [0, 1, 2, 3] top
    

    5.栈的时间复杂度分析

        Stack<E>
        ·void push(E)    O(1) 均摊
        ·E pop()    O(1)   均摊
        ·E peek()    O(1)
        ·int getSize()    O(1)
        ·boolean isEmpty()    O(1)
    
    1. 栈的另外一个应用——括号匹配

    业务逻辑如下:

        import java.util.Stack;
    
        class Solution {
            public boolean isValid(String s) {
                Stack<Character> stack = new Stack<>();
                for (int i = 0; i < s.length(); i++) {
                    char c = s.charAt(i);
                    if (c == '(' || c == '[' || c == '{') {
                        stack.push(c);
                    } else {
                        if (stack.isEmpty()) {
                            return false;
                        }
                        char topChar = stack.pop();
                        if (topChar == '(' && c != ')') {
                            return false;
                        }
                        if (topChar == '[' && c != ']') {
                            return false;
                        }
                        if (topChar == '{' && c != '}') {
                            return false;
                        }
                    }
                }
                return stack.isEmpty();   //这里很巧妙
            }
    
            //测试
            public static void main(String[] args){
                System.out.println((new Solution()).isValid("()"));
                System.out.println((new Solution()).isValid("()[]}{"));
                System.out.println((new Solution()).isValid("({[]})"));
                System.out.println((new Solution()).isValid("({)}[]"));
    
            }
        }
    

    相关文章

      网友评论

          本文标题:栈(Stack)

          本文链接:https://www.haomeiwen.com/subject/glbzqqtx.html