数据结构学习—— 栈(stack)

  • 什么是栈
  • 无处不在的栈——栈的应用
  • 使用数组实现ArrayStack及时间复杂度分析
  • Leetcode20题：有效的括号

什么是栈(stack)

栈(stack)是一种运算受限的线性数据结构，运算受限指的是栈这种数据结构仅允许在一端添加元素，删除元素，这一端被称作栈顶，相对应的另一端则称为栈底。如图所示：

stack.jpg



当前栈，如果想要添加元素“D”只能从栈顶部添加，从栈中取出元素则还是从栈顶开始取元素，所以栈是一种后进先出的数据结构即：LIFO(Last In First Out)。

无处不在的栈——栈的应用

一：Undo(撤销操作)

当我们在文档编辑器中输入文字，当发现输入错误时，想要撤销到前一步，这个操作就是Undo。撤销的原理实际上就是栈这种数据结构来设计实现的。例如：李雷在某个文档编辑器上输入文字“我爱韩梅梅”，结果，由于李雷满脑子想的都是韩梅梅的音容笑貌，不小心将内容输入成了“我爱含梅梅”。李雷想将内容恢复到“我爱” 这一步，所以他按了三次“Ctrl+z”,然后又依次将“韩”，“梅”，“梅”三个字输入了进去。

Undo1


Undo2


Undo3



Undo(撤销)看似很高级的操作，背后的原理就是栈。

二：C语言printf()函数

来看一个C语言的问题：

#include<stdio.h>
int main(void){
    int i=1;
    printf("%d%d%d",i,i++,i++);
    return 0;
}

这个程序的运行结果是什么？如果只是知道i++与++i的区别是不足以解决这道问题的。先公布答案，这个程序的运行结果为：321，这与printf的底层原理有关，因为printf的底层实现就是栈。还是拿李雷韩梅梅来举例说明。

printf("我爱韩梅梅");

printf函数首先会将字符串内容从右至左 push到栈中。

printf



然后，再将栈里面的元素依次pop出来，这样我们就能看到"我爱韩梅梅"这个字符串被打印出来了。这道题也是一样，首先将最右边的%d即“i++” push到栈中，i==1，1入栈后，执行++操作，i的值变成了2。按照上述思路依次将所有元素推入栈中，栈的情况为：

printf2



将所有的元素出栈，出栈的顺序就是我们看到的打印结果即：321。

三：程序调用系统栈

有如下程序：

A();
function A(){
1    ...
2    B();
3    ...
4    end
}
function B(){
1    ...
2    C();
3    ...
4    end
}
function C(){
1    ...
2    ...
3    ...
4    end
}

程序从A方法开始调用，执行到 A方法的第二行，计算机发现需要执行B方法，这时就会将执行到哪一步这样一个信息压入到系统栈中。例如，定义A2为A方法的第二行，计算机此时将A2压入系统栈，表明执行到了A方法的第二行。

system



计算机在系统栈压入这样一个信息后，开始执行B方法，执行到B方法的第二行，发现需要执行C方法，于是计算机将B2压入系统栈中。
system



计算机开始执行C方法，C方法中没有调用其他的函数，执行结束后，计算机发现系统栈中有残留的任务，于是pop stack 发现需要回去执行完B方法，且执行到了B方法的第二行。B方法执行完毕后，计算机又去看了看系统栈，发现仍有残留的任务需要执行，于是乎又 pop stack 发现原来A方法还没有执行完毕，且执行到了第二行，所以计算机又将A方法执行完毕。这时系统栈为空，计算机终于松了一口气，知道所有的任务已经执行完毕了~

使用数组实现ArrayStack及时间复杂度分析

本文中ArrayStack的底层实现数组为动态数组：动态数组,DobbyKim's Blog。

public interface Stack<E> {
    void push(E e);
    E pop();
    E peek();
    int getSize();
    boolean isEmpty();
}
public class ArrayStack<E> implements Stack<E>{
    Array<E> array;
    public ArrayStack(int capacity){
        array = new Array<>(capacity);
    }
    public ArrayStack(){
        array = new Array<>();
    }
    public void push(E e){...}
    public E pop(){...}
    public int getSize(){...}
    public int getCapacity(){...}
    public boolean isEmpty(){...}
    public E peek(){...}
    public String toString(){...}
}

点击查看源码


ArrayStack的方法push 与 pop 的均摊时间复杂度为O(1),因为这里面涉及到底层实现Array为动态数组，resize()扩容操作为一个O(n)的算法。getSize()方法，peek()方法，isEmpty()方法的时间复杂度均为O(1)。

Leetcode20题：有效的括号

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


有效字符串需满足：


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


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


注意空字符串可被认为是有效字符串。

  • 示例 1: 
输入: "()"
输出: true
  • 示例 2: 
输入: "()[]{}"
输出: true
  • 示例 3: 
输入: "(]"
输出: false
  • 示例 4: 
输入: "([)]"
输出: false
  • 示例 5: 
输入: "{[]}"
输出: true

问题解决思路：栈。只要是左侧的括号为'('，'['，'{'就push到栈中，遇到与之匹配的右侧括号则pop,最后栈如果为空则说明匹配成功。Java代码如下：

import java.util.Stack
class Solution {
    public boolean isValid(String s) {
        Stack<Character>stack = new Stack<>();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{'){
                stack.push(s.charAt(i));
            }else{
                if(stack.isEmpty())
                    return false;
                char c = stack.pop;
                if(s.charAt(i)==')' && c!='(')
                    return false;
                if(s.charAt(i)==']' && c!='[')
                    return false;
                if(s.charAt(i)=='}' && c!='{')
                    return false;
            }
        }
        return stack.isEmpty();
    }
}