栈概述

  • 栈的特点：先进后出，后进先出
  • 应用
    • 浏览器后退功能
    • Dijkstra 双栈算术表达式计算器

栈的四种操作

  • 访问 Access 时间复杂度 O(1)
    访问栈顶元素
  • 搜索 Search 时间复杂度 O(N)
    需要对栈进行遍历查找
  • 插入 Insert 时间复杂度 O(1)

在栈顶插入元素

  • 删除 Remove 时间复杂度 O(1)
    删除栈顶元素

栈实际的常用操作（Java）

  • 创建栈

    1.       //Create a stack 
    2.       Stack<Integer> stack = new Stack<>();

  • 添加元素

    1.       //Add element
    2.       //Time Complexity:O(1)
    3.       stack.push(1);
    4.       stack.push(2);
    5.       stack.push(3);
    6.       //[1,2,3]
    7.       System.out.println(stack.toString());

  • 获取栈顶元素

    1.       //Get the top of stack
    2.       // Time Complexity:O(1)
    3.       //3
    4.       stack.peek();

  • 删除栈顶元素

    1.       //Remove the top of stack
    2.       //Time Complexity:O(1)
    3.       int temp = stack.pop();
    4.       //3
    5.       System.out.println(temp);

  • 栈的大小

    1.       //Stack length
    2.       //Time Complexity:O(1)
    3.       //2
    4.       stack.size();

  • 栈是否为空

    1.       //Stack is empty?
    2.       //Time Complexity:O(1)
    3.       //false
    4.       stack.isEmpty();

  • 遍历栈

    1.       //Iterate a stack    边删除边遍历
    2.       //Time Complexity:O(N)
    3.       while (!stack.isEmpty()) {
    4.           int num = stack.pop();
    5.           System.out.println(num);
    6.       }

LeetCode练习

#20

**#496

参考：https://www.bilibili.com/read/cv8687919?spm_id_from=333.788.b_636f6d6d656e74.10