数据结构-栈(Stack)
2020-05-16 本文已影响0人
鼬殿
栈(stack)又名堆栈是一种特殊的线性表,只能在一端进行操作
- 往栈中添加元素的操作,一般叫做
push
,入栈 - 从栈中移除元素的操作,一般叫做
pop
,出栈(只能移除栈顶元素,也叫做:弹出栈顶元素) - 后进先出的原则,
Last In First Out
,LIFO
这里说的“栈”与内存中的“栈空间”是两个不同的概念
栈的接口设计
◼int size();
// 元素的数量
◼ boolean isEmpty();
// 是否为空
◼ void push(E element);
// 入栈
◼ E pop();
// 出栈
◼E top();
// 获取栈顶元素
◼ void clear();
// 清空
栈的内部实现其实可以直接利用前面章节提到的数据结构(动态数组、链表)
package com.njf;
public class Stack<E> {
private ArrayList<E> list = new ArrayList<>();
public void clear() {
list.clear();
}
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);
}
}
调用验证
package com.njf;
public class Main {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(11);
stack.push(22);
stack.push(33);
stack.push(44);
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
可以看到出栈的顺序如下
44
33
22
11