Version: Next

栈的实现

栈是一种特殊的线性表，特点是只能在一端进行操作

  • 向栈中添加元素的操作，一般叫做push，入栈
  • 从栈中移除操作，一般叫做pop，出栈，只能移除栈顶元素，也叫做弹出栈顶元素
  • 后进先出（先进后出）：Last in First Out, LIFO

API接口

int size()——返回元素的数量

boolean isEmpty()——栈是否为空

void push(E element)——入栈

E pop()——出栈

E top()——返回栈顶元素 (aka peek())

实现

info

可以在内部组合一个ArrayList或者LinkedArrayList来实现

MyStack.java
/**
* 实现一个栈
* - 使用ArrayList 或者 双向链表实现， 操作尾部的元素，时间复杂度为O(1)
*/
public class MyStack<E> {
private List<E> list = new ArrayList<>();
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public void push(E element) {
list.add(element);
}
public E pop() {
return list.remove(list.size() - 1);
}
public E top() {
return list.get(list.size() - 1);
}
}
  • 测试
测试
public static void main(String[] args) {
MyStack<Integer> stack = new MyStack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
while (!stack.isEmpty()) {
System.out.println("stack.pop() = " + stack.pop());
}
}
运行结果
stack.pop() = 4
stack.pop() = 3
stack.pop() = 2
stack.pop() = 1

java.util.Stack

继承自Vector，类似ArrayList，但Vector是线程安全的