数据结构-栈
本文介绍数据结构中栈的概念、顺序栈、链式栈的实现以及栈的常见应用,如函数调用栈、表达式求值、括号匹配等

# 数据结构-栈

# 栈的理解

  1. 一种操作受限的线性表结构,只允许在一端插入删除数据
  2. 数组和链表可以在功能上代替栈,但是数组和链表过于灵活,暴露了太多操作接口,使用时比较不可控
  3. 当一个数据集合只涉及在一端插入删除数据,且满足先进后出特性,应该首选栈这种数据结构
  4. 入栈出栈的时间复杂度、空间复杂度都为 O(1)

空间复杂度是指除了原本的数据存储空间外,算法运行还需要的额外存储空间

# 栈的实现

# 顺序栈

  1. 基于数组实现,可以自动扩容

  2. 分析入栈操作

    • 时间复杂度最好为 O(1),最坏为 O(n)
    • 每 k 次入栈,需要一次扩容,均摊时间复杂度为 O(1)
public class MyArrayStack
{
    Object[] baseArray;
    int count;//元素个数
    int depth;//数组大小

    public MyArrayStack(int depth)
    {
        this.depth = depth;
        baseArray = new Object[depth];
    }

    /**
     * 入栈,自动扩容
     *
     * @param o
     * @return
     */
    public boolean push(Object o)
    {
        if (count == depth)
        {//扩容
            depth *= 2;
            Object[] tempArray = new Object[depth];
            System.arraycopy(baseArray, 0, tempArray, 0, count);
            baseArray = tempArray;
        }
        baseArray[count] = o;
        count++;
        return true;
    }

    /**
     * 出栈
     *
     * @return
     */
    public Object pop()
    {
        if (count == 0)
        {
            return null;
        }
        Object o = baseArray[count - 1];
        count--;
        return o;
    }
}

# 链式栈

用链表实现,基于 java LinkedList 类

public class StackByLinkedList
{
    LinkedList baseList = new LinkedList();

    public void push(Object o)
    {
        baseList.addLast(o);
    }

    public Object pop()
    {
        return baseList.removeLast();
    }
}

# 栈的应用

# 函数调用栈

  1. 操作系统给每个线程划分一块独立的内存空间,这个内存被组织成栈的形式,用来存储函数调用时的临时变量
  2. 每进入一个函数就会将临时变量作为栈帧入栈,函数执行完成之后返回对应栈帧,先进后出

# 表达式求值

  1. 操作数栈存放操作数,遇到数字压入操作数栈
  2. 运算符栈存放运算符,遇到运算符时
    • 如果比栈顶运算符优先级高,则存入栈中
    • 如果比栈顶优先级相同或更低,则取出栈顶运算符,取出两个操作数,计算后将结果压入操作数栈,继续比较

# 括号匹配

  1. 表达式包含三种括号,可以相互嵌套,两两对应为合法形式,类似{[}()]这种是不合法形式,使用栈来判断是否合法

  2. 用栈来保存未匹配的的左括号,从左到右扫描,遇到右括号,与栈顶左括号比较,如果不匹配则不合法,如果匹配则继续

    public boolean isValid(String s)
    {
        Stack stack = new Stack();
        HashMap map = new HashMap();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{'); 
        Set left = map.keySet();
        Collection right = map.values();
        char[] chars = s.toCharArray();
        for (char c : chars)
        {
            if (stack.empty() && left.contains(c))
            {
                return false;
            }
            else if (!stack.empty() && left.contains(c))
            {
                if ((char) map.get(c) == (char) stack.peek())
                {
                    stack.pop();
                }
                else
                {
                    return false;
                }
            }
            else
            {
                stack.push(c);
            }
        }
        if (!stack.empty())
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    
Comment here, be cool~

Copyright © 2020 CadeCode

Theme 2zh powered by VuePress

本页访问次数 0

Loading