前言
栈(Stack)是限定只能在一段进行插入和删除操作的线性表。
进行插入和删除操作的一端称为“栈顶”(top),另一端称为“栈底”(bottom)。
栈的插入操作称为“入栈”(push),栈的删除 操作称为“出栈”(pop)。
栈具有后进先出(LIFO),先进后出(FILO)的特性。
Stack类
Java工具包下的Stack类继承于Vector,由此可见Stack底层是由数组实现的。
Stack和Collection的关系如下图:
我们来看下Stack的源码:
1 | package java.util; |
根据源码,可以发现Stack的方法调用了Vector类的方法,实现了线程安全。
我们主要看一下Vector里的下面三个方法:
1 | //添加一个元素 |
关联方法如下:
1 | // |
实践
我们如何用数组实现自己的一个stack呢?
1 | public class Stack { |
以上代码就是一个简易的Stack的实现方式。
代码见: https://github.com/JavaZWT/sakuratears
总结
Stack类在编程过程中用到的不是很多,但是计算机栈内存机制遵循先进后出原则,学习Stack类,可以帮助我们加深对程序及数据结构的理解。