栈Stack


Topic: 基本概念学习

Recall

栈(Stack)是一种后进先出(LIFO)的数据结构,操作栈的元素的方法有:

  • 把元素压栈:push(E)
  • 把栈顶的元素“弹出”:pop(E)
  • 取栈顶元素但不弹出:peek(E)

在Java中,我们用Deque可以实现Stack的功能,注意只调用push()/pop()/peek()方法,避免调用Deque的其他方法。

最后,不要使用遗留类Stack

Notes

  • 栈(Stack)是一种后进先出(LIFO:Last In First Out)的数据结构。
  • Queue的特点FIFO如下

              ────────────────────────
      (\(\      (\(\    (\(\    (\(\      (\(\
     (='.') ─> (='.')  (='.')  (='.') ─> (='.')
    O(_")")   O(_")") O(_")") O(_")")   O(_")")
              ────────────────────────
  • 后进后出:

               ───────────────────────────────┐
      (\(\       (\(\    (\(\    (\(\    (\(\ │
     (='.') <─> (='.')  (='.')  (='.')  (='.')│
    O(_")")    O(_")") O(_")") O(_")") O(_")")│
               ───────────────────────────────┘
  • Stack是这样一种数据结构:只能不断地往Stack中压入(push)元素,最后进去的必须最早弹出(pop)来:
  • Stack只有入栈和出栈的操作:
    • 把元素压栈:push(E);
    • 把栈顶的元素“弹出”:pop(E);
    • 取栈顶元素但不弹出:peek(E)。
  • 在Java中,我们用Deque可以实现Stack的功能:
    • 把元素压栈:push(E)/addFirst(E);
    • 把栈顶的元素“弹出”:pop(E)/removeFirst();
    • 取栈顶元素但不弹出:peek(E)/peekFirst()。
  • 为什么Java的集合类没有单独的Stack接口呢?因为有个遗留类名字就叫Stack,出于兼容性考虑,所以没办法创建Stack接口,只能用Deque接口来“模拟”一个Stack了。
  • 当我们把Deque作为Stack使用时,注意只调用push()/pop()/peek()方法,不要调用addFirst()/removeFirst()/peekFirst()方法,这样代码更加清晰。
  • Stack在计算机中使用非常广泛,JVM在处理Java方法调用的时候就会通过栈这种数据结构维护方法调用的层次。例如:

    staticvoid main(String[] args) {
        foo(123);
    }
    
    static String foo(x) {
    return "F-" + bar(x + 1);
    }
    
    staticint bar(int x) {
    return x << 2;
    }

    JVM会创建方法调用栈,每调用一个方法时,先将参数压栈,然后执行对应的方法;当方法返回时,返回值压栈,调用方法通过出栈操作获得方法返回值。

    因为方法调用栈有容量限制,嵌套调用过多会造成栈溢出,即引发StackOverflowError

    我们再来看一个Stack的用途:对整数进行进制的转换就可以利用栈

    例如,我们要把一个int整数12500转换为十六进制表示的字符串,如何实现这个功能?

    首先我们准备一个空栈:

    │   │
    │   │
    │   │
    │   │
    │   │
    │   │
    │   │
    │   │
    └───┘
    

    然后计算12500÷16=781…4,余数是4,把余数4压栈:

    │   │
    │   │
    │   │
    │   │
    │   │
    │   │
    │   │
    │ 4 │
    └───┘
    

    然后计算781÷16=48…13,余数是1313的十六进制用字母D表示,把余数D压栈:

    │   │
    │   │
    │   │
    │   │
    │   │
    │ D │
    │   │
    │ 4 │
    └───┘
    

    然后计算48÷16=3…0,余数是0,把余数0压栈:

    │   │
    │   │
    │   │
    │ 0 │
    │   │
    │ D │
    │   │
    │ 4 │
    └───┘
    

    最后计算3÷16=0…3,余数是3,把余数3压栈:

    │   │
    │ 3 │
    │   │
    │ 0 │
    │   │
    │ D │
    │   │
    │ 4 │
    └───┘
    

    当商是0的时候,计算结束,我们把栈的所有元素依次弹出,组成字符串30D4,这就是十进制整数12500的十六进制表示的字符串。

    计算中缀表达式

    在编写程序的时候,我们使用的带括号的数学表达式实际上是中缀表达式,即运算符在中间,例如:1 + 2 * (9 - 5)

    但是计算机执行表达式的时候,它并不能直接计算中缀表达式,而是通过编译器把中缀表达式转换为后缀表达式,例如:1 2 9 5 - * +

SUMMARY:栈的数据结构是先进先出,在Java中属于集合的一个实现,只能一个口负责进和出是一种低级的实现,因此一般不推荐使用Java的Stack接口。

参考地址:

使用Stack

Java栈为何要使用Deque?

声明:Eironn's Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 栈Stack


Java开发,同时会一些旁门左道。