本文参考整理自小码哥的《恋上数据结构和算法》课程,图片转自课程ppt,如有侵权,请联系删除~
- 栈是一种特殊的线性表, 只能在一端进行插入或者删除操作
- 往栈中添加元素的操作,一般叫做push,入栈
- 从栈中移除元素的操作,一般叫做pop,出栈(只能移除栈顶的元素)
- 成员变量无非就是size和一个element数组或者链表作为存储元素的容器
接口设计
因为栈是只能在一端进行操作,也就是说除了最上面的元素用户可见,其余元素用户并不可见
因此可以知道栈的基本操作如下:
public class Stack<E> {
// 元素的数量
public int size();
// 是否为空
public boolean isEmpty();
// 入栈
public void push(E element);
// 出栈
public E pop();
// 获取栈顶元素
public E top();
// 清空栈内元素
public void clear();
}
- 由上面的接口可以看到,基本上是前面做过的动态数组或链表的子集
- 因此,在实现栈的操作时,我们可以对之前的动态数组或双向链表进行再封装
可以想到的是两种实现方式
- 继承动态数组或双向链表
- 将动态数组或者双向链表作为成员变量
代码实现
继承方式
继承方式会拿到父类所有非私有变量和方法,所以这里不需要再在Stack类中定义size变量和一些与父类相同的方法
只需要对有变化的方法进行重写或者新增父类中没有的方法
import top.hellocode.List.List;
/**
* @author HelloCode
* @site https://www.hellocode.top
* @date 2022年05月16日 10:44
*/
public class Stack<E> extends ArrayList {
// 入栈
public void push(E element){
add(element);
}
// 出栈
public E pop(){
return (E) remove(size - 1);
}
// 获取栈顶元素
public E top(){
return (E) get(size - 1);
}
}
继承中有一个问题,虽然我们Stack类中只实现了这几个符合栈逻辑的方法
但是在调用Stack中的方法时,还可以拿到父类中所有的非私有方法,这样就会导致栈并不太符合逻辑
包含方式
除了使用继承,还可以将双向链表或者动态数组作为成员变量(私有)
Stack中的方法,通过调用成员变量的方法来实现
package top.hellocode.Stack;
import top.hellocode.List.ArrayList;
import top.hellocode.List.List;
/**
* @author HelloCode
* @site https://www.hellocode.top
* @date 2022年05月16日 10:44
*/
public class Stack<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 void clear() {
list.clear();
}
}
用这种方式实现的栈就只能调用我们所设计的方法,符合栈逻辑。这种设计方式也是目前主流使用的一种